From Horn-SRIQ to Datalog: A Data-Independent Transformation That Preserves Assertion Entailment

David Carral, Larry González, Patrick KoopmannAAAI 2019 · DOI

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.

NFA representation of role chains used in the transformation process.

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.

Performance comparison (time in seconds, log scale) between the proposed Datalog rewriting (black) and Konclude (orange) on Reactome and Uniprot datasets.

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

BibTeX
@inproceedings{carral2019from,
  author = {David Carral and Larry González and Patrick Koopmann},
  title = {{From Horn-SRIQ to Datalog: A Data-Independent Transformation That Preserves Assertion Entailment}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33012736},
}
Figure