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:
- 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.
- 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}$.
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.
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