k-匿名隐私保护模型中不确定性数据的查询问题  

Querying of Uncertain Data in the k-anonymity Privacy Protecting Model

作　　者：刘玉静[1] 刘国华[1] 李捷元 肖瑞[1] 

机构地区：[1]东华大学计算机学院,上海201620

出　　处：《计算机与数字工程》2013年第11期1779-1783,1865,共6页Computer & Digital Engineering

基　　金：国家自然科学基金(编号:61070032)资助

摘　　要：查询是一种重要的数据库操作。在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.

关 键 词：不确定性数据 K-匿名 可能世界 数据模型 查询 数据复杂度 

分 类 号：TP319[自动化与计算机技术—计算机软件与理论]