Terminological Reasoning in SHIQ with Ordered Binary Decision Diagrams

Sebastian Rudolph, Markus Krötzsch, Pascal HitzlerAAAI 2008

Abstract

Automated reasoning is a cornerstone of the Semantic Web, yet scaling these processes for complex ontologies remains a significant challenge. This paper presents a pioneering approach that adapts Ordered Binary Decision Diagrams (OBDDs)—a data structure widely used in hardware and software verification—to perform terminological reasoning for the description logic $SHIQ$. By transforming logical axioms into Boolean functions and employing a fixed-point iteration over "domino" interpretations, the authors establish a sound and complete symbolic reasoning framework.

Introduction

The effectiveness of the Semantic Web depends on the ability to efficiently check the consistency of ontologies defined in the Web Ontology Language (OWL). At its core, OWL is powered by Description Logics (DLs), specifically the $SHIQ$ fragment. Traditional reasoning engines, such as Pellet or RacerPro, primarily utilize tableau-based algorithms. While robust, these methods often encounter scalability bottlenecks as ontologies grow in size and complexity. This paper explores an alternative paradigm: symbolic reasoning via OBDDs, which have demonstrated the capacity to handle state spaces as large as $10^{20}$ in formal verification domains.

The $SHIQ$ Logic

$SHIQ$ provides a rich set of constructors for defining concepts and roles. These include inverse roles, qualified number restrictions, and general concept inclusions (GCIs) within a Terminological Box (TBox).

Syntax and semantics of SHIQ constructs.

The complexity of $SHIQ$ makes it difficult to map directly to the Boolean logic required by OBDDs. The authors address this by first reducing $SHIQ$ to a simpler logic, $ALCIb$, which preserves satisfiability while flattening complex expressions.

Methodology

The proposed reasoning pipeline consists of several innovative steps:

  1. Logic Reduction: A $SHIQ$ knowledge base is transformed into $ALCIb$ in polynomial time. This involves eliminating transitivity and complex number restrictions by introducing equivalent structures.
  2. Domino Interpretations: To represent models symbolically, the authors introduce "dominoes"—local snapshots of a model representing two individuals and their relationships. A set of dominoes is consistent if it can be tiled to form a valid model.
  3. Boolean Encoding: These sets of dominoes are encoded as Boolean functions. Each concept and role is mapped to a Boolean variable, allowing the entire set of possible interpretations to be manipulated as a single OBDD.
  4. Fixed-Point Iteration: The algorithm employs a "top-down" pruning strategy. Starting with the set of all possible dominoes, it iteratively removes those that violate logical constraints using standard OBDD operations. The process terminates when a fixed point is reached; if the resulting set is non-empty, the ontology is satisfiable.

Key Contributions

The primary contribution of this work is the first sound and complete algorithm for $SHIQ$ reasoning with general TBoxes using OBDDs. Unlike previous attempts that were limited to simpler logics like $ALC$, this approach supports the full expressivity of $SHIQ$. The shift from search-based tree construction to symbolic function manipulation offers a new theoretical foundation for high-performance DL reasoners.

Limitations and Future Work

While the theoretical framework is sound, several areas remain for future development. The current algorithm focuses on TBox (terminological) reasoning and does not yet support ABox (assertional) data regarding specific individuals. Furthermore, the logic $SHIQ$ excludes nominals, which are necessary for the more expressive $SHOIQ$. Finally, the practical performance of the algorithm depends heavily on Boolean variable ordering, an NP-complete problem that requires sophisticated heuristics for real-world application.

Conclusion

By bridging the gap between Description Logics and formal verification techniques, this paper opens a promising avenue for scalable Semantic Web reasoning. The use of OBDDs provides a powerful mechanism for managing the complexity of modern ontologies, setting the stage for a new generation of symbolic reasoners.

Summary updated

BibTeX
@inproceedings{rudolph2008terminological,
  author = {Sebastian Rudolph and Markus Krötzsch and Pascal Hitzler},
  title = {{Terminological Reasoning in SHIQ with Ordered Binary Decision Diagrams}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure