Revisiting Acyclicity and Guardedness Criteria for Decidability of Existential Rules
Markus Krötzsch, Sebastian Rudolph
Revisiting Acyclicity and Guardedness Criteria for Decidability of Existential Rules
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.
Published at Karlsruhe Institute of Technology (Technical report)
Download PDF (last update: Jan 30 2011)
Citation details
- Markus Krötzsch, Sebastian Rudolph. Revisiting Acyclicity and Guardedness Criteria for Decidability of Existential Rules. In Institute AIFB Technical Report 3011. Karlsruhe Institute of TechnologyProperty "Publisher" has a restricted application area and cannot be used as annotation property by a user. 2011.
author = {Markus Kr{\"o}tzsch and Sebastian Rudolph},
title = {Revisiting Acyclicity and Guardedness Criteria
for Decidability of Existential Rules},
year = {2011},
number = {3011},
institution = {Institute AIFB, Karlsruhe Institute of
Technology},
note = {Available online at
\url{http://www.aifb.kit.edu/web/Techreport3011}}
}
Remarks
The results from this work have been published in the paper Extending Decidable Existential Rules by Joining Acyclicity and Guardedness at IJCAI 2011.
