Worst-Case Optimal Querying of Very Expressive Description Logics with Path Expressions and Succinct Counting

Bartosz Bednarczyk, Sebastian RudolphIJCAI 2019 · DOI

TL;DR

This paper tackles the challenge of querying highly expressive knowledge representation languages (Description Logics) with complex path expressions and counting. The authors introduce a novel reduction technique that achieves worst-case optimal query answering, proving that this can be done efficiently (EXPTIME-complete) even without the previously assumed unary encoding for number restrictions, as long as the query size is bounded.

What Problem Does This Paper Address?

Knowledge representation (KR) systems, particularly Description Logics (DLs), are powerful tools for modeling complex information. Querying these knowledge bases (KBs) is a fundamental task. While simple queries are well-understood, more expressive query languages, like positive two-way regular path queries (P2RPQs), pose significant computational challenges, especially when combined with highly expressive DLs like ZOIQ. ZOIQ supports features like nominals, role inverses, and number restrictions, making query answering undecidable in its full generality. Previous work established decidability and complexity bounds for fragments of ZOIQ, but often relied on the assumption of unary encoding for number restrictions, which can lead to very large representations. This paper aims to remove this assumption and provide tighter complexity bounds for querying expressive DLs with path expressions, extending these results to the guarded two-variable fragment of first-order logic with counting.

Methods

The core of the paper's contribution lies in a novel reduction technique. The authors transform the query entailment problem ($K \models q$) into a knowledge base satisfiability problem ($K \models q \iff K \cup K_q \models \bot$). This is achieved by introducing a mechanism to "annotate" models of the KB with information about query matches.

  1. Annotation Framework: They define a KB $K_q$ that, when combined with the original KB $K$, annotates domain elements with special concept names ($Q_M$) indicating how parts of the query ($q$) match into the model. This annotation process is deterministic and iterative, leveraging automata-theoretic techniques for path expressions.
  2. Reduction to Satisfiability: The key insight is that if a query $q$ is entailed by $K$, then any model of $K$ (and the associated annotations $K_q$) must satisfy certain conditions. Conversely, if $K \cup K_q$ is unsatisfiable, it implies that no model of $K$ can satisfy $q$. This reduction is shown to be query-entailment-preserving.
  3. Succinct Counting: A significant achievement is demonstrating that this reduction works without requiring unary encoding for number restrictions. By leveraging the "quasi-forest model property" and "quasi-forest homomorphism-cover property" of certain DL fragments, they show that the complexity remains manageable.
  4. GC² Extension: The authors also provide a polynomial-time translation from GC² databases (guarded two-variable logic with counting) to ZIQ KBs. This allows them to transfer their DL query answering results to this related formalism.

Datasets

Not discussed in the paper. The focus is on theoretical complexity results rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Removing Unary Encoding Burden: The most significant insight is that the complexity of querying expressive DLs with path expressions and counting doesn't necessarily increase when moving from unary to binary encoding of number restrictions, provided the query size is bounded. This simplifies practical implementation and theoretical analysis.
  • Annotation as a Unifying Technique: The annotation framework provides a powerful and general method for reasoning about query matches within DL models. It elegantly captures the interaction between query structure and KB semantics.
  • Bridging DLs and First-Order Logic: The paper successfully bridges the gap between expressive DLs and fragments of first-order logic (GC²) by providing a translation, showing that similar query answering capabilities can be achieved in both paradigms.
  • Worst-Case Optimality: The paper establishes worst-case optimal complexity bounds, meaning the algorithms presented are as efficient as theoretically possible for the given problem and logic fragment.

Key Results

  • EXPTIME-completeness for Bounded Queries: The paper proves that querying tame ZOIQ KBs with simplified P2RPQs is EXPTIME-complete when the number of atoms in the query is bounded by a constant.
  • 2EXPTIME-completeness for General Queries: For general simplified P2RPQs (without a bounded number of atoms), the complexity is 2EXPTIME-complete.
  • GC² Extension: P2RPQ entailment from GC² databases is also shown to be 2EXPTIME-complete, dropping to EXPTIME-complete for bounded-size queries.
  • Strengthened Query Containment Results: The findings lead to improved complexity bounds for query containment problems in DLs.

Limitations and Future Work

  • Finite Model Querying: The current results hold for arbitrary models. The authors note that very little is known about finite model query answering in these expressive DLs, which is a significant open area.
  • Query Language Expressivity: While the technique is powerful, it might not be readily extendable to even more elaborate query languages beyond P2RPQs, such as those with nested queries or more complex structural recursion.
  • Practical Implementation: The theoretical results establish worst-case optimal complexity. Further research would be needed to explore practical implementations and optimizations for these complex reasoning tasks.

Summary updated

BibTeX
@inproceedings{bednarczyk2019worst,
  author = {Bartosz Bednarczyk and Sebastian Rudolph},
  title = {{Worst-Case Optimal Querying of Very Expressive Description Logics with Path Expressions and Succinct Counting}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/212},
}
Figure