Portal de Periódicos da CAPES

On rules with existential variables: Walking the decidability line

2011; Elsevier BV; Volume: 175; Issue: 9-10 Linguagem: Inglês

10.1016/j.artint.2011.03.002

1872-7921

Jean-François Baget, Michel Leclère, Marie-Laure Mugnier, Êric Salvat,

Advanced Database Systems and Queries

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 ∀∃-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 ∀∃-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.