AAAI Publications, Twenty-Ninth AAAI Conference on Artificial Intelligence

Font Size: 
From Classical to Consistent Query Answering under Existential Rules
Thomas Lukasiewicz, Maria Vanina Martinez, Andreas Pieris, Gerardo I Simari

Last modified: 2015-02-18

Abstract


Querying inconsistent ontologies is an intriguing new problem that gave rise to a flourishing research activity in the description logic (DL) community. The computational complexity of consistent query answering under the main DLs is rather well understood; however, little is known about existential rules. The goal of the current work is to perform an in-depth analysis of the complexity of consistent query answering under the main decidable classes of existential rules enriched with negative constraints. Our investigation focuses on one of the most prominent inconsistency-tolerant semantics, namely, the AR semantics. We establish a generic complexity result, which demonstrates the tight connection between classical and consistent query answering. This result allows us to obtain in a uniform way a relatively complete picture of the complexity of our problem.

Keywords


Inconsistency; Consistent query answering; Conjunctive queries; Existential rules; Tuple-generating dependencies; Computational complexity

Full Text: PDF