摘要
查询是一种重要的数据库操作。在k-匿名隐私保护模型中,每条元组不仅包括精确数据,还包括泛化数据,因此k-匿名数据是一种不确定数据。为了讨论k-匿名数据的查询问题,首先,提出一种描述k-匿名数据的不确定性数据模型,在此基础上,定义了k-匿名数据的成员(Membership)问题、可能性(Possibility)问题、确定性(Certainty)问题、包含(Containment)问题等查询问题,然后,讨论了这些问题的数据复杂度,证明了Membership问题是PTIME,q-Membership问题是NP-完全的,q′-Containment问题是Πp 2-完全的,q-Containment问题coNP-完全的,Possibility问题是PTIME,q-Possibility问题是NP-完全的,Certainty问题是coNP-完全的。这些结论为k-匿名隐私保护模型中不确定性数据查询方法的研究奠定了理论基础。
It is a very important operation to query on databases. Each tuple in the k-anonymity privacy protection model contains not only the accurate data, but also the generalized data, so the k-anonymous data is a kind of uncertain data. In order to discuss the querying problem of k-anonymous data, a k-anonymous data model based on the possible world is proposed first. And then, the querying problems as Membership, Possibility, Certainty, Containment are defined. Finally the data-complexity of these querying problems are investigated, and show that Membership is in PTIME, q-Membership is NP-complete, q^Containment is lip 2-complete, q-Containment is coNP-complete, possibility is in PTIME, q-Possibility is NP-complete, certainty is coNP-complete. These conclusions lay a theoretical foundation for the study of the querying of uncertain data in the k-anonymity privacy protecting model.
出处
《计算机与数字工程》
2013年第11期1779-1783,1865,共6页
Computer & Digital Engineering
基金
国家自然科学基金(编号:61070032)资助
