When Are Description Logic Knowledge Bases Indistinguishable?

Elena Botoeva, Roman Kontchakov, Vladislav Ryzhikov, Frank Wolter, Michael ZakharyaschevIJCAI 2015

Introduction

In the field of knowledge engineering, ontologies and knowledge bases (KBs) are dynamic entities, frequently subjected to versioning, modularization, or simplification through "forgetting" specific terms. A fundamental challenge for engineers is determining whether these modifications impact the end-user's experience. This paper investigates $Σ$-query inseparability: the condition under which two Description Logic (DL) KBs yield identical answers to all possible conjunctive queries (CQs) over a specific vocabulary ($Σ$).

Inseparability is a weaker condition than logical equivalence; two KBs may differ logically yet remain indistinguishable to a query engine. While complexity was previously understood for some logics, this research fills a significant gap for Horn-fragments of the $\mathcal{ALCHI}$ family, particularly those combining inverse roles and role inclusions.

Methodology: Materializations and Games

The authors transition from abstract logical definitions to a semantic characterization based on two primary concepts:

  1. Materializations and Generating Structures: A "materialization" is a model of a KB containing all information necessary to answer any CQ. Although these models can be infinite, the authors demonstrate that for Horn DLs, they can be represented by finite generating structures.
  2. Homomorphic Embeddability: The paper proves that a KB $K_1$ entails the queries of $K_2$ if and only if a $Σ$-homomorphism exists from the materialization of $K_2$ into that of $K_1$.

To operationalize this check, the authors introduce a game-theoretic framework. Inseparability is determined by a game played on finite generating structures between two players. Player 1 attempts to construct a homomorphism, while Player 2 challenges by navigating the structure. The complexity of the problem is dictated by the required strategies—such as "forward" strategies for logics without inverse roles or "backward" strategies when inverse roles are present.

The Complexity Landscape

The research maps the computational complexity of $Σ$-query inseparability across the Horn-DL family. A key finding is the "hardness" of inverse roles: the combination of inverse roles and qualified existential restrictions forces the game to permit both forward and backward moves, resulting in 2EXPTIME-completeness for Horn-$\mathcal{ALCHI}$.

Complexity landscape and game strategies for Horn-DL inseparability.

As shown in the complexity map above, the complexity varies significantly based on the logic's features:

  • P-complete: For $\mathcal{EL}$, $\mathcal{ELH}$, and basic $DL-Lite$.
  • EXPTIME-complete: For $Horn-\mathcal{ALC}$, $Horn-\mathcal{ALCH}$, and $DL-Lite^H$.
  • 2EXPTIME-complete: For $Horn-\mathcal{ALCI}$ and $Horn-\mathcal{ALCHI}$.

In terms of data complexity, the problem remains P-complete for nearly all studied logics, matching the complexity of standard query answering.

Illustrative Example

While this is a theoretical paper focused on formal proofs, the authors utilize "toy" examples to ground their concepts. For instance, an automotive industry TBox illustrates how complex relationships between components and engine types can be modeled.

A sample TBox from the automotive industry used for illustrative purposes.

Such examples demonstrate that significant simplifications—like removing internal axioms—can be achieved without altering the results of user-facing queries, providing a theoretical basis for knowledge exchange and module extraction.

Conclusion and Future Directions

This work provides a unified framework for understanding query inseparability in Horn DLs. However, several limitations remain. The results are restricted to Horn logics; non-Horn logics lack the "best" materialization property, making them significantly harder to analyze. Additionally, the 2EXPTIME complexity for expressive fragments suggests that practical implementations will require sophisticated heuristics or the identification of tractable sub-fragments for real-world ontologies. Future research may also explore scenarios where the signature $Σ$ is not fixed, seeking the largest possible vocabulary for which two KBs remain inseparable.

Summary updated

BibTeX
@inproceedings{botoeva2015when,
  author = {Elena Botoeva and Roman Kontchakov and Vladislav Ryzhikov and Frank Wolter and Michael Zakharyaschev},
  title = {{When Are Description Logic Knowledge Bases Indistinguishable?}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure