A Description Logic with Transitive and Converse Roles and Role Hierarchies

Ulrike Sattler, Ian Horrocks1998 · DOI

Abstract Transitive roles are essential for the adequate representation of aggregated objects, allowing for descriptions of parts without specifying decomposition levels. While the Description Logic (DL) $\mathcal{ALCHR}_+$ supports transitive roles and role hierarchies, it lacks the ability to describe parts in terms of the whole (and vice versa) due to the absence of inverse roles. This paper presents $\mathcal{ALCIHR}_+$, which extends $\mathcal{ALCHR}_+$ with inverse roles. We provide a sound and complete tableaux-based decision procedure for $\mathcal{ALCIHR}_+$ that avoids the "cut rule" often required for transitive closure, offering a more computationally efficient approach to reasoning in complex part-whole hierarchies.

1. Introduction

In knowledge representation, modeling "aggregated objects"—complex entities composed of various parts—is a fundamental requirement. A key logical property needed for this is transitivity: if a component $A$ is part of $B$, and $B$ is part of $C$, then $A$ is logically part of $C$.

Earlier formalisms like $\mathcal{ALCHR}_+$ could handle transitivity in a single direction (e.g., "has part"). However, practical applications often require bidirectional reasoning. For instance, one might need to describe a "Whole" based on its "Parts" using a "has part" role, while simultaneously describing a "Part" in relation to its "Whole" using an "is part of" role. To address this, the authors introduce $\mathcal{ALCIHR}_+$, integrating inverse roles into a framework that already supports transitive roles and role hierarchies.

2. The $\mathcal{ALCIHR}_+$ Logic

The authors define the syntax and semantics of $\mathcal{ALCIHR}_+$, extending the basic $\mathcal{ALC}$ logic with three powerful features:

  • Transitive Roles ($\mathcal{R}_+$): Roles $R$ where $xRy$ and $yRz$ implies $xRz$.
  • Inverse Roles ($\mathcal{I}$): For every role $R$, there exists an inverse role $R^-$ such that $xRy$ if and only if $yR^-x$.
  • Role Hierarchies ($\mathcal{H}$): The ability to define subsumption relationships between roles (e.g., $R \sqsubseteq S$).

A significant design choice was the use of transitive roles rather than a general "transitive closure" operator. While both lead to the same complexity class (EXPTIME-hard), transitive roles can be implemented more efficiently in practice.

3. The Tableaux Algorithm

The core contribution of the paper is a sound and complete tableaux algorithm for checking the satisfiability of $\mathcal{ALCIHR}_+$ concepts. The algorithm works by attempting to construct a tree-like model that satisfies the given logical constraints.

3.1 Avoiding the Cut Rule

Previous approaches to logics with transitive closure and inverse roles often relied on a "cut rule" in their proof systems. The cut rule is notorious for causing poor algorithmic performance because it introduces non-deterministic choices that explode the search space. The authors' algorithm for $\mathcal{ALCIHR}_+$ avoids this rule by carefully designing expansion rules—specifically the $\forall_+$-rule—to handle the interaction between transitivity and inverses.

3.2 Ensuring Termination: Blocking

To prevent the algorithm from creating infinite branches (e.g., an infinite chain of "parts of parts"), the authors employ a blocking technique. If the algorithm encounters a new node in the model that is "covered" by an existing ancestor node (i.e., it has the same set of logical constraints), it stops expanding that branch.

4. Key Results and Implications

The paper establishes several critical theoretical results:

  • Decidability: Satisfiability and subsumption problems in $\mathcal{ALCIHR}_+$ are shown to be decidable.
  • Internalization: The authors demonstrate that General Concept Inclusions (GCIs) can be internalized using a universal role, allowing the reasoner to handle global constraints within a single satisfiability check.
  • Practicality: By avoiding the cut rule and focusing on transitive roles over closure, the algorithm is better suited for "average-case" performance in real-world knowledge engineering tasks.

5. Conclusion

$\mathcal{ALCIHR}_+$ represents a significant milestone in the evolution of Description Logics. By providing a formal framework and a well-behaved algorithm for bidirectional transitive hierarchies, it laid the groundwork for subsequent logics like $\mathcal{SHIQ}$ and the development of high-performance ontology reasoners used in the Semantic Web and modern AI. While it lacks features like qualified number restrictions, its treatment of transitivity and inverses remains a cornerstone of practical knowledge representation.

Summary updated

Abstract

Aus der Einleitung: „As widely argued [Horrocks&Gough,1997; Sattler,1996], transitive roles play an important role in the adequate representation of aggregated objects: they allow these objects to be described by referring to their parts without specifying a level of decomposition. In [Horrocks&Gough,1997], the Description Logic (DL) ALCHR+ is presented, which extends ALC with transitive roles and a role hierarchy. It is argued in [Sattler,1998] that ALCHR+ is well-suited to the representation of aggregated objects in applications that require various part-whole relations to be distinguished, some of which are transitive. However, ALCHR+ allows neither the description of parts by means of the whole to which they belong, or vice versa. To overcome this limitation, we present the DL ALCHIR+ which allows the use of, for example, has part as well as is part of. To achieve this, ALCHR+ was extended with inverse roles. It could be argued that, instead of defining yet another DL, one could make use of the results presented in [De Giacomo&Lenzerini,1996] and use ALC extended with role expressions which include transitive closure and inverse operators. The reason for not proceeding like this is the fact that transitive roles can be implemented more eficiently than the transitive closure of roles (see [Horrocks&Gough,1997]), although they lead to the same complexity class (ExpTime-hard) when added, together with role hierarchies, to ALC. Furthermore, it is still an open question whether the transitive closure of roles together with inverse roles necessitates the use of the cut rule [DeGiacomo&Massacci,1998], and this rule leads to an algorithm with very bad behaviour. We will present an algorithm for ALCHIR+ without such a rule.”
BibTeX
@misc{sattler1998description,
  author = {Ulrike Sattler and Ian Horrocks},
  title = {{A Description Logic with Transitive and Converse Roles and Role Hierarchies}},
  year = {1998},
  doi = {10.25368/2022.81},
}
Figure