Consequence-Based Reasoning for Description Logics with Disjunctions and Number Restrictions

Andrew Bate, Boris Motik, Bernardo Cuenca Grau, David Tena Cucala, Frantisek Simancik, Ian Horrocks

Authors: Andrew Bate, Boris Motik, Bernardo Cuenca Grau, David Tena Cucala, František Simančík, Ian Horrocks
Affiliation: Department of Computer Science, University of Oxford

Introduction

In the field of Knowledge Representation, Description Logics (DLs) serve as the formal foundation for the Semantic Web and critical large-scale ontologies such as SNOMED CT. A primary challenge in this domain is "classification"—the process of computing the complete hierarchy of concepts within an ontology. Historically, this task has been dominated by tableau-based and resolution-based reasoning. While tableau methods are goal-directed, they often suffer from redundancy; resolution methods are powerful but can generate excessive irrelevant inferences.

Consequence-based (CB) reasoning emerged as a hybrid approach, combining the goal-directed nature of tableau with the efficiency of resolution. However, a significant limitation persisted: CB reasoners could not simultaneously handle disjunctions (OR statements) and number restrictions (cardinality constraints). This paper introduces a novel CB reasoning algorithm and its implementation, Sequoia, which bridges this gap for the logic $\mathcal{ALCHIQ}^+$.

Methodology

The authors propose a new calculus that integrates three core technical innovations to handle the computational complexity of combined disjunctions and number restrictions:

  1. Context Structures: Inferences are organized into a graph of "contexts," each representing a specific segment of a potential model. By localizing inferences to specific contexts or their immediate neighbors, the algorithm prevents the reasoner from exploring irrelevant logical branches.
  2. First-Order Clause Encoding: Logical consequences are represented as restricted first-order clauses. This allows the application of advanced automated theorem-proving techniques within the DL framework.
  3. Ordered Paramodulation: To manage number restrictions efficiently, the authors adapted paramodulation—a standard technique for reasoning with equality. This allows Sequoia to determine when two entities must be identical without resorting to exhaustive guessing.

Structural Transformation

A critical step in the methodology is the normalization of complex DL axioms into a simplified clausal form. This pre-processing ensures that the core reasoning engine remains efficient while maintaining the ability to compute the full concept hierarchy.

Normalization rules for transforming DL axioms into clausal form.

Sequoia also employs a "pay-as-you-go" strategy, ensuring that for simpler ontologies (such as those in the $\mathcal{EL}$ profile), the algorithm automatically scales down to run in polynomial time.

Evaluation and Results

The performance of Sequoia was evaluated using a massive corpus of 703 ontologies from the Oxford Ontology Repository, ranging from simple medical ontologies to complex structures.

Key Findings

  • Robustness and Speed: Sequoia successfully classified 610 out of 703 ontologies in under 10 seconds. It consistently outperformed established tableau reasoners like FaCT++, Pellet, and HermiT.
  • Competitive Edge: While the reasoner Konclude remains the overall speed leader, Sequoia proved its worth by successfully processing 8 complex ontologies where HermiT, Pellet, and FaCT++ all failed.
  • Efficiency on Simple Logic: On the $\mathcal{EL}$ version of SNOMED CT, Sequoia matched the performance of specialized tools like ELK and Snorocket. This confirms that the added expressive power does not penalize performance on simpler, large-scale tasks.

Conclusion and Future Work

Sequoia represents a major milestone in automated reasoning, proving that consequence-based methods can scale to highly expressive logics. However, some limitations remain. The current implementation does not yet support nominals (specific individuals) or datatypes, which are necessary for full OWL 2 DL compliance. Additionally, very large cardinality restrictions and complex interactions in specific ontologies (like the "Pizza" ontology) continue to pose optimization challenges. Future work will focus on extending the framework to ABox reasoning (instance data) and further optimizing equality handling.

Summary updated

Abstract

Classification of description logic (DL) ontologies is a key computational problem in modern data management applications, so considerable effort has been devoted to the development and optimisation of practical reasoning calculi. Consequence-based calculi combine ideas from hypertableau and resolution in a way that has proved very effective in practice. However, existing consequence-based calculi can handle either Horn DLs (which do not support disjunction) or DLs without number restrictions. In this paper, we overcome this important limitation and present the first consequence-based calculus for deciding concept subsumption in the DL ALCHIQ+. Our calculus runs in exponential time assuming unary coding of numbers, and on ELH ontologies it runs in polynomial time. The extension to disjunctions and number restrictions is technically involved: we capture the relevant consequences using first-order clauses, and our inference rules adapt paramodulation techniques from first-order theorem proving. By using a well-known preprocessing step, the calculus can also decide concept subsumptions in SRIQ---a rich DL that covers all features of OWL 2 DL apart from nominals and datatypes. We have implemented our calculus in a new reasoner called Sequoia. We present the architecture of our reasoner and discuss several novel and important implementation techniques such as clause indexing and redundancy elimination. Finally, we present the results of an extensive performance evaluation, which revealed Sequoia to be competitive with existing reasoners. Thus, the calculus and the techniques we present in this paper provide an important addition to the repertoire of practical implementation techniques for description logic reasoning.
BibTeX
@article{bate2018consequence,
  author = {Andrew Bate and Boris Motik and Bernardo Cuenca Grau and David Tena Cucala and Frantisek Simancik and Ian Horrocks},
  title = {{Consequence-Based Reasoning for Description Logics with Disjunctions and Number Restrictions}},
  journal = {J. Artif. Intell. Res.},
  year = {2018},
  doi = {10.1613/jair.1.11257},
}
Figure