Complexity of Approximate Query Answering under Inconsistency in Datalog+/-
Complexity of Approximate Query Answering under Inconsistency in Datalog+/-
Thomas Lukasiewicz, Enrico Malizia, Cristian Molinaro
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1921-1927.
https://doi.org/10.24963/ijcai.2018/265
Several semantics have been proposed to query inconsistent ontological knowledge bases, including the intersection of repairs and the intersection of closed repairs as two approximate inconsistency-tolerant semantics. In this paper, we analyze the complexity of conjunctive query answering under these two semantics for a wide range of Datalog+/- languages. We consider both the standard setting, where errors may only be in the database, and the generalized setting, where also the rules of a Datalog+/- knowledge base may be erroneous.
Keywords:
Knowledge Representation and Reasoning: Computational Complexity of Reasoning
Knowledge Representation and Reasoning: Description Logics and Ontologies