Polynomial Rewritings for Linear Existential Rules

Georg Gottlob, Marco Manna, Andreas PierisIJCAI 2015

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."

Visualization of a proof structure (chase graph) for linear existential rules, showing how rules generate new atoms and how a query matches them.

To achieve polynomial size, the authors employ several key techniques:

  1. Database Compilation: The database is slightly modified with auxiliary constants (bits 0 and 1 and a star symbol) to allow the query to encode and decode "labeled nulls" (unknown values) using binary strings.
  2. 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.
Logical shortcuts and definitions used to construct the polynomial-sized rewritings.
  1. 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

BibTeX
@inproceedings{gottlob2015polynomial,
  author = {Georg Gottlob and Marco Manna and Andreas Pieris},
  title = {{Polynomial Rewritings for Linear Existential Rules}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure