On the Decidability of Role Mappings between Modular Ontologies

Jie Bao, George Voutsadakis, Giora Slutzki, Vasant G. HonavarAAAI 2008

Abstract

In the vision of the Semantic Web, knowledge is distributed across multiple, independently developed ontology modules. To integrate these modules, ontology mappings define how concepts and roles in one module relate to another. A critical challenge is ensuring that these linked systems remain decidable—guaranteeing that an automated reasoner can process them in finite time. This paper explores the "decidability frontier" for role mappings in Distributed Description Logics (DDL) and Package-based Description Logics (P-DL), proving that while certain DDL extensions are undecidable, specific P-DL variants remain computationally tractable even with complex features.

Introduction

Ontology mappings are the rules that explain how a concept or role in one module relates to another (e.g., asserting that the marriedTo relation in a "Family" module implies the knows relation in a "Social" module). Previous frameworks like DDL and P-DL offered different ways to handle these mappings, but it was not previously clear which specific combinations of features—such as negated roles or inverse mappings—would make the logic undecidable.

Methods

The authors employ two primary mathematical strategies to map out the boundaries of what is computable:

Undecidability Proofs via Domino Tiling

To show that certain DDL extensions are undecidable, the authors use a reduction from the "Domino Tiling Problem." They demonstrate that if a logic is expressive enough to encode the rules of tiling an infinite grid, it is inherently undecidable. They construct specific DDL ontologies that "force" a grid structure using features like role negation, cardinality restrictions, or inverse bridge rules.

Grid construction for the Domino Tiling reduction used in undecidability proofs.

Decidability Proofs via Logic Reduction

To prove the decidability of the P-DL variant $ALCHIO(\neg)P$, they reduce it to a known decidable logic called $ALBO$, which supports boolean role operators. By showing that a P-DL problem can be translated into an $ALBO$ problem, they inherit $ALBO$'s decidability and complexity bounds.

Key Insights and Ideas

  • The DDL "Flexibility" Trap: DDL allows for very flexible "domain relations" between modules. However, this flexibility is a double-edged sword. When combined with features like role negation or cardinality, the logic becomes powerful enough to simulate a Turing-complete grid, leading to undecidability.
  • P-DL’s Structural Safeguards: Unlike DDL, P-DL requires domain relations to be "one-to-one" and "compositionally consistent." These constraints prevent the formation of the complex, grid-like structures that cause DDL to fail, allowing P-DL to support much richer role logic (like nominals and inverses) while remaining decidable.
  • The Decidability Frontier: The paper effectively draws a line for ontology language designers. If role mappings require negation or cardinality, DDL is likely the wrong framework; P-DL offers a more robust path forward.

Key Results

  • Undecidability of DDL Extensions: The authors formally proved that DDL variants based on the $\mathcal{ALC}$ logic become undecidable if they include role negations in bridge rules ($ALC(\neg)D_{CR}$), cardinality restrictions on domain relations ($ALCD_{CRN}$), or inverse bridge rules between roles ($ALCD_{CRI}$).
  • Decidability of P-DL: The paper establishes that the P-DL family $ALCHIO(\neg)P$ is decidable. Specifically, the consistency and concept satisfiability problems for these logics are shown to be in NEXPTIME, meaning they are computationally intensive but fundamentally solvable.

Limitations and Future Work

The authors note that the decidability of P-DLs supporting unrestricted role inclusion (denoted as "H") remains an open problem. Furthermore, while they proved decidability for $ALCHIO(\neg)P$, future work is needed to see if these results hold when adding even more complex features, such as transitive roles or general number restrictions. Finally, moving from a theoretical NEXPTIME decidability proof to a high-performance reasoning engine remains a significant engineering challenge.

Summary updated

BibTeX
@inproceedings{bao2008decidability,
  author = {Jie Bao and George Voutsadakis and Giora Slutzki and Vasant G. Honavar},
  title = {{On the Decidability of Role Mappings between Modular Ontologies}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure