Abstract
Consequence-based (CB) reasoning has proven highly effective for Horn Description Logics (DLs), but extending these techniques to more expressive logics like $SRIQ$—which include concept disjunctions and counting quantifiers—has been a long-standing challenge. This paper introduces the first CB algorithm for $SRIQ$, utilizing a novel contextual graph structure and integrating ordered paramodulation to handle equality constraints. Our prototype implementation, Sequoia, demonstrates that this approach is not only theoretically sound but also practically superior to many state-of-the-art tableau-based reasoners on complex real-world ontologies.
Introduction
In Knowledge Representation, a fundamental trade-off exists between the expressiveness of a logic and the efficiency of its reasoning algorithms. For expressive Description Logics (DLs), tableau-based reasoning has long been the standard. However, these methods often suffer from "state explosion" when dealing with large, complex ontologies, as they attempt to construct exhaustive models of the data.
Consequence-based (CB) reasoning offers a more efficient alternative by deriving logical consequences directly in a goal-directed manner. Until now, CB techniques were largely restricted to simpler Horn logics. They struggled with the combination of disjunctions ($A \sqcup B$) and counting quantifiers (e.g., "at most $n$"), which create intricate equality constraints. This work bridges that gap, presenting a robust CB framework for the expressive logic $SRIQ$.
A Consequence-Based Calculus for SRIQ
The core of the proposed approach is a novel calculus that adapts high-performance theorem-proving techniques to the DL context. The algorithm transforms DL axioms into a specific clausal form, as illustrated in the general translation rules shown in Figure 3.
Key technical innovations include:
- Contextual Graph Structure: Reasoning is organized into a directed graph of "contexts," which localizes derivations and prevents the generation of irrelevant facts.
- Context Clauses: By introducing variables for the current node ($x$) and its predecessor ($y$), the calculus captures constraints across different parts of the ontology without the full overhead of first-order logic.
- Ordered Paramodulation: To handle the equality constraints arising from counting quantifiers, the authors integrate ordered paramodulation—a technique from automated theorem proving—directly into the CB framework.
An example of this reasoning process within the contextual graph is shown in Figure 4, demonstrating how clauses are derived and propagated between nodes.
Experimental Evaluation
The authors evaluated their prototype, Sequoia, using a corpus of 777 ontologies from the Oxford Ontology Repository. To ensure a fair comparison, nominals and datatypes (which Sequoia does not yet support) were pre-processed into fresh classes and properties.
Sequoia was compared against established reasoners including HermiT, Pellet, FaCT++, and Konclude. The results were compelling:
- Performance: Sequoia processed 733 out of 784 ontologies in under 10 seconds, significantly outperforming HermiT, Pellet, and FaCT++.
- Robustness: Sequoia successfully reasoned over 21 "hard" ontologies that caused other reasoners to time out or crash. Notably, it was the only system to complete the task on a particularly challenging version of the Foundational Model of Anatomy (FMA) ontology.
- Scalability: The system's performance was found to be comparable to Konclude, the current state-of-the-art for these logics.
Discussion and Future Work
A key insight of this work is that treating the predecessor of a node as a named variable allows for efficient equality reasoning using standard resolution techniques. Furthermore, the calculus is "worst-case optimal," ensuring it remains within the EXPTIME complexity bounds of $SRIQ$ and avoiding the unpredictable performance "hangs" common in tableau reasoners.
While a major step forward, the current version of Sequoia does not yet support nominals, reflexive roles, or datatypes. Adding nominals increases theoretical complexity to NEXPTIME, which would likely require a non-deterministic version of the calculus. Future work will also focus on optimizing equality reasoning for ontologies with very large cardinality restrictions.
Summary updated