Source-linked AI summary
Conjunctive Query Answering for the Description Logic SHIQ
Birte Glimm, Ian Horrocks, Carsten Lutz, Ulrike Sattler
TL;DR
The paper studies the poorly understood problem of answering unions of conjunctive queries over SHIQ knowledge bases when transitive roles occur in both queries and knowledge bases. It develops a rewriting-based decision procedure and proves decidability with a tight single-exponential-in-KB and double-exponential-in-query combined bound, plus co-NP-complete data complexity. These results also settle related decidability questions for query containment and weakly safe Datalog extensions.
Problem
Conjunctive query answering over expressive DL knowledge bases is challenging when transitive roles are admitted in queries.
Method
The paper rewrites conjunctive queries into tree-shaped or grounded queries whose entailment reduces to standard reasoning problems.
Results
The paper proves decidability, with time single exponential in KB size and double exponential in query size, and co-NP-completeness for data complexity.
Takeaways & Limitations
The procedure also establishes decidability for related problems including query containment and consistency of SHIQ knowledge bases with weakly safe Datalog rules.
Takeaways & Limitations
Extending the procedure to SHOIQ and making SHIQ query answering more implementable remain future work.
Abstract
from arXiv · showhide
Conjunctive queries play an important role as an expressive query language for Description Logics (DLs). Although modern DLs usually provide for transitive roles, conjunctive query answering over DL knowledge bases is only poorly understood if transitive roles are admitted in the query. In this paper, we consider unions of conjunctive queries over knowledge bases formulated in the prominent DL SHIQ and allow transitive roles in both the query and the knowledge base. We show decidability of query answering in this setting and establish two tight complexity bounds: regarding combined complexity, we prove that there is a deterministic algorithm for query answering that needs time single exponential in the size of the KB and double exponential in the size of the query, which is optimal. Regarding data complexity, we prove containment in co-NP.
1. Introduction
The paper addresses conjunctive query entailment in SHIQ, where transitive roles make reasoning challenging, and generalizes an earlier decision procedure to unions of conjunctive queries. It establishes decidability, tight combined-complexity bounds, co-NP-completeness for data complexity, and consequences for rule extensions.
- Motivation: SHIQ knowledge bases support expressive reasoning services, but conjunctive query entailment becomes challenging when query roles may be transitive.DLs use concepts and roles as unary and binary predicates, while SHIQ reasoning services include satisfiability and instance retrieval.
- Contribution: The paper generalizes an earlier SHIQ decision procedure from conjunctive queries to unions of conjunctive queries.It rewrites each conjunctive query into tree-shaped or grounded queries whose entailment reduces to standard reasoning problems.
- Results: Conjunctive query entailment in SHIQ has a deterministic algorithm with time single exponential in KB size and double exponential in query size.The paper states this bound is tight and therefore establishes the combined complexity of the problem.
- Results: Conjunctive query entailment is 2ExpTime-complete for SHIQ and strictly harder than instance checking.The lower bound already holds for ALCI, while instance retrieval has co-NP-complete data complexity in SHIQ.
- Consequences: Decidability of unions of conjunctive queries also closes the consistency problem for SHIQ knowledge bases extended with weakly safe Datalog rules.The paper connects these problems through an existing equivalence between UCQ entailment and rule-extended knowledge-base consistency.
2. Preliminaries
The preliminaries define SHIQ knowledge bases, their syntax and semantics, and conjunctive queries. They also introduce query entailment, query answering, role inverses and hierarchies, transitivity, equality, and cyclic query structure.
- SHIQ syntax and semantics: SHIQ interpretations map concepts to domain subsets, roles to binary relations, transitive roles to transitive relations, and individuals to domain elements.Role inclusions are interpreted as relation inclusions.
- SHIQ syntax and semantics: SHIQ concepts are built from concept names using Boolean constructors, role restrictions, and number restrictions on simple roles.The grammar includes universal and existential restrictions plus at-most and at-least restrictions.
- SHIQ syntax and semantics: A SHIQ knowledge base is a triple (T, R, A) consisting of a TBox, role hierarchy, and ABox, and is consistent when it has a model.The TBox contains GCIs, the role hierarchy contains role inclusions, and the ABox contains concept, role, negated-role, and inequality assertions.
- Conjunctive queries: Query answers are tuples of individual names whose substitutions produce Boolean queries entailed by the knowledge base.Unions of conjunctive queries are disjunctions of conjunctive queries, and non-Boolean answering reduces to entailment.
- Conjunctive queries: A Boolean conjunctive query is a non-empty set of concept, role, and equality atoms with existentially quantified variables.Ground queries contain only individual names; query entailment asks whether every model of a knowledge base satisfies the query.
- Query structure: Cyclic queries are identified from the underlying undirected graph of terms and role atoms, with inverse roles making edge direction irrelevant.Multiple role atoms between the same two terms do not by themselves constitute a cycle.
3. Related Work
Related work covers automata-based procedures, restricted query semantics, undecidability results, query containment, and DL–rule integration. The paper’s procedure supports standard first-order semantics with transitive roles and yields stronger data-complexity information than the cited automata approach.
- Automata-based approaches: An automata-based procedure decides positive existential path queries over ALCQIbreg and therefore provides a decision procedure for SHIQ conjunctive-query entailment.The paper characterizes that approach as more elegant but notes that it does not provide an NP upper bound for data complexity.
- Existing query procedures: Most earlier expressive-DL algorithms disallow transitive roles in conjunctive queries, preventing them from answering some queries considered here.Other systems commonly restrict variable assignments to individuals named in the ABox, which changes the query semantics.
- Boundaries: Conjunctive-query entailment remains open for SHOIQ, while extensions with inequalities or safe role negation can become undecidable.These undecidability results apply even to some DLs with lower expressivity.
- Query containment: A decision procedure for unions of conjunctive queries in SHIQ can also decide query containment with respect to a TBox.Query containment reduces to entailment for unions of conjunctive queries over a knowledge base.
- DL–rule integration: Decidability of SHIQ UCQ entailment implies decidability of consistency for SHIQ knowledge bases extended with weakly safe Datalog rules.Arbitrary Datalog extensions can be undecidable, motivating safeness restrictions on rule–DL interaction.
4. Query Rewriting by Example
The paper illustrates a rewriting strategy that uses forest-shaped canonical models to transform cyclic conjunctive queries into ground or tree-shaped queries whose entailment can be checked for SHIQ knowledge bases.
- Forest models: The rewriting procedure focuses on forest models, transforming cyclic query components into tree-shaped subqueries with forest-shaped matches.Forest bases preserve tree structure while allowing transitive roles to be interpreted without transitive closure.
- Canonical interpretations: A canonical model is based on a forest base and differs from it only in the interpretation of non-simple roles.The forest base organizes each ABox individual’s domain elements as a tree rooted at that individual.
- The running example: The canonical interpretation represents ABox individuals as root nodes and shows transitive-role shortcuts as additional relationships.The domain elements are pairs (a, w), where a identifies the root individual and w belongs to the corresponding tree.
- The running example: The running query is cyclic because its underlying undirected graph contains a cycle, motivating the rewriting examples.The example knowledge base contains concept, role, and ABox assertions, while the query has variables u, x, y, and z and no individual names.
- The running example: A match of the original query onto the canonical interpretation demonstrates that the query is true in every model of the knowledge base.The text states K |= q for the running example.
- Rewriting outcome: The complete rewriting yields ground queries or rolled-up concept atoms, and entailment of their disjunction is equivalent to entailment of the original query.The procedure has a bound on the number of forest-shaped rewritings and reduces checking the rewritten queries to knowledge-base consistency.
5. Query Rewriting
The rewriting procedure transforms conjunctive queries into forest-shaped, tree-shaped, ground, or single-concept queries while preserving entailment. This reduction supports a decision procedure for UCQs over SHIQ knowledge bases with transitive roles.
- Tree- and Forest-Shaped Queries: A root splitting partitions reachable query terms into disjoint regions unless their roots are equivalent modulo ≈ *.Each root induces a sub-query containing atoms whose terms lie in its reachable region.
- Query Rewriting: The rewriting steps exhaustively transform each conjunctive-query disjunct, including collapsings and split rewritings that replace role atoms using transitive sub-roles.The resulting split rewritings are paired with root splittings and are later refined into forest-shaped rewritings.
- From Forests to Concepts: Forest and ground rewritings yield a disjunction of queries that are either single concept atoms or ground queries, preserving entailment of the original query.For the constructed queries q1 ∨· · · ∨qℓ, K |= q iff K |= q1 ∨· · · ∨qℓ.
- Query Matches: Query matches guide rewriting by transforming arbitrary matches into split, forest, and tree matches, with each stronger match inducing a corresponding query shape.Every tree match is a forest match, and every forest match is a split match.
- Correctness of the Query Rewriting: A canonical-model match can be rewritten into a forest match that is injective modulo ≈ *, establishing the correctness bridge from arbitrary queries to forest-shaped queries.The same correspondence is stated for split and tree-related rewritings through induced root splittings.
- Summary and Discussion: The rewriting sets are computable in polynomial time in KB size and exponential time in query size, while their size depends on transitive roles and role-hierarchy depth for queried non-simple roles.Theorem 19 reduces entailment to the disjunction of treesK(q) and groundK(q).
6. The Decision Procedure
The procedure rewrites conjunctive queries into tree-shaped and ground queries, then decides entailment through consistency tests on extended knowledge bases. It establishes tight combined-complexity bounds, co-NP-completeness for data complexity, and decidability consequences for related tasks.
- Decision procedure: The deterministic algorithm answers entailment by checking whether every extended knowledge base is inconsistent.The extensions block tree matches through TBox axioms and spoil ground-query matches through added ABox assertions.
- Correctness: The algorithm is correct for unions of connected Boolean conjunctive queries under the unique name assumption.The correctness result is later extended beyond the unique name assumption using A-partitions.
- Combined complexity: 2ExpTime-complete is the combined complexity of Boolean conjunctive-query entailment in SHIQ.A matching lower bound establishes tightness, improving the previous co-3NExpTime upper bound for simple query roles.
- Data complexity: co-NP-complete is the data complexity of conjunctive-query entailment in SHIQ.Non-entailment is decidable in nondeterministic polynomial time in the ABox size, and co-NP-hardness already holds for ALE.
- Consequences: The results also establish decidability of query containment and consistency for SHIQ knowledge bases extended with weakly safe Datalog rules.Query answering reduces to entailment tests over possible answer tuples, with at most mA^k tests for k answer variables and mA individual names.
7. Conclusions
The paper closes an open decidability problem for UCQ entailment in SHIQ and derives decidability for related tasks. Its future work targets SHOIQ and more implementable, goal-directed rewriting procedures.
- Conclusions: The decision procedure closes a longstanding open problem for unions of conjunctive-query entailment in SHIQ.It also yields decidability for query answering, query containment, and weakly safe Datalog extensions.
- Conclusions: 2ExpTime-completeness holds for combined complexity, while data complexity is co-NP-complete.The paper notes that UCQ entailment is theoretically no harder than SHIQ instance checking with respect to data complexity.
- Future work: Future work will extend the procedure to SHOIQ and seek more implementable query-answering algorithms through goal-directed rewriting.The paper identifies goal-directed query rewriting as crucial for improved implementability.
Appendix A. Complete Proofs
The appendix supplies correctness proofs for canonical-model reductions, query rewritings, and the deterministic and nondeterministic decision procedures. It also derives their complexity bounds and handles removal of the unique name assumption.
- Canonical models: A non-entailment has a canonical model that does not satisfy the query.This canonical-model property supports reducing query entailment to checking canonical structures.
- Canonical-model construction: The constructed interpretation satisfies the knowledge base and provides a canonical model from which query non-entailment is proved.A contradiction would transfer a query match into the original countermodel.
- Query rewriting: Collapsing, split, and loop rewritings preserve query satisfaction while restructuring matches in canonical models.The proofs show both directions: rewritten matches imply original-query matches, and canonical matches can be transformed into rewritten matches.
- Decision procedure: The rewriting theorem reduces each Boolean conjunctive query to tree or ground queries without changing entailment.The algorithmic correctness theorem then applies the extended-knowledge-base test under the unique name assumption.
- Complexity: 2p(m)2p(n) bounds consistency checks and deterministic UCQ entailment, with p polynomial.The same bound appears for SHIQ conjunction knowledge bases and for the connected-query procedure.
- Data complexity: Non-entailment without the unique name assumption is characterized through an A-partition and a corresponding query.The nondeterministic procedure runs in polynomial time in the ABox size when the TBox, role hierarchy, and query are fixed.