AAAI Publications, Twenty-First International Joint Conference on Artificial Intelligence

Font Size: 
Query Answering in Description Logics with Transitive Roles
Thomas Eiter, Carsten Lutz, Magdalena Ortiz, Mantas Simkus

Last modified: 2009-06-25


We study the computational complexity of conjunctive query answering w.r.t. ontologies formulated in fragments of the description logic SHIQ. Our main result is the identification of two new sources of complexity: the combination of transitive roles and role hierarchies which results in 2ExpTime-hardness, and transitive roles alone which result in coNExpTime-hardness. These bounds complement the existing result that inverse roles make query answering in SHIQ 2ExpTime-hard.  We also show that conjunctive query answering with transitive roles, but without inverse roles and role hierarchies, remains in ExpTime if the ABox is tree-shaped.


Description Logics and Ontologies, Computational Complexity of Reasoning, Knowledge Representation

Full Text: PDF