Regular Path Queries in Expressive Description Logics with Nominals

Diego Calvanese, Thomas Eiter, Magdalena OrtizIJCAI 2009 · OpenReview

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:

  1. Nominals ($O$): References to specific individuals (e.g., "The Eiffel Tower") within class definitions.
  2. Inverse Roles ($I$): The ability to navigate relationships in both directions (e.g., "parent of" vs. "child of").
  3. 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

Abstract

Reasoning over complex queries in the DLs underlying OWL 2 is of importance in several application domains. We provide decidability and (tight) upper bounds for the problem of checking entailment and containment of positive regular path queries under various combinations of constructs used in such expressive DLs; specifically: regular expressions and (safe) Booleans over roles, and allowing for the combination of any two constructs among inverse roles, qualified number restrictions, and nominals. Our results carry over also to the DLs of the SR family, and thus have a direct impact on OWL 2.
BibTeX
@inproceedings{calvanese2009regular,
  author = {Diego Calvanese and Thomas Eiter and Magdalena Ortiz},
  title = {{Regular Path Queries in Expressive Description Logics with Nominals}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=H1Vn9SG_br},
}
Figure