Abstract
Existential rules (also known as Datalog± or tuple-generating dependencies) have been intensively studied in recent years as a prominent formalism in knowledge representation and database systems. We consider them here as a querying formalism, extending classical Datalog, the language of deductive databases. It is well known that the classes of databases recognized by (Boolean) existential rule queries are closed under homomorphisms. Also, due to the existence of a semi-decision procedure (the chase), these database classes are recursively enumerable. We show that, conversely, every homomorphism-closed recursively enumerable query can be expressed as an existential rule query, thus arriving at a precise characterization of existential rules by model-theoretic and computational properties. Although the result is very intuitive, the proof turns out to be non-trivial. This result can be seen as a very expressive counterpart of the prominent Lyndon-Łos-Tarski-Theorem characterizing the homomorphism-closed fragment of first-order logic. Notably, our result does not presume the existence of any additional built-in structure on the queried data, such as a linear order on the domain, which is a typical requirement for other characterizations in the spirit of descriptive complexity.
Introduction
In the fields of database theory and knowledge representation, existential rules (Datalog±) are a popular framework for describing relationships and inferring new data. Prior to this work, researchers identified two defining characteristics of these queries:
- Homomorphism Closure: If a query is satisfied by a database, it remains satisfied if more facts are added or if the data is mapped to a larger structure.
- Semi-Decidability: There exists a semi-decision procedure (the "chase") that will eventually confirm if a query is true, though it may run indefinitely if the query is false.
The central challenge addressed in this paper is the converse: Is every query that satisfies these two properties expressible as an existential rule? Proving this is difficult because existential rules lack the standard tools—negation and a built-in linear order—typically required to simulate a Turing Machine (TM) on a database.
Methods
The authors utilize a constructive proof, demonstrating how to build a set of existential rules that simulate a TM recognizing a specific query. The core challenge lies in simulating computation without a predefined order or the ability to check for the absence of facts.
The List Annotator and D-lists
Because the logic cannot assume a linear order, the authors developed rules to generate all possible sequences, or "D-lists," of domain elements. While many of these sequences may be repetitive or disorganized, the logic ensures that at least one proper order is explored.
Database Guessing and Exceptional Acceptance
To overcome the lack of negation, the rules "guess" every possible database configuration. If a guessed configuration is inconsistent with the actual input (e.g., the input contains a fact that the guess claims is missing), the simulation uses a trick called "exceptional acceptance." This ensures the simulation only fails if the TM rejects a configuration that truly matches the input.
Singularization
The proof leverages "singularization" to show that even if the generated orders are repetitive, the homomorphism-closure property ensures that the TM's acceptance on a collapsed version of the data implies the query is true for the original data.
Key Results and Insights
The primary result of this work is a definitive characterization of the expressivity of existential rules:
Theorem 1: A query is expressible with existential rules if and only if its set of satisfying databases is recursively enumerable and closed under homomorphisms.
This establishes existential rules as a "complete" language for this semantic class. It serves as a high-powered counterpart to the Lyndon-Łos-Tarski Theorem from first-order logic, but extended to the realm of semi-decidable queries. Notably, this result is order-independent; unlike many characterizations in descriptive complexity, it proves the logic is powerful enough to "invent" its own internal structures to perform computation.
Limitations and Future Work
While the paper proves the theoretical possibility of such expressions, the construction used is a "brute force" simulation. The resulting existential rules would be massive and computationally inefficient for practical use. Future research aims to find similar capturing results for lower complexity classes (like P, NP, or PSPACE) by applying syntactic restrictions to the rules. Additionally, bridging the gap for simpler versions like Datalog, which cannot capture all polynomial-time homomorphism-closed queries, remains an open challenge.
Summary updated