Conjunctive Query Answering for the Description Logic SHIQ

By Birte Glimm, Ian Horrocks, Carsten Lutz, U. Sattler. International Joint Conference on Artificial Intelligence, 2007

310 citations recorded by the source corpus.

Conjunctive queries play an important role as an expressive query language for Description Logics (DLs). Although modern DLs usually provide for transitive roles, it was an open problem whether conjunctive query answering over DL knowledge bases is decidable if transitive roles are admitted in the query. In this paper, we consider conjunctive queries over knowledge bases formulated in the popular DL SHIQ and allow transitive roles in both the query and the knowledge base. We show that query answering is decidable and establish the following complexity bounds: regarding combined complexity, we devise 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. Regarding data complexity, we prove co-NP-completeness.

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/ce4817f431c03532c7e2995bed2264b396e77c62

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Data Complexity of Query Answering in Description Logics (2006, unknown): “Here, by ‘complex’ we mean that it does not suffice to ask for the instances of concepts, but we need at least to express conjunctive conditions on the extensional level [5–11].”
Bridging the gap between OWL and relational databases (2007, methodology): “Instance checking can be generalized to answering conjunctive queries over DL knowledge bases [10, 12].”
The DL-Lite Family and Relations (2009, methodology): “As follows from the results of Ortiz et al. (2006) for SHIQ, instance checking (and in fact query answering) for DL-LiteHNbool is in coNP for data complexity, while the results of Hustadt et al. (2005) and Eiter et al. (2008) for Horn-SHIQ imply a polynomial-time upper bound for DL-LiteHFhorn.”
Taming the Infinite Chase: Query Answering under Expressive Relational Constraints (2008, result): “One may imagine the set H in a squid decomposition as the head of a squid, and the set T as a forest of tentacles attached to that head, in a way similar to what is done in (Glimm et al. 2008).”