Extending Decidable Existential Rules by Joining Acyclicity and Guardedness

Markus KrötzschMarkus Krötzsch, Sebastian RudolphSebastian Rudolph

Download

Markus Krötzsch, Sebastian Rudolph
Extending Decidable Existential Rules by Joining Acyclicity and Guardedness
In Toby Walsh, eds., Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), 963-968, July 2011. IJCAI/AAAI

Details
Bibtex

KurzfassungAbstract
Existential rules, i.e. Datalog extended with existential quantifiers in rule heads, are currently studied under a variety of names such as Datalog+/–, \exists\forall-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.
Bemerkung: Note: Additional proofs for this work can be found in the technical report Revisiting Acyclicity and Guardedness Criteria for Decidability of Existential Rules.
Forschungsgruppe:Research Group: Computational LogicComputational Logic, Wissensbasierte SystemeKnowledge-Based Systems

@inproceedings{KR2011,
  author    = {Markus Kr{\"{o}}tzsch and Sebastian Rudolph},
  title     = {Extending Decidable Existential Rules by Joining Acyclicity and
               Guardedness},
  editor    = {Toby Walsh},
  booktitle = {Proceedings of the 22nd International Joint Conference on
               Artificial Intelligence (IJCAI 2011)},
  publisher = {IJCAI/AAAI},
  year      = {2011},
  month     = {July},
  pages     = {963-968}
}