Abstract
Information systems support data privacy by granting access only to certain (public) views. The data privacy problem is to decide whether hidden (private) information may be inferred from the public views and some additional general background knowledge. We study the problem of provable privacy in the context of \(\mathcal{ALC}\) knowledge bases. First we show that the \(\mathcal{ALC}\) privacy problem wrt. concept retrieval and subsumption queries is ExpTime-complete. Then we provide a sufficient condition for data privacy that can be checked in PTime.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F. (eds.): The Description Logic Handbook. Cambridge University Press, Cambridge (2003)
Smith, M.K., Welty, C., McGuinness, D.L.: OWL web ontology language guide (2004), http://www.w3.org/TR/owl-guide/
Stoffel, K., Studer, T.: Provable data privacy. In: Viborg, K., Debenham, J., Wagner, R. (eds.) DEXA 2005. LNCS, vol. 3588, pp. 324–332. Springer, Heidelberg (2005)
Stouppa, P., Studer, T.: A formal model of data privacy. In: Virbitskaite, I., Voronkov, A. (eds.) PSI 2006. LNCS, vol. 4378, pp. 401–411. Springer, Heidelberg (2007)
Stouppa, P., Studer, T.: Data privacy for \(\mathcal{ALC}\), Technical Report, IAM 08-002 (2008), http://www.iam.unibe.ch/publikationen/techreports/2008/
Fagin, R., Kolaitis, P.G., Miller, R., Popa, L.: Data exchange: Semantics and query answering. Theoretical Computer Science 336, 89–124 (2005)
Hofmann, M.: Proof-theoretic approach to description-logic. In: LICS 2005, pp. 229–237. IEEE Computer Society, Los Alamitos (2005)
van der Meyden, R.: Logical approaches to incomplete information: a survey. In: Logics for databases and information systems, pp. 307–356. Kluwer, Dordrecht (1998)
Calì, A., Calvanese, D., Giacomo, G.D., Lenzerini, M.: Data integration under integrity constraints. In: Pidduck, A.B., Mylopoulos, J., Woo, C.C., Ozsu, M.T. (eds.) CAiSE 2002. LNCS, vol. 2348, pp. 262–279. Springer, Heidelberg (2002)
Halevy, A.Y.: Answering queries using views: A survey. The VLDB Journal 10(4), 270–294 (2001)
Arenas, M., Libkin, L.: XML data exchange: Consistency and query answering. In: PODS, pp. 13–24 (2005)
Nash, A., Deutsch, A.: Privacy in glav information integration. In: Schwentick, T., Suciu, D. (eds.) ICDT 2007. LNCS, vol. 4353, pp. 89–103. Springer, Heidelberg (2006)
Biskup, J., Weibert, T.: Keeping secrets in incomplete databases. Journal of Information Security 7(3), 199–217 (2008)
Miklau, G., Suciu, D.: A formal analysis of information disclosure in data exchange. In: SIGMOD, pp. 575–586. ACM, New York (2004)
Deutsch, A., Papakonstantinou, Y.: Privacy in database publishing. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol. 3363, pp. 230–245. Springer, Heidelberg (2004)
Machanavajjhala, A., Gehrke, J.: On the efficiency of checking perfect privacy. In: PODS 2006, pp. 163–172. ACM Press, New York (2006)
Dalvi, N.N., Miklau, G., Suciu, D.: Asymptotic conditional probabilities for conjunctive queries. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol. 3363, pp. 289–305. Springer, Heidelberg (2004)
Martin, D.J., Kifer, D., Machanavajjhala, A., Gehrke, J., Halpern, J.Y.: Worst-case background knowledge in privacy. In: ICDE, pp. 126–135. IEEE, Los Alamitos (2007)
Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R.: View-based query answering over description logic ontologies. In: Principles of Knowledge Representation and Reasoning, pp. 242–251 (2008)
Grau, B.C., Horrocks, I.: Privacy-preserving query answering in logic-based information systems. In: 18th European Conference on Artificial Intelligence (ECAI 2008) (to appear, 2008)
Horrocks, I., Patel-Schneider, P., van Harmelen, F.: From SHIQ and RDF to OWL: The making of a web ontology language. Journal of Web Semantics 1(1) (2003)
Calvanese, D., Lenzerini, M.: Answering queries using views over description logics knowledge bases. In: Proceedings of AAAI 2000, pp. 386–391 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Stouppa, P., Studer, T. (2008). Data Privacy for \(\mathcal{ALC}\) Knowledge Bases. In: Artemov, S., Nerode, A. (eds) Logical Foundations of Computer Science. LFCS 2009. Lecture Notes in Computer Science, vol 5407. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92687-0_28
Download citation
DOI: https://doi.org/10.1007/978-3-540-92687-0_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-92686-3
Online ISBN: 978-3-540-92687-0
eBook Packages: Computer ScienceComputer Science (R0)