Computing Horn Rewritings of Description Logics Ontologies

Mark Kaminski, Bernardo Cuenca Grau

Introduction

In Knowledge Representation and the Semantic Web, ontologies (such as those defined in OWL 2) serve as the schema for structured data. A persistent challenge in this field is the trade-off between expressivity and computational performance. While standard Description Logics (DLs) allow for disjunction (e.g., "Every student is either an Undergraduate or a Graduate"), this feature makes reasoning co-NP-hard relative to data size. Conversely, Horn DLs, which forbid disjunction, allow for polynomial-time reasoning but limit modeling flexibility.

This research addresses the "Horn rewritability" problem: determining if a complex ontology $\mathcal{O}_1$ can be transformed into a Horn ontology $\mathcal{O}_2$ that maintains query equivalence across any dataset. Such a transformation would enable developers to model with disjunction while deploying with high-performance Horn reasoners.

Methodology

The authors propose a practical framework based on three technical pillars:

  1. Undecidability Analysis: The paper proves that for many common logic fragments (e.g., $\mathcal{ALCF}$), it is undecidable whether a general ontology has a Horn rewriting.
  2. Markability and Transposition: To circumvent undecidability, the authors introduce "markability," a sufficient condition derived from Datalog. If an ontology is markable, its rules can be "transposed"—shuffling atoms between the antecedent and consequent and introducing fresh predicates to eliminate disjunction.
  3. The $\xi$-Translation: A novel translation method ($\xi$) is introduced to convert DL axioms into rules using functional terms for existential restrictions. This encoding facilitates the identification of valid markings and the subsequent translation back into standard DL syntax.
The complete workflow from a non-Horn ontology to a Horn DL rewriting through rule translation, transposition, and final rewriting.

Key Insights

A significant finding is that checking for markability can be reduced to a 2-SAT problem, allowing the identification of rewritable ontologies in linear time. Furthermore, the method is "language-preserving"; for instance, an $\mathcal{ALC}$ ontology is rewritten into a Horn-$\mathcal{ALC}$ ontology, ensuring compatibility with existing DL reasoners. The authors also highlight that treating existential successors as unary functional terms during intermediate steps is crucial for focusing the marking process on simpler unary predicates.

Experimental Evaluation

The approach was evaluated on a corpus of 120 non-Horn ontologies from sources including the Protege Ontology Library, BioPortal, the Oxford Ontology Repository, and the EBI linked data platform (e.g., ChEMBL and BioPAX Reactome).

Key Results: * Practicality: Approximately 27% (32 out of 120) of the tested ontologies were found to be markable, including complex real-world examples. * Efficiency: For these 32 ontologies, the resulting Horn rewritings are polynomial in size, avoiding the exponential explosion common in logic transformations. * Complexity: The data complexity for checking satisfiability in markable ontologies drops to PTIME-complete, confirming the expected performance gains.

Limitations and Future Work

As markability is a sufficient but not necessary condition, some rewritable ontologies may be missed. Additionally, in a small subset of cases (3 out of 32), the marking required binary predicates (roles), which hindered the final translation back to standard DL syntax. Future research will focus on relaxing markability conditions and empirically measuring performance improvements across various reasoners like HermiT or Konclude.

Summary updated

BibTeX
@inproceedings{kaminski2015computing,
  author = {Mark Kaminski and Bernardo Cuenca Grau},
  title = {{Computing Horn Rewritings of Description Logics Ontologies}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=BkZKZQG_br},
}
Figure