Conjunctive Query Answering for the Description Logic SHIQ

Abstract

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.

References in corpus (2)

• Complexity Results and Practical Algorithms for Logics in Knowledge Representation
• Reasoning with Individuals for the Description Logic SHIQ

Cited by in corpus (8)

• The DL-Lite Family and Relations
• Nominals, Inverses, Counting, and Conjunctive Queries or: Why Infinity is your Friend!
• Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies
• Data-Complexity of the Two-Variable Fragment with Counting Quantifiers
• Type-elimination-based reasoning for the description logic SHIQbs using decision diagrams and disjunctive datalog
• Completeness Guarantees for Incomplete Ontology Reasoners: Theory and Practice
• A Practical Acyclicity Notion for Query Answering over Horn-SRIQ Ontologies
• Efficient Description Logic Reasoning in Prolog: The DLog system