Extending decidable existential rules by joining acyclicity and guardedness
Markus Krötzsch, Sebastian Rudolph · 2011
Existential rules, i.e. Datalog extended with exis-tential quantifiers in rule heads, are currently stud-ied 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 frag-ments for which query answering is decidable. This paper extends and consolidates two of the main approaches in this field – acyclicity and guard-edness – by providing (1) complexity-preserving generalisations of weakly acyclic and weakly (frontier-)guarded rules, and (2) a novel formal-ism 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. 1