Abstract
Levesque’s proper knowledge bases (proper KBs) correspond to infinite sets of ground positive and negative facts, with the notable property that for FOL formulas in a certain normal form, which includes conjunctive queries and positive queries possibly extended with a controlled form of negation, entailment reduces to formula evaluation. However proper KBs represent extensional knowledge only. In description logic terms, they correspond to ABoxes. In this paper, we augment them with DL-Lite TBoxes, expressing intensional knowledge (i.e., the ontology of the domain). DL-Lite has the notable property that conjunctive query answering over TBoxes and standard description logic ABoxes is reducible to formula evaluation over the ABox only. Here, we investigate whether such a property extends to ABoxes consisting of proper KBs. Specifically, we consider two DL-Lite variants: \(\textit{DL-Lite}_{ rdfs }\), roughly corresponding to RDFS, and \(\textit{DL-Lite}_{ core }\), roughly corresponding to OWL 2 QL. We show that when a \(\textit{DL-Lite}_{ rdfs }\) TBox is coupled with a proper KB, the TBox can be compiled away, reducing query answering to evaluation on the proper KB alone. But this reduction is no longer possible when we associate proper KBs with \(\textit{DL-Lite}_{ core }\) TBoxes. Indeed, we show that in the latter case, query answering even for conjunctive queries becomes coNP-hard in data complexity.
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
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison Wesley (1995)
Allemang, D., Hendler, J.: Semantic Web for the Working Ontologist: Effective Modeling in RDFS and OWL. Morgan Kaufmann (2008)
Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P.F. (eds.): The Description Logic Handbook: Theory, Implementation and Applications. Cambridge University Press (2003)
Baader, F., Brandt, S., Lutz, C.: Pushing the \({\cal EL}\) envelope, pp. 364–369 (2005)
Baier, C., Katoen, J.P.: Principles of model checking. MIT Press (2008)
Berardi, D., Calvanese, D., De Giacomo, G.: Reasoning on UML class diagrams. Artif. Intell. 168(1–2), 70–118 (2005)
Brachman, R., Levesque, H.: Knowledge Representation and Reasoning. Morgan Kaufmann (2004)
Brickley, D., Guha, R., McBride, B.: RDF Schema 1.1. W3C Recommendation. World Wide Web Consortium, February 2014. http://www.w3.org/TR/rdf-schema/
Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. Autom. Reasoning 39(3), 385–429 (2007)
Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Data complexity of query answering in description logics. Artif. Intell. 195, 335–360 (2013)
Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R., Ruzzi, M.: Using OWL in data integration. In: Semantic Web Information Management - A Model-Based Perspective, pp. 397–424. Springer (2009)
De Giacomo, G., Lespérance, Y., Levesque, H.J.: Efficient reasoning in proper knowledge bases with unknown individuals. In: Proc. of IJCAI 2011, pp. 827–832 (2011)
Donini, F.M., Lenzerini, M., Nardi, D., Schaerf, A.: Deduction in concept languages: from subsumption to instance checking. J. of Logic and Computation 4(4), 423–452 (1994)
Franconi, E., Gutierrez, C., Mosca, A., Pirrò, G., Rosati, R.: The logic of extensional RDFS. In: Alani, H., et al. (eds.) ISWC 2013, Part I. LNCS, vol. 8218, pp. 101–116. Springer, Heidelberg (2013)
Lenzerini, M.: Data integration: a theoretical perspective. In: Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 3–5, Madison, Wisconsin, USA, pp. 233–246 (2002)
Lenzerini, M.: Ontology-based data management. In: Proceedings of the 6th Alberto Mendelzon International Workshop on Foundations of Data Management, Ouro Preto, Brazil, June 27–30, pp. 12–15 (2012)
Levesque, H.J.: A completeness result for reasoning with incomplete first-order knowledge bases. In: KR, pp. 14–23 (1998)
Liu, Y.: Tractable Reasonng in Incomplete First-Order Knowledge Bases. Ph.D. thesis, Department of Computer Science, University of Toronto (2006)
Liu, Y., Levesque, H.J.: A tractability result for reasoning with incomplete first-order knowledge bases. In: IJCAI, pp. 83–88 (2003)
W3C: OWL 2 web ontology language primer, 2nd edn. Tech. rep., W3C Recommendation, December 11, 2012
W3C: SPARQL 1.1 overview. Tech. rep., W3C Recommendation March 21, 2013
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
De Giacomo, G., Levesque, H. (2015). Adding DL-Lite TBoxes to Proper Knowledge Bases. In: Arenas, M., et al. The Semantic Web - ISWC 2015. ISWC 2015. Lecture Notes in Computer Science(), vol 9366. Springer, Cham. https://doi.org/10.1007/978-3-319-25007-6_18
Download citation
DOI: https://doi.org/10.1007/978-3-319-25007-6_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-25006-9
Online ISBN: 978-3-319-25007-6
eBook Packages: Computer ScienceComputer Science (R0)