Revisiting Conjunctive Query Entailment for S

We clarify the complexity of answering unions of conjunctive queries over knowledge bases formulated in the description logic S, the extension of ALC with transitive roles. Contrary to what existing partial results suggested, we show that the problem is, in fact, 2ExpTime-complete; hardness already holds in the presence of two transitive roles and for Boolean conjunctive queries. We complement this result by showing that the problem remains in coNExpTime when the input query is rooted or is restricted to use at most one transitive role (but may use arbitrarily many non-transitive roles).

Authors

• Yazmín Ibáñez-García
• Jean Christoph Jung TU Dortmund University
• Vincent Michielini University of Bordeaux
• Filip Murlak University of Warsaw

Keywords

No keywords are indexed for this paper.