The Impact of Disjunction on Query Answering Under Guarded-Based Existential Rules

Pierre Bourhis, Michael Morak, Andreas Pieris

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study the complexity of conjunctive query answering under (weakly-)(frontier-)guarded disjunctive existential rules, i.e., existential rules extended with disjunction, and their main subclasses, linear rules and inclusion dependencies (IDs). Our main result states that conjunctive query answering under a fixed set of disjunctive IDs is 2EXPTIME-hard. This quite surprising result together with a 2EXPTIME upper bound for weakly-frontier-guarded disjunctive rules, obtained by exploiting recent results on guarded negation first-order logic, gives us a complete picture of the computational complexity of our problem. We also consider a natural subclass of disjunctive IDs, namely frontier-one (only one variable is propagated), for which the combined complexity decreases to EXPTIME. Finally, we show that frontier-guarded rules, combined with negative constraints, are strictly more expressive than DL-LiteHbool, one of the most expressive languages of the DL-Lite family. We also show that query answering under this DL is 2EXPTIME-complete in combined complexity.
Original languageEnglish
Title of host publicationIJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013
PublisherThe AAAI Press
Pages796-802
Number of pages7
Publication statusPublished - 2013

Fingerprint Dive into the research topics of 'The Impact of Disjunction on Query Answering Under Guarded-Based Existential Rules'. Together they form a unique fingerprint.

Cite this