Extending Decidable Existential Rules by Joining Acyclicity and Guardedness

Krötzsch, Markus; Rudolph, Sebastian

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

Extending Decidable Existential Rules by Joining Acyclicity and Guardedness

Markus Krötzsch, Sebastian Rudolph

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 963-967.

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

Abstract

Existential rules, i.e. Datalog extended with existential quantifiers in rule heads, are currently studied under a variety of names such as Datalog +/-, ∀∃-rules, and tuple-generating dependencies. The renewed interest in this formalism is fuelled by a wealth of recently discovered language fragments for which query answering is decidable. This paper extends and consolidates two of the main approaches in this field — acyclicity and guardedness — by providing (1) complexity-preserving generalisations of weakly acyclic and weakly (frontier-)guarded rules, and (2) a novel formalism of glut-(frontier-)guarded rules that subsumes both. This builds on an insight that acyclicity can be used to extend any existential rule language while retaining decidability. Besides decidability, combined query complexities are established in all cases.

Markus Krötzsch, and Sebastian Rudolph. 2011. Extending Decidable Existential Rules by Joining Acyclicity and Guardedness. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 963–967. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-166

@inproceedings{ijcai2011p166,
  title     = {Extending Decidable Existential Rules by Joining Acyclicity and Guardedness},
  author    = {Krötzsch, Markus and Rudolph, Sebastian},
  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     = {963--967},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-166},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-166},
}

TY  - CPAPER
TI  - Extending Decidable Existential Rules by Joining Acyclicity and Guardedness
AU  - Krötzsch, Markus
AU  - Rudolph, Sebastian
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  - 963
EP  - 967
DO  - 10.5591/978-1-57735-516-8/IJCAI11-166
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-166
ER  -