Skip to main content

From Classical to Consistent Query Answering under Existential Rules

Thomas Lukasiewicz‚ Maria Vanina Martinez‚ Andreas Pieris and Gerardo I. Simari


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.

Book Title
Proceedings of the 29th National Conference on Artificial Intelligence‚ AAAI 2015‚ Austin‚ Texas‚ USA‚ January 25−29‚ 2015
Blai Bonet and Sven Koenig
AAAI Press