k-匿名隐私保护模型中不确定性数据的查询问题
刘玉静
刘国华
李捷元
肖瑞
1.东华大学计算机学院 上海2016202.东华大学计算机学院 上海2016203.东华大学计算机学院 上海2016204.东华大学计算机学院 上海201620
摘要：查询是一种重要的数据库操作.在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-匿名隐私保护模型中不确定性数据查询方法的研究奠定了理论基础.
关键词：不确定性数据k-匿名可能世界数据模型查询数据复杂度
分类号：TP319(计算技术、计算机技术)
资助基金：国家自然科学基金(61070032)
论文发表日期：2013-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：6( 1779-1783,1865 )
英文信息