We clarify the complexity of answering unions of conjunctive queries over knowledge bases formulated in the description logic $\mathcal S$, the extension of $\mathcal{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).

翻译：我们阐明了在描述逻辑$\mathcal S$（即$\mathcal{ALC}$扩展了传递角色）中构建的知识库上回答合取查询并集的复杂度问题。与现有部分研究结果所暗示的不同，我们证明该问题实际上是2ExpTime完全的；仅需两个传递角色及布尔合取查询即可导致问题困难性。我们进一步补充证明：当输入查询为根查询或限制至多使用一个传递角色（但可任意使用多个非传递角色）时，该问题仍保持在coNExpTime复杂度类中。