Introduction
In database theory, Ontology-Based Query Answering (OBQA) extends standard querying by incorporating logical rules (an ontology) that describe relationships within the data. A classic challenge in this field is "query rewriting": transforming a query and its associated rules into a single, standard SQL query. Historically, this process often led to an "exponential explosion" in query size, making it impractical for large-scale systems. This paper addresses this by proving that for "linear existential rules," rewritings can be kept to a polynomial size.
The Challenge of Exponential Explosion
Linear existential rules are a flexible class of logic that can handle "unknown" values—for instance, a rule stating "Every person has a parent" without specifying who that parent is. When these rules are "unfolded" into a query, the number of possible logical paths typically grows exponentially. This paper investigates whether these rules can be rewritten into First-Order (FO) queries or non-recursive Datalog that only grow polynomially relative to the original query size.
Methodology: Proof Generators and Binary Encoding
The core of the authors' approach is the Proof Generator. Instead of unfolding every logical path, they formalize the process of finding a proof as a reachability problem on a "chase graph."
To achieve polynomial size, the authors employ several key techniques:
- Database Compilation: The database is slightly modified with auxiliary constants (bits
0and1and astarsymbol) to allow the query to encode and decode "labeled nulls" (unknown values) using binary strings. - Logical Shortcuts: The authors define a series of shortcuts to handle null values and domain constraints without repeating complex sub-formulas, which is essential for maintaining polynomial bounds.
- Divide and Conquer Reachability: Similar to the logic in Savitch’s Theorem, the query "guesses" proof structures and verifies them using a recursive-like structure that stays within polynomial limits.
Key Results
The paper establishes several significant bounds:
- Linear Existential Rules (LIN): These are proven to be polynomially combined rewritable. By slightly modifying the database, the resulting query remains small.
- Full Linear Rules (FLIN): Rules without existential variables are polynomially purely rewritable, meaning no database modification is required.
- DLR-LiteR Support: The results confirm that DLR-LiteR, a logic widely used in Semantic Web applications, is polynomially combined rewritable.
Conclusion and Future Work
This research solves long-standing open questions by showing that the structural simplicity of linear rules—where proof paths form a "forest" rather than complex branching trees—allows for efficient rewriting. While these results are currently theoretical, they provide a roadmap for implementing more efficient OBQA systems. Future work will involve testing these polynomial rewritings against real-world SQL optimizers to determine if the theoretical size bounds translate into practical performance gains.
Summary updated