Existential Rules

Origin. The rules are the tuple-generating dependencies of 1970s database theory, and the chase that saturates them comes from Maier, Mendelzon and Sagiv, "Testing Implications of Data Dependencies" (ACM TODS 4(4): 455–469, 1979), and Aho, Beeri and Ullman, "The Theory of Joins in Relational Databases" (ACM TODS 4(3): 297–314, 1979). Beeri and Vardi, "The implication problem for data dependencies" (ICALP 1981), and Chandra, Lewis and Makowsky (STOC 1981) proved the associated inference problems undecidable. The rereading as an ontology language came in three bodies of work: data exchange (Fagin, Kolaitis, Miller and Popa, "Data exchange: semantics and query answering", Theoretical Computer Science 336(1): 89–124, 2005), the Datalog± programme (Calì, Gottlob and Lukasiewicz, "A general Datalog-based framework for tractable query answering over ontologies", PODS 2009; Calì, Gottlob, Lukasiewicz, Marnette and Pieris, LICS 2010), and the ∀∃-rules of the graph-based tradition (Baget, Leclère and Mugnier, "Walking the decidability line for rules with existential variables", KR 2010).

Models. Rules of the form ∀x∀y(φ(x,y) → ∃z ψ(x,z)) read as an ontology over a database: the body matched against known facts, the head inventing new individuals. Value invention is the whole difference from Datalog, which is exactly the existential-free fragment, and it is what an ontology needs — "every person has a parent" speaks about individuals the data does not name. Reasoning is certain-answer: a Boolean conjunctive query is entailed when it holds in every model of the data and the rules, and the chase builds the model that decides this, a universal model that maps homomorphically into every model. Against the description logics: existential rules allow predicates of any arity and arbitrary conjunctive bodies, where ALC and its relatives stay at arity two with the tree model property. DL-Lite translates into linear rules with negative constraints and keys (Calì, Gottlob and Lukasiewicz 2009), and EL and ELI ontologies rewrite as guarded rules over unary and binary predicates.

Formalism.

Rules: σ: ∀x∀y(φ(x,y) → ∃z ψ(x,z)); φ the body, ψ the head, conjunctions of atoms. Frontier: the variables x shared by body and head. Full (existential-free) rules = Datalog.

Certain answers: cert(q, Σ, D): the answers to q holding in every model of the database D and the rule set Σ. BCQ entailment: D, Σ ⊨ q — the decision problem of the subject.

Chase: Apply rules to D, inventing fresh nulls for existential variables, to a fixpoint. The result is a universal model: D, Σ ⊨ q iff chase(D, Σ) ⊨ q. The chase need not terminate; termination is undecidable.

Undecidability: BCQ entailment for unrestricted rule sets is undecidable (Beeri and Vardi 1981; Chandra, Lewis and Makowsky 1981).

Three decidability paradigms (Baget, Leclère and Mugnier 2010): fes — finite expansion sets: the chase terminates. bts — bounded treewidth sets: the chase may be infinite but has bounded treewidth, and decidability follows from the bounded-treewidth model property (Courcelle 1990). fus — finite unification sets: backward chaining terminates; the query rewrites into a finite union of conjunctive queries. None of the three abstract classes is recognizable: membership is undecidable.

Weakly acyclic sets (fes; Fagin, Kolaitis, Miller and Popa 2005): Position graph over predicate positions, with special edges for existential positions; weakly acyclic iff no cycle passes through a special edge. The chase then terminates in polynomially many steps in the data: certain answers in polynomial time, PTIME-complete in data complexity (hardness from Datalog).

Guarded sets (bts; Calì, Gottlob and Kifer, KR 2008; JAIR 48: 115–174, 2013): Some body atom — the guard — contains every body variable. Linear rules: a single body atom; include the inclusion dependencies. Weakly guarded: only the affected variables need a guard. BCQ entailment, guarded: 2EXPTIME-complete; EXPTIME-complete for bounded arity; PTIME-complete in data complexity. Linear: PSPACE-complete; NP-complete for bounded arity (Johnson and Klug 1984 for inclusion dependencies); first-order rewritable, so data complexity in AC⁰. Weakly guarded: EXPTIME-complete already in data complexity.

