Skip to main content

Complexity of Inconsistency−Tolerant Query Answering in Datalog+⁄−

Thomas Lukasiewicz‚ Maria Vanina Martinez and Gerardo I. Simari

Abstract

The study of inconsistency-tolerant semantics for query answering in ontological languages has recently gained much attention. In this work, we consider three inconsistency-tolerant semantics recently proposed in the literature, namely: consistent query answering, the intersection (also called IAR) semantics, and the intersection of closed repairs (ICR) semantics. We study the data complexity of conjunctive query answering under these semantics for a wide set of tractable fragments of Datalog+⁄−. The Datalog+⁄− family of ontology languages covers several important description logics (DLs), bridging the gap in expressive power between database query languages and DLs as ontology languages, and extending the well-known Datalog language in order to embed DLs. Its properties of decidability of query answering and of tractability of query answering in the (data) complexity make Datalog+⁄− very useful in modeling real-world applications in which inconsistency-tolerant reasoning is essential.

Book Title
Proceedings of the 12th International Conference on Ontologies‚ Databases‚ and Applications of Semantics‚ ODBASE 2013‚ Graz‚ Austria‚ September 10−11‚ 2013
Editor
Robert Meersman‚ Hervé Panetto‚ Tharam Dillon‚ Johann Eder‚ Zohra Bellahsene‚ Norbert Ritter‚ Pieter De Leenheer and Deijing Dou
Pages
488−500
Publisher
Springer
Series
Lecture Notes in Computer Science
Volume
8185
Year
2013