 |
    |
Complexity of Inconsistency-Tolerant Query Answering in Datalog+/–
Thomas Lukasiewicz, Maria Vanina Martinez, and Gerardo I. Simari
Department of Computer Science, University of Oxford, UKthomas.lukasiewicz@cs.ox.ac.uk
vanina.martinez@cs.ox.ac.uk
gerardo.simari@cs.ox.ac.uk
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.
LNCS 8185, p. 488 ff.
lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2013