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.
Thomas Eiter, Carsten Lutz, Magdalena Ortiz, Mantas Simkus