Efficient Query Rewriting in the Description Logic EL and Beyond

Peter Hansen, Carsten Lutz, Inanç Seylan, Frank Wolter

Abstract

Ontology-Based Data Access (OBDA) relies on efficient query rewriting to bridge high-level conceptual models with relational databases. However, for the $\mathcal{EL}$ family of description logics—widely used in healthcare and biology—finite First-Order (FO) rewritings are not guaranteed to exist. This paper introduces a novel "decomposed" algorithm that translates complex ontology-based queries into efficient, non-recursive Datalog programs. By breaking down query structures into reusable node pairs, the proposed method provides a solution that is both theoretically complete and practically fast enough to handle massive real-world ontologies.

Introduction

The challenge of query rewriting in $\mathcal{EL}$ logics stems from the potential for non-existence of finite FO-rewritings. Previous approaches often suffered from being incomplete, producing impractical Unions of Conjunctive Queries (UCQs) that degrade database performance, or failing to terminate on complex inputs. This research addresses these issues by proposing a decomposition-based approach that targets non-recursive monadic Datalog, which modern database optimizers handle far more efficiently than large UCQs.

The Decomposed Algorithm

The core of the proposed solution is a three-phase algorithm:

  1. Decomposition: Instead of constructing a massive tree-shaped query, the algorithm decomposes the query into "node pairs." This facilitates structure sharing, ensuring that common query components are computed only once.
  2. Annotation & Cycle Checking: Node pairs are enriched with logical consequences to detect "root cycles." The presence of such cycles allows the algorithm to definitively identify queries that are not FO-rewritable.
  3. Datalog Construction: If no root cycles are detected, the node pairs are reassembled into a non-recursive monadic Datalog program. This format acts as a set of temporary views, offering a succinct and performant alternative to flat SQL queries.

Experimental Evaluation

The algorithm, implemented in a system called Grind, was evaluated against seven real-world ontologies known for their complexity, including ENVO, FBbi, MOHSE, NBO, not-galen, SO, and XP. These datasets contain cycles and complex role restrictions that typically challenge rewriting tools.

Performance metrics and ontology statistics for the evaluated TBoxes.

As shown in the table above, the ontologies vary significantly in size (CI and CN counts). The system demonstrated high termination rates, successfully processing 98.8% of nearly 11,000 test cases within a 30-second timeout.

Results and Discussion

The experimental results highlight several key advantages of the decomposed algorithm:

  • Practical Rewritability: While theoretical guarantees are lacking for $\mathcal{EL}$, the study found that queries are almost always FO-rewritable in practice. Only 74 out of 10,989 test cases were non-rewritable.
  • Efficiency and Speed: The algorithm is remarkably fast, with many queries processed in under 0.5 seconds. Even for the most complex ontologies like not-galen, the system provided definitive answers where previous tools might fail.
  • Succinctness of Rewritings: A major benefit of targeting Datalog is the compact nature of the output. Most generated rewritings were small; for instance, in the NBO ontology, 55% of rewritings consisted of a single rule.
Distribution of the number of rules in generated rewritings across different ontologies.

As illustrated in the figure above, the vast majority of concept names across all ontologies require very few rules (typically 1 or 2) for their rewriting, demonstrating the succinctness of the Datalog approach.

Conclusion and Future Work

This work demonstrates that efficient and complete query rewriting for $\mathcal{EL}$ ontologies is achievable through decomposition and Datalog targeting. Future research will focus on extending this framework to full Conjunctive Queries (CQs) and more expressive logics, such as $\mathcal{ELHI}$, which includes inverse roles. While the worst-case complexity remains a theoretical challenge, the practical performance of the Grind system marks a significant step forward for OBDA in complex domains.

Summary updated

Abstract

We propose a new type of algorithm for computing first-order (FO) rewritings of concept queries under ELHdr-TBoxes. The algorithm is tailored towards efficient implementation, yet complete. It outputs a succinct non-recursive datalog rewriting if the input is FO-rewritable and otherwise reports non-FO-rewritability. We carry out experiments with realworld ontologies which demonstrate excellent performance in practice and show that TBoxes originating from applications admit FO-rewritings of reasonable size in almost all cases, even when in theory such rewritings are not guaranteed to exist.
BibTeX
@inproceedings{hansen2015efficient,
  author = {Peter Hansen and Carsten Lutz and Inanç Seylan and Frank Wolter},
  title = {{Efficient Query Rewriting in the Description Logic EL and Beyond}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure