On rules with existential variables: Walking the decidability line
By Jean-François Baget, Michel Leclère, Marie-Laure Mugnier, Eric Salvat. Artificial Intelligence, 2011
358 citations recorded by the source corpus.
We consider positive rules in which the conclusion may contain existentially quantified variables, which makes reasoning tasks (such as conjunctive query answering or entailment) undecidable. These rules, called @[email protected]?-rules, have the same logical form as tuple-generating dependencies in databases and as conceptual graph rules. The aim of this paper is to provide a clearer picture of the frontier between decidability and non-decidability of reasoning with these rules. Previous known decidable classes were based on forward chaining. On the one hand we extend these classes, on the other hand we introduce decidable classes based on backward chaining. A side result is the definition of a backward mechanism that takes the complex structure of @[email protected]?-rule conclusions into account. We classify all known decidable classes by inclusion. Then, we study the question of whether the union of two decidable classes remains decidable and show that the answer is negative, except for one class and a still open case. This highlights the interest of studying interactions between rules. We give a constructive definition of dependencies between rules and widen the landscape of decidable classes with conditions on rule dependencies and a mixed forward/backward chaining mechanism. Finally, we integrate rules with equality and negative constraints to our framework.
Subfields: Artificial Intelligence, Computer Networks and Communications
View Paper: https://www.semanticscholar.org/paper/530a5b51c42d616a8f255b2330dac67e8f3452c6
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Georg Gottlob
- Thomas Lukasiewicz
- Andrea Calì
- Ana Marasovic
- Sarah Wiegreffe
- Oana-Maria Camburu
- Chenhao Tan
In Computer Networks and Communications
Citations in the corpus
- A general datalog-based framework for tractable query answering over ontologies (2009, background): “guarded and of frontier-guarded TGDs [13, 84].”