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 2-EXPTIMEhardness, and transitive roles alone which result in CO-NEXPTIME-hardness. These bounds complement the existing result that inverse roles make query answering in SHIQ 2-EXPTIME-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.

Authors

• Thomas Eiter
• Carsten Lutz
• Magdalena Ortiz
• Mantas Simkus

Keywords

No keywords are indexed for this paper.