Query Answering in the Horn Fragments of the Description Logics SHOIQ and SROIQ

TL;DR

This paper tackles the challenge of efficiently querying complex knowledge bases represented in OWL 1 and OWL 2 (specifically, their Horn fragments). The authors present novel algorithms that achieve surprisingly good performance, showing that querying these expressive logics is no harder than standard reasoning tasks, with complexity bounds of EXPTIME and 2EXPTIME for combined complexity and PTIME for data complexity.

What Problem Does This Paper Address?

The Semantic Web relies heavily on Description Logics (DLs) for knowledge representation, with OWL 1 and OWL 2 being prominent standards. However, the expressiveness of these DLs comes with a significant computational cost, making reasoning and querying tasks computationally expensive. This is particularly true for tasks like deciding knowledge base satisfiability or concept subsumption, which are NEXPTIME-complete for SHOIQ (OWL 1) and 2NEXPTIME-complete for SROIQ (OWL 2). Even basic query answering (conjunctive queries) is a challenge, with decidability still an open question for full SHOIQ and SROIQ.

To address this, researchers have explored "Horn fragments" of these DLs. These fragments restrict the DL's syntax to exclude disjunctions, making them more computationally tractable, especially in terms of data complexity. While previous work showed these Horn fragments are better for basic reasoning, the complexity of answering more sophisticated queries, like 2-way regular path queries (2CRPQs), remained an open question. This paper aims to fill that gap by providing algorithms and complexity results for 2CRPQ answering in the Horn fragments of SHOIQ and SROIQ.

Methods

The core of the paper's contribution lies in developing algorithms for answering 2-way regular path queries (2CRPQs) over Horn fragments of SHOIQ and SROIQ. The authors leverage the concept of a "universal model," which is a special model of a knowledge base that can be used to answer all queries. They show that these Horn fragments possess a "forest-like" universal model that can be finitely represented by a "model description."

This model description is a structured representation of the universal model, comprising a graph part and a successor function. The authors then develop a method to check if a query is satisfied by this universal model. This involves:

  1. Query Partitioning: Decomposing the 2CRPQ into smaller parts that can be evaluated over different components of the universal model (graph nodes vs. tree structures).
  2. Tree Automata: Using tree automata to efficiently check query satisfaction within the tree-shaped parts of the universal model.
  3. Path Relation Computation: Effectively computing a relation that captures all relevant paths between graph nodes in the universal model.

The paper also shows that query answering in Horn-SHOIQ and Horn-SROIQ can be reduced to query answering in a simpler DL called Horn-ALCHOIQDis, which simplifies the analysis.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity and algorithmic development rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Querying Expressive DLs is Tractable (in Horn Fragments): The most significant insight is that answering complex queries like 2CRPQs in the Horn fragments of OWL 1 and OWL 2 is computationally feasible, with complexity bounds matching those of standard reasoning tasks. This is a substantial improvement over the undecidability or high complexity of such queries in the full DLs.
  • Universal Models as a Key Tool: The existence and convenient representation of a universal model (specifically, a forest-like one) is crucial for developing efficient query answering algorithms. This model acts as a canonical representation that simplifies the query evaluation process.
  • Model Descriptions for Structure: The novel concept of "model descriptions" provides a finite way to represent potentially infinite universal models, making them amenable to algorithmic manipulation.
  • 2CRPQs as a Powerful Query Language: The paper highlights the utility of 2CRPQs, which generalize standard conjunctive queries and allow for complex navigation patterns, making them suitable for querying rich knowledge bases.

Key Results

  • Combined Complexity:
    • Query answering for 2CRPQs in Horn-SHOIQ is EXPTIME-Complete.
  • Query answering for 2CRPQs in Horn-SROIQ is 2EXPTIME-Complete.
  • Data Complexity:
    • For both Horn-SHOIQ and Horn-SROIQ, data complexity of 2CRPQ answering is PTIME-Complete.
  • Novelty: These are the first completeness results for query answering in DLs that support inverses, nominals, and counting.
  • Efficiency: The algorithms developed are shown to be optimal in terms of complexity.

Limitations and Future Work

  • Theoretical Focus: The paper primarily focuses on theoretical complexity bounds and algorithmic development. While it provides a strong theoretical foundation, empirical evaluation on real-world ontologies and benchmarks would be valuable to assess practical performance.
  • Horn Fragments: The results are specific to the Horn fragments of OWL. Extending these findings to the full OWL 1 and OWL 2 languages remains a significant challenge.
  • Future Directions: The authors suggest that their techniques could pave the way for more efficient querying algorithms for the Horn restrictions of OWL and might offer insights into tackling CQ entailment for full SROIQ and SHOIQ. Further research could explore the application of these methods to other expressive DLs or more complex query languages.

Summary updated

BibTeX
@inproceedings{2011query,
  title = {{Query Answering in the Horn Fragments of the Description Logics SHOIQ and SROIQ}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
}
Figure