中文摘要：

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