Frontier-guarded sets (bts; Baget, Mugnier, Rudolph and Thomazo, IJCAI 2011): The guard need cover only the frontier; frontier-one restricts the frontier to a single variable. Both: 2EXPTIME-complete combined, with or without an arity bound; PTIME-complete in data complexity.

Sticky sets (fus; Calì, Gottlob and Pieris, PVLDB 3: 554–565, 2010; Artificial Intelligence 193: 87–128, 2012): A marking procedure flags body variables whose values can be lost in the head; sticky iff no marked variable occurs twice in a body — join values always propagate ("stick") to the inferred atoms. Neither chase termination nor bounded treewidth; decidability through rewriting: UCQ-rewritable, data complexity in AC⁰. Combined: EXPTIME-complete; NP-complete for bounded arity.

Datalog±: The program name for the family (Calì, Gottlob and Lukasiewicz 2009): Datalog plus existential heads (also negative constraints and keys), minus whatever syntax must go to keep entailment decidable — the fragments above are its dialects.

Symbols.

Metatheory. The chase is the subject's one tool and its one hazard. Its result is a universal model, so certain-answer entailment reduces to evaluation over a single — generally infinite — structure; every decidable class is a theorem about how much of that structure a conjunctive query can see. Entailment for unrestricted rule sets is undecidable (Beeri and Vardi 1981), and so is chase termination, and so is membership in each of the abstract classes fes, bts and fus (Baget, Leclère and Mugnier 2010) — the concrete classes are, by contrast, syntactically checkable. The verified landscape: guarded rules are 2EXPTIME-complete in combined complexity, EXPTIME-complete at bounded arity and PTIME-complete in the data (Calì, Gottlob and Kifer 2008/2013); frontier-guarded and frontier-one rules are 2EXPTIME-complete at any arity and PTIME-complete in the data, by the greedy bounded-treewidth algorithm of Baget, Mugnier, Rudolph and Thomazo (2011); weakening the guard to affected variables raises data complexity to EXPTIME-complete; linear rules are PSPACE-complete, sticky rules EXPTIME-complete, both NP-complete at bounded arity, and both first-order rewritable — the query plus the rules compile into a union of conjunctive queries evaluated on the raw data, placing data complexity in AC⁰ as for DL-Lite. Weak acyclicity makes the chase polynomial in the data (Fagin, Kolaitis, Miller and Popa 2005), the foundation of data exchange, where the chase result is the materialized target instance itself.

Applies to. Ontology-based data access and ontology-mediated query answering. Data exchange and data integration, where source-to-target TGDs are the mapping language. Datalog± knowledge bases and rule engines over relational data. Capturing description logics — DL-Lite in linear rules, EL and ELI in guarded rules — inside one relational formalism. Reasoning over knowledge graphs with predicates of arbitrary arity.

Limitations. Everything usable is a fragment: unrestricted rules are undecidable, so each class surrenders something — weak acyclicity forbids the recursion through existentials that ontological axioms like "every person has a parent, who is a person" require, guardedness forbids unguarded joins, stickiness forbids reusing a join value that a head can drop. The abstract classes that explain why these work are not recognizable, so no procedure decides whether an arbitrary rule set is safe. The language is positive and monotone: no negation, no disjunction in heads, and adding either revives undecidability except under separate restrictions; equality-generating dependencies interact with TGDs so badly that even guarded sets keep decidability only under additional conditions on the EGDs (Calì, Gottlob and Kifer 2013). First-order rewritability caps a class's expressiveness at AC⁰ data complexity — no transitive closure, no genuine recursion — and the rewritings themselves can be exponentially large in the query, so the cost excluded from data complexity reappears in the SQL shipped to the database, exactly as recorded for DL-Lite. The combined complexities are severe throughout: nothing in the family evaluates faster than NP, and the guarded classes require doubly exponential time.

© 2026 Lingenic LLC