On The Querying Of Uncertain Data In The K-anonymity Privacy Protecting Model

In the rapid development of network information technology today, people enjoy the convenient and efficient of publishing and accessing information, at the same time, also bear the risk of leaking privacy. Common means of protection of privacy may probe the secret use of data transformation, in order to reduce the risk of loss of privacy. K-anonymity privacy model is a common model of privacy protection, satisfing the requirements of the data is more and more on the Internet.Modeling is the basic for data management of uncertainty. The specificity in the uncertainty of the data in the k-anonymity privacy protection model is found, namely, its uncertainty is caused by human with generalization, the probability that each instance after generalization is reduced to the original tuple is equal. Because of this specificity, the past modeling approaches of uncertainty data are not suitable for this kind of uncertainty data simply.It is a very important operation to query on databases. Each tuple in the κ-anonymity privacy protection model contains not only the accurate data, but also the generalized data, so the κ-anonymous data is a kind of uncertain data. In order to discuss the querying problem of κ-anonymous data, first we proposed a κ-anonymous data model based on the possible world, and then define the querying problems as membership, possibility, Certainty, containment, and finally we investigate the data-complexity of these querying problems, and show that membership is in PTIME, q-Membership is in NP-complete, q’-Containment is in NP-complete, q-Containment is in coNP-complete, Possibility is in PTIME,q-Possibility is in NP-complete. These conclusions lay a theoretical foundation for the study of the querying of uncertain data in the κ-anonymity privacy protecting model.