First Order Rewritability in Ontology-Mediated Querying in Horn Description Logics

David Toman, Grant E. WeddellAAAI 2022 · DOI

Introduction

Ontology-Mediated Querying (OMQ) has emerged as a powerful paradigm for accessing data by enriching traditional database schemas with domain knowledge expressed through ontologies. In this setup, a Knowledge Base (KB) consists of an "ABox" (the data) and a "TBox" (the ontology). A central challenge in OMQ is the efficient evaluation of queries, as ontologies often imply facts not explicitly present in the ABox. While Datalog programs can be used to "complete" the data, the most desirable outcome is First-Order (FO) rewritability: the ability to transform a query and its associated ontology into a single SQL query executable by standard relational database management systems.

The Challenge of FO Rewritability

FO rewritability is the "holy grail" of OMQ because it allows for the seamless integration of ontologies with existing database infrastructure without the need for specialized reasoning engines. However, achieving this is non-trivial. For many expressive Description Logics (DLs), query answering is inherently recursive, which falls outside the scope of standard FO logic. This research addresses two fundamental questions:

  1. Decidability: Given an ontology, can we determine if a specific query (or all possible queries) can be rewritten into FO logic?
  2. Synthesis: If a rewriting exists, how can it be algorithmically constructed?

Bridging Description Logics and Classical Logic

The authors propose a framework that bridges the gap between the Datalog-based reasoning common in DLs and classical First-Order logic. This is achieved through three primary theoretical pillars.

Clark’s Completion

The first step involves representing the ontology's rules as a Datalog program $\Pi_{\mathcal{T}}$. To analyze this program using classical logic, the authors apply Clark’s completion. This process transforms the "if" rules of Datalog into "if and only if" formulas, effectively "closing" the definitions of concepts and roles. This transformation allows the application of powerful theorems from classical logic that are typically not applicable to open-world reasoning or recursive Datalog.

Mapping Horn DL axioms to completion rules in the Datalog program $\Pi_{\mathcal{T}}$.

As shown in the figure above, standard DL axioms such as concept intersections, value restrictions, and role inclusions are systematically mapped to completion rules. This mapping provides a formal basis for the subsequent logic-based analysis.

Beth Definability and Craig Interpolation

Once the logic is "closed" via Clark's completion, the authors utilize Beth’s Definability Theorem (1953). This theorem provides a criterion to check if a concept (e.g., "Manager") can be uniquely defined using only the base symbols available in the data source. If a concept is Beth definable over the completion, an FO rewriting is guaranteed to exist.

To actually synthesize the rewriting, the framework employs Craig Interpolation. An interpolant acts as a "middle-ground" formula that captures the necessary logic using only the allowed vocabulary of the data source. This provides a constructive method for generating the final SQL-like query.

Advanced Features and Constraints

A significant contribution of this work is its ability to handle more complex DL features and real-world database environments.

Handling Existential Restrictions

In more expressive Horn logics like Horn-$SHIQ$, the ontology may contain existential restrictions (e.g., "Every employee must have a manager"). The framework handles these by introducing Skolem functions into the completion rules, as illustrated below.

Completion rules for existential restrictions using Skolem functions.

Integration of Database Constraints

The research also highlights that FO rewritability is often a property of the entire system, including database integrity constraints like foreign keys. The authors demonstrate that certain ontologies that appear non-rewritable in isolation become rewritable when the underlying database's structural constraints are taken into account. These constraints can "simplify" the required reasoning, making FO rewriting feasible.

Key Results and Complexity

The authors establish that determining the existence of FO rewritability for the completion of an ABox and uniform query rewritability is decidable. Specifically, for expressive logics like Horn-$SHIQ$ and Horn-$DLFD$, this problem falls within the EXPTIME complexity class.

Furthermore, the framework is constructive. By using automated theorem provers capable of generating interpolants, the authors provide a practical algorithmic path to synthesize rewritings. This approach also unifies previous work, showing that it naturally encompasses simpler, industry-standard families like DL-Lite, where it produces "perfect rewritings."

Conclusion and Future Work

While this framework provides a robust theoretical foundation for FO rewritability in Horn DLs, some challenges remain. The reliance on the "unique minimal model" property limits its application to non-Horn logics, where disjunctions make rewritability significantly harder to achieve. Additionally, the synthesized FO formulas can become quite large, potentially impacting performance in very large databases. Future research will explore the use of non-First-Order interpolants, such as the $\mu$-calculus, to handle cases where standard FO rewriting is impossible, and aim to optimize the efficiency of the synthesis process.

Summary updated

BibTeX
@inproceedings{toman2022first,
  author = {David Toman and Grant E. Weddell},
  title = {{First Order Rewritability in Ontology-Mediated Querying in Horn Description Logics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i5.20534},
}
Figure