Abstract
In the field of Description Logics (DLs), identifying the features that drive computational complexity is crucial for designing efficient reasoning systems. This paper, presented at AAAI-22, explores the impact of the Self operator on Conjunctive Query (CQ) entailment. Contrary to previous assumptions that Self is a "benign" feature, the authors prove that its inclusion in the basic logic $\mathcal{ALC}$ raises the complexity of CQ entailment from EXPTIME-complete to 2EXPTIME-hard. This result settles a long-standing open problem regarding the complexity of the $\mathcal{Z}$ family of logics.
Introduction
Description Logics are formalisms used to represent knowledge in a structured way, forming the backbone of the Semantic Web. A primary reasoning task is Conjunctive Query (CQ) entailment, which involves determining if a complex query is logically implied by a knowledge base. For the standard logic $\mathcal{ALC}$, this task is EXPTIME-complete. Researchers have identified several "malign" features, such as inverse roles and nominals, that push this complexity to 2EXPTIME-hard. Until now, the Self operator—allowing the definition of concepts like "entities related to themselves"—was considered computationally inexpensive and was included in standards like OWL 2 without much concern for performance overhead.
Methodology: Reducing ATM to CQ Entailment
The authors establish the 2EXPTIME-hardness of $\mathcal{ALC}_{Self}$ through a reduction from the problem of simulating an Alternating Turing Machine (ATM) that operates within exponential space. The reduction involves encoding the ATM's computation history into a set of tree-like structures.
Configuration Units and the "Self" Trick
The core of the reduction relies on constructing full binary trees to represent the Turing machine's tape. Because $\mathcal{ALC}_{Self}$ lacks inverse roles, the authors cannot easily traverse "up" the tree or link distant nodes. To overcome this, they employ a "Self trick." By using the Self operator to create self-loops on specific nodes, they allow a conjunctive query to "idle" or circle in place.
This mechanism enables the query to mimic case distinctions and check complex consistency conditions across different branches of the tree. If the Turing machine makes an illegal transition, a carefully designed query will find a match. Thus, the absence of a query match proves the existence of a valid, accepting computation path for the ATM.
Key Insights and Results
The primary finding is that the Self operator is a "malign" feature for query answering. It provides enough expressive power to simulate disjunction over paths, which is a key ingredient for 2EXPTIME-hardness. This result has significant theoretical implications:
- Complexity Parity: It places $\mathcal{ALC}_{Self}$ in the same complexity class as much more expressive logics like $\mathcal{ALCI}$ (with inverses) and $\mathcal{SROIQ}$.
- Closing Theoretical Gaps: It resolves the complexity of the $\mathcal{Z}$ family of logics, a problem open since 2009, and establishes the hardness of the forward guarded fragment with equality.
Conclusion
The discovery that Self is 2EXPTIME-hard for CQ entailment highlights how seemingly local features can have a profound global impact on reasoning complexity. While this represents a worst-case theoretical bound, it cautions developers of DL-based systems that the inclusion of Self can lead to "pathological" performance issues in complex querying scenarios. Future research will likely focus on identifying tractable fragments of $\mathcal{ALC}_{Self}$ that remain efficient for practical applications.
Summary updated