Abstract
Reasoning over complex queries in the Description Logics (DLs) underlying OWL 2 is of importance in several application domains. This research provides decidability and tight upper bounds for checking entailment and containment of positive regular path queries under various combinations of constructs used in expressive DLs—specifically regular expressions and (safe) Booleans over roles, and the combination of any two constructs among inverse roles, qualified number restrictions, and nominals. These results extend to the DLs of the SR family, directly impacting the OWL 2 standard.
Introduction
In the landscape of the Semantic Web, ontologies powered by the Web Ontology Language (OWL 2) serve as the backbone for structured knowledge representation. These ontologies rely on Description Logics (DLs) to define categories and relationships. However, a persistent "reasoning gap" has existed between the expressive power of these logics and the ability to perform complex, database-like queries over them. Specifically, Regular Path Queries (RPQs)—which allow for searching paths defined by regular expressions—are computationally expensive and, in many expressive DLs, have historically been mathematically undecidable.
This paper addresses this gap by establishing the first decidability results and tight complexity bounds for querying expressive DLs that incorporate nominals, inverse roles, and counting restrictions.
The Challenge of Graph-Like Structures
The difficulty in reasoning within expressive DLs like $SROIQ$ (the logic behind OWL 2) stems from the interaction of three specific features:
- Nominals ($O$): References to specific individuals (e.g., "The Eiffel Tower") within class definitions.
- Inverse Roles ($I$): The ability to navigate relationships in both directions (e.g., "parent of" vs. "child of").
- Qualified Number Restrictions ($Q$): The ability to count relationships (e.g., "has at least 3 children who are doctors").
Individually, these features are manageable. However, when combined, they break the "tree-model property"—the characteristic that any satisfiable concept has a model that looks like a tree. Nominals, in particular, act as "shortcuts" between branches, turning the data structure into a complex graph. Standard tree automata techniques, which are the workhorse of DL reasoning, fail in these non-tree environments.
Methodology: $ZOIQ$ and Fully Enriched Automata
To overcome these structural challenges, the authors propose a new framework centered on a highly expressive DL called $ZOIQ$. This logic incorporates regular expressions over roles, Boolean role operators, and "Self" concepts.
Quasi-Forest Models
The researchers proved that while nominals disrupt pure tree structures, the models of these logics still behave like "quasi-forests." In a quasi-forest, the model is a collection of trees where the roots (representing nominals) can be interconnected in complex ways, but the rest of the structure remains tree-like.
Fully Enriched Automata (FEA)
To reason over these quasi-forests, the paper employs Fully Enriched Automata (FEA). These are advanced state machines capable of:
- Navigating both up and down tree branches.
- "Jumping" to specific nominal roots.
- Performing "graded" transitions to handle qualified number restrictions (counting neighbors).
The core of the proof involves "internalizing" the entire Knowledge Base (the ABox and TBox) into a single concept and then reducing the query entailment problem to an "emptiness problem" for the FEA—essentially checking if there is any model that the automaton would accept.
Key Results and Complexity
The paper provides a comprehensive map of the complexity landscape for these logics:
- Satisfiability: Checking the consistency of a Knowledge Base in sublogics of $SROIQ$ (such as $SRIQ$, $SROI$, and $SROQ$) is shown to be 2EXPTIME-complete. This holds even when numbers in restrictions are represented in binary.
- Query Entailment: The authors establish that Positive 2-way Regular Path Queries (P2RPQs)—which support complex regular expressions and inverse navigation—are decidable.
- Complexity Bounds: For most expressive logics, query entailment is found to be in 2EXPTIME (using unary coding for numbers). This provides a "tight" upper bound, defining the exact computational difficulty of these problems.
- Query Containment: The research offers the first decidability results for determining if one recursive query is a subset of another within these specific DL frameworks.
Implications and Future Work
This work represents a significant theoretical milestone in DL research. By treating nominals as "anchors" or roots, the authors unified the treatment of the "Big Three" features ($O, I, Q$), which was previously considered a "holy grail" in the field.
However, challenges remain. The decidability of the full $ZOIQ$ logic (combining $O, I,$ and $Q$ simultaneously) was not fully resolved at the time of publication. Additionally, while the 2EXPTIME algorithms are theoretically optimal, they involve massive exponential blowups that make direct implementation difficult. Future work is required to translate these theoretical frameworks into efficient, real-world reasoners for the Semantic Web.
Summary updated