On Finite and Unrestricted Query Entailment beyond SQ with Number Restrictions on Transitive Roles

Tomasz Gogacz, Víctor Gutiérrez-Basulto, Yazmín Ibáñez-García, Jean Christoph Jung, Filip MurlakIJCAI 2019 · DOI

TL;DR

This paper delves into the complexities of querying knowledge bases described by description logics (DLs) that combine number restrictions with transitive roles. The authors establish tight computational complexity bounds for various query types, including regular path queries and instance queries, for extensions of the DL SQ. This work is crucial for building more expressive and practical knowledge representation systems, especially in domains like biomedicine where such combinations are essential.

What Problem Does This Paper Address?

Knowledge representation systems often use description logics (DLs) to model information. A key task is querying these knowledge bases, which involves determining if a query is entailed by the knowledge base. While DLs like SQ offer a good balance of expressivity and decidability, combining certain features can lead to undecidability. Specifically, the interaction between number restrictions (e.g., "at least 3") and transitive roles (e.g., "is a subclass of" which implies "is a subclass of a subclass of") is problematic. Previous work often restricted this interaction. However, real-world applications, like modeling biological structures, require expressing constraints like "an organ has exactly one mitral valve, which is shared by its left and right atrium." This paper addresses the challenge of understanding the computational complexity of query entailment in DLs that allow this problematic interaction, specifically focusing on extensions of SQ with nominals (SOQ) and inverse roles (SIQ⁻). They also investigate the distinction between unrestricted query entailment and finite query entailment, which is particularly relevant for database applications.

Methods

The authors employ a combination of theoretical computer science techniques to tackle the problem. A core contribution is the development of a tree-like counter-model property for the studied DLs. This property, an extension of existing techniques for SQ, shows that if a query is not entailed, a counter-model exists with a specific "canonical tree decomposition" of bounded width and outdegree. This property is instrumental in devising automata-based decision procedures.

For unrestricted query entailment, they construct non-deterministic tree automata (NTAs) that recognize these canonical tree decompositions. The emptiness problem for these NTAs then directly translates to query entailment, yielding tight 2EXPTIME upper bounds.

For finite query entailment, they adapt existing approaches by introducing the notion of a "safe" canonical tree decomposition. This involves ensuring that no infinite downward paths in the decomposition are associated with the same transitive role. They then show how to construct NTAs that recognize these safe decompositions, leading to 2EXPTIME upper bounds for finite query entailment as well.

A significant part of the work involves reducing known hard problems (like the word problem for alternating Turing machines) to query entailment in their DLs. This establishes 2EXPTIME-hardness lower bounds, demonstrating that their upper bounds are optimal.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity analysis and does not involve empirical evaluation on specific datasets.

Key Insights and Ideas

  • The "dangerous" interaction: The paper highlights why combining number restrictions and transitive roles is computationally challenging, yet practically necessary. They provide concrete examples of its importance.
  • Canonical Tree Decompositions as a unifying tool: The authors show how extending the concept of canonical tree decompositions allows for a unified approach to both unrestricted and finite query entailment in these complex DLs.
  • Finite vs. Unrestricted Entailment: They demonstrate that for these logics, finite and unrestricted entailment do not always coincide, making the study of finite entailment a distinct and important problem.
  • Surprising Complexity for Instance Queries: The paper reveals that adding inverse roles to SQ (resulting in SIQ⁻) makes instance query entailment 2EXPTIME-hard, which is unusual as instance queries are often less complex than other query types.
  • Automata-theoretic approach: The successful application of non-deterministic tree automata with Büchi acceptance conditions for recognizing specific tree decompositions is a key methodological insight.

Key Results

  • 2EXPTIME-completeness for Regular Path Queries (PRPQ): The paper establishes tight 2EXPTIME upper bounds for PRPQ entailment over SOQ and SIQ⁻ knowledge bases, both for unrestricted and finite entailment. These bounds are matched by lower bounds derived from reductions of known hard problems.
  • 2EXPTIME-completeness for Instance Queries (IQ):
    • Finite and unrestricted IQ entailment over SOQ knowledge bases is NEXPTIME-complete.
  • Unrestricted IQ entailment over SIQ⁻ knowledge bases is 2EXPTIME-complete.
  • Finite IQ entailment over SIQ⁻ knowledge bases, restricted to a single transitive role and no non-transitive roles, is also 2EXPTIME-complete.
  • Lower Bounds: The paper proves 2EXPTIME-hardness for PRPQ entailment in SOQ and SIQ⁻, and for IQ entailment in SIQ⁻, by reducing the word problem for alternating Turing machines.

Limitations and Future Work

  • Full SIQ⁻ Coverage: The paper focuses on specific fragments of SIQ⁻ for finite entailment (e.g., single transitive role). A natural next step is to cover full SIQ⁻ for finite entailment of more complex queries like PRPQs. This is noted as challenging due to the difficulty in guaranteeing strongly canonical decompositions.
  • Generalizing Colored Blocking: For more complex query types and logics, generalizing the "colored blocking principle" or developing entirely new techniques might be necessary.
  • Beyond Instance Queries: Extending the finite entailment results beyond instance queries for full SIQ⁻ is a significant open problem.
  • Practical Implementations: While the theoretical complexity is established, the practical implications and performance of decision procedures based on these results would be an interesting area for future research.

Summary updated

BibTeX
@inproceedings{gogacz2019finite,
  author = {Tomasz Gogacz and Víctor Gutiérrez-Basulto and Yazmín Ibáñez-García and Jean Christoph Jung and Filip Murlak},
  title = {{On Finite and Unrestricted Query Entailment beyond SQ with Number Restrictions on Transitive Roles}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/238},
}
Figure