Complexity of Inconsistency-Tolerant Query Answering in Datalog+/– under Cardinality-Based Repairs

Authors

  • Thomas Lukasiewicz University of Oxford
  • Enrico Malizia University of Exeter
  • Andrius Vaicenavičius University of Oxford

DOI:

https://doi.org/10.1609/aaai.v33i01.33012962

Abstract

Querying inconsistent ontological knowledge bases is an important problem in practice, for which several inconsistencytolerant query answering semantics have been proposed, including query answering relative to all repairs, relative to the intersection of repairs, and relative to the intersection of closed repairs. In these semantics, one assumes that the input database is erroneous, and the notion of repair describes a maximally consistent subset of the input database, where different notions of maximality (such as subset and cardinality maximality) are considered. In this paper, we give a precise picture of the computational complexity of inconsistencytolerant (Boolean conjunctive) query answering in a wide range of Datalog± languages under the cardinality-based versions of the above three repair semantics.

Downloads

Published

2019-07-17

How to Cite

Lukasiewicz, T., Malizia, E., & Vaicenavičius, A. (2019). Complexity of Inconsistency-Tolerant Query Answering in Datalog+/– under Cardinality-Based Repairs. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 2962-2969. https://doi.org/10.1609/aaai.v33i01.33012962

Issue

Section

AAAI Technical Track: Knowledge Representation and Reasoning