Abstract
This paper addresses the computational complexity of reasoning in expressive Description Logics (DLs) that incorporate regular path expressions, a feature critical for navigational queries in the Semantic Web. While the combined complexity of these logics is often EXPTIME-complete, this work demonstrates that the data complexity—where the ontology is fixed and the dataset size varies—is NP-complete. This result suggests that highly expressive logics like those underlying OWL 2 can be theoretically as efficient as simpler database query languages when scaled to large datasets.
Introduction
In Knowledge Representation, Description Logics (DLs) provide the formal foundation for ontologies. Languages like OWL 2 allow for complex relationship modeling, including regular path expressions (e.g., finding all ancestors via recursive "parent" roles). However, increased expressivity typically leads to higher computational costs. Traditionally, research has focused on combined complexity, which accounts for growth in both the ontology and the data. This paper shifts focus to data complexity, providing a more realistic measure for large-scale applications where the set of rules (TBox) is relatively small compared to the volume of facts (ABox).
Methodology: Modular Construction and Path Decomposition
The author introduces a novel "modular construction" algorithm to decide the satisfiability of a Knowledge Base (KB). The approach moves away from monolithic model construction, instead treating the model as a quasi-forest. This structure consists of a "clearing"—the part containing named individuals from the ABox—and "subtrees" containing anonymous elements generated by the ontology's rules.
A key technical innovation is the decomposition of regular paths. Any complex path in a forest-like model can be categorized into a finite set of basic types, such as direct moves, roundtrips into subtrees, or bypasses between nominals.
By introducing "shortcut roles" that represent these complex paths as single edges in the clearing, the algorithm can verify global path constraints using only local information. This allows for an NP-guessing strategy where a valid configuration of labels is non-deterministically chosen and then verified in polynomial time.
Key Insights: Decorations and Localization
The algorithm relies on "automata decorations"—special labels on data individuals that summarize whether a path could be completed if a certain type of subtree were attached. This "virtual satisfaction" decouples the data from the potentially infinite parts of the model.
Furthermore, the author addresses the challenge of number restrictions (e.g., "at least $n$ friends") through the localization of counting. By using specific decorations, the algorithm manages to track cardinality constraints even when the related individuals are scattered or reside in anonymous subtrees.
Results and Implications
The primary result of this work is the proof that the satisfiability problem for $\mathcal{ZOIQ}$ (a logic including nominals, inverses, counting, and regular paths) is NP-complete regarding data complexity. This result unifies and extends known bounds for various fragments of OWL 2. Additionally, the paper establishes that rooted conjunctive query entailment in $\mathcal{ZIQ}$ is coNEXPTIME-complete for combined complexity, providing a new upper bound for a notoriously difficult problem.
Conclusion
While this paper settles the theoretical complexity of expressive DLs with path expressions, practical implementation remains a challenge. The "constant" factor dependent on the TBox remains exponential, necessitating future research into optimizing modular construction for actual reasoning engines. The current framework also assumes a quasi-forest model property, which may not hold for logics with certain cyclic dependencies or general role inclusions. Nevertheless, this work provides a robust theoretical foundation for scalable reasoning in complex knowledge bases.
Summary updated