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