Effective Query Rewriting with Ontologies over DBoxes

Inanç Seylan, Enrico Franconi, Jos de BruijnIJCAI 2009

Introduction

In the field of Semantic Web and knowledge representation, Description Logics (DLs) serve as the formal foundation for ontologies. However, a significant practical challenge remains: the mismatch between the "open-world" assumptions of DLs and the "closed-world" reality of relational databases. This paper addresses this gap by introducing DBoxes, a formal mechanism that allows specific ontology predicates to be treated as complete database tables. By leveraging logic-based interpolation, the authors provide a method to rewrite complex ontological queries into standard SQL-like expressions.

The Open World vs. Closed World Mismatch

Traditionally, Description Logics utilize an ABox (Assertion Box) to store instance data. ABoxes operate under the Open World Assumption (OWA): if a specific fact is not present in the ABox, it is considered unknown rather than false. This is fundamentally at odds with relational databases, which operate under the Closed World Assumption (CWA): if a tuple is not in a table, it is assumed not to exist.

This discrepancy complicates the use of ontologies as conceptual views over existing databases. To query a database through an ontology, one must ensure that the answers are strictly determined by the available data and then translate (or rewrite) those queries into a language the database engine can execute.

Methodology: DBoxes and Interpolation

The authors propose the DBox as a hybrid structure where the extensions of certain predicates are "closed" and exactly defined by the underlying data. To facilitate query rewriting in this environment, the research relies on two core logical principles:

  1. Beth Definability: This theorem posits that if a concept is implicitly defined by a set of predicates (i.e., its instances are uniquely determined by them), then an explicit logical formula for that concept must exist.
  2. Craig Interpolation: This provides the constructive method for finding that explicit formula. Given a logical implication $A \to B$, an interpolant is a formula $C$ such that $A \to C$ and $C \to B$, using only the vocabulary shared by $A$ and $B$.

The Tableau-Based Algorithm

The primary contribution of the paper is a constructive, tableau-based algorithm for the Description Logic $\mathcal{ALC}$. While tableau algorithms are typically used to check for logical satisfiability, the authors "adorn" the process to extract an interpolant during the proof. This allows the system to take a query and an ontology and generate a rewritten query that can be executed directly on a relational database.

To ensure practical viability, the authors integrate the algorithm with industry-standard tableau optimizations, including:

  • Backjumping: To prune the search space during satisfiability checks.
  • Lazy Unfolding: To handle large terminologies efficiently.
  • Semantic Branching: To improve the efficiency of the search process.

Key Insights and Results

Definability Equivalence

The authors prove that for $\mathcal{ALC}$ with DBoxes, implicit definability and explicit definability are equivalent. This is a crucial theoretical result: it guarantees that if a query can be answered by the database, a valid rewriting must exist and can be found by their algorithm.

Complexity Considerations

While DBoxes bridge the gap between OWA and CWA, they introduce computational overhead. The paper notes a "complexity shift": in simpler logics like DL-lite, moving from an ABox to a DBox can increase data complexity from LOGSPACE to coNP-hard. This suggests that while the method is powerful, it requires careful implementation to remain performant.

Handling Indefinability with Abduction

In cases where a query cannot be rewritten because the ontology lacks sufficient links to the database predicates, the authors suggest using abduction. This form of logical inference seeks the simplest additional axioms required to make the query definable, effectively providing a roadmap for how to "fix" or extend the ontology to support the desired queries.

Limitations and Future Directions

The current framework is limited to the logic $\mathcal{ALC}$. It does not yet support several common features of more expressive languages like OWL, such as:

  • Inverse Roles: These allow information to flow "backwards" through the logical tableau, which complicates the inductive construction of interpolants.
  • Number Restrictions: Constraints such as "has at least 3 children" are not yet handled by the rewriting procedure.
  • Conjunctive Queries: The current work focuses on "concept queries." Extending the interpolation method to handle complex joins and multiple variables remains a significant area for future research.

Conclusion

By framing query rewriting as a problem of Craig Interpolation over DBoxes, this paper provides a rigorous path for using rich ontologies to query standard relational data. While expressive limitations remain, the sound and complete tableau-based algorithm offers a foundation for building more effective semantic data access layers.

Summary updated

BibTeX
@inproceedings{seylan2009effective,
  author = {Inanç Seylan and Enrico Franconi and Jos de Bruijn},
  title = {{Effective Query Rewriting with Ontologies over DBoxes}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2009},
}
Figure