Introduction
In the field of Knowledge Representation, there is a fundamental trade-off between the expressivity of a logic and its computational scalability. Description Logics (DLs) like Horn-SRIQ offer high expressivity, allowing for complex definitions such as role chains, which are vital for domains like biology and medicine. However, reasoning over large-scale datasets (ABoxes) with such expressive ontologies often becomes a bottleneck. This paper presents a novel, data-independent transformation that bridges this gap by converting Horn-SRIQ ontologies into Datalog programs, enabling the use of high-performance Datalog engines for efficient assertion retrieval.
The Challenge of Assertion Retrieval in Horn-SRIQ
Assertion Retrieval (AR) involves inferring all implicit facts from a Knowledge Base. While simple DLs are well-supported, Horn-SRIQ introduces complexities, particularly through role chains. A role chain allows defining a relationship based on a sequence of others (e.g., "the brother of my father is my uncle"). Reasoning with these is difficult because it often necessitates considering "anonymous individuals"—objects whose existence is implied by the logic but which are not explicitly named in the data.
Previous techniques could handle simpler logics like Horn-SHIQ, but the inclusion of role chains in Horn-SRIQ remained a significant hurdle for data-intensive applications.
Methodology: NFA Encoding and Datalog Rewriting
The authors' approach is centered on a data-independent transformation. This means the complex logical analysis of the ontology (the TBox) is performed once, independent of the actual data. The result is a set of Datalog rules that can be applied to any ABox.
NFA Encoding of Role Chains
To handle the paths created by complex role chains, the authors utilize Non-Deterministic Finite Automata (NFAs). These automata "track" how relationships propagate through the model, allowing the system to handle complex sequences of properties efficiently.
Saturation and Rewriting
The transformation involves a specialized saturation calculus that pre-computes inferences involving anonymous individuals. By leveraging the "Forest-Model" property—the fact that Horn-SRIQ models can be viewed as trees rooted at individuals—the authors can capture the necessary logic using a finite set of Datalog predicates. This process is proven to be worst-case optimal and complete, ensuring that all valid inferences are captured without adding unnecessary complexity.
Experimental Evaluation
The proposed method was evaluated using real-world biological ontologies, Reactome and Uniprot, and a large corpus from MOWLCorp. The Datalog programs were executed using the RDFox engine and compared against Konclude, a state-of-the-art DL reasoner.
Performance and Scalability
The results demonstrate a significant performance advantage for the Datalog-based approach, especially as the size of the dataset increases.
As shown in the figure, the Datalog rewriting approach (black bars) consistently outperforms Konclude (orange bars). In the largest Uniprot samples, Konclude timed out after an hour, whereas the Datalog-based reasoning finished in mere seconds. Furthermore, the size of the generated Datalog programs remained manageable; for 74% of the ontologies tested, the resulting program was less than three times the size of the original ontology.
Conclusion and Future Work
This research provides a practical pathway for applying expressive Horn-SRIQ ontologies to massive datasets. By transforming complex logic into optimized Datalog rules, the authors enable high-performance reasoning that was previously unattainable for such expressive languages. While the method faces potential "state-space explosion" for ontologies with extremely complex role chains, it remains highly effective for the vast majority of real-world knowledge bases. Future work will focus on extending this technique to even more expressive logics and further optimizing the rule generation process.
Summary updated