Query Answering in Description Logics with Transitive Roles

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