Walking the Complexity Lines for Generalized Guarded Existential Rules

Baget, Jean-François; Mugnier, Marie-Laure; Rudolph, Sebastian; Thomazo, Michael

doi:10.5591/978-1-57735-516-8/IJCAI11-126

Walking the Complexity Lines for Generalized Guarded Existential Rules

Jean-François Baget, Marie-Laure Mugnier, Sebastian Rudolph, Michaël Thomazo

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 712-716.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-126

Abstract

We establish complexities of the conjunctive query entailment problem for classes of existential rules (i.e. Tuple-Generating Dependencies or Datalog+/- rules). Our contribution is twofold. First, we introduce the class of greedy bounded treewidth sets (gbts), which covers guarded rules, and their known generalizations, namely (weakly) frontier-guarded rules. We provide a generic algorithm for query entailment with gbts, which is worst-case optimal for combined complexity with bounded predicate arity, as well as for data complexity. Second, we classify several gbts classes, whose complexity was unknown, namely frontier-one, frontier-guarded and weakly frontier-guarded rules, with respect to combined complexity (with bounded and unbounded predicate arity) and data complexity.

Jean-François Baget, Marie-Laure Mugnier, Sebastian Rudolph, and Michael Thomazo. 2011. Walking the Complexity Lines for Generalized Guarded Existential Rules. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 712–716. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-126

@inproceedings{ijcai2011p126,
  title     = {Walking the Complexity Lines for Generalized Guarded Existential Rules},
  author    = {Baget, Jean-François and Mugnier, Marie-Laure and Rudolph, Sebastian and Thomazo, Michael},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {712--716},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-126},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-126},
}

TY  - CPAPER
TI  - Walking the Complexity Lines for Generalized Guarded Existential Rules
AU  - Baget, Jean-François
AU  - Mugnier, Marie-Laure
AU  - Rudolph, Sebastian
AU  - Thomazo, Michael
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 712
EP  - 716
DO  - 10.5591/978-1-57735-516-8/IJCAI11-126
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-126
ER  -