Conjunctive queries play an important role as an expressive query language
for Description Logics (DLs). Although modern DLs usually provide for
transitive roles, conjunctive query answering over DL knowledge bases is only
poorly understood if transitive roles are admitted in the query. In this paper,
we consider unions of conjunctive queries over knowledge bases formulated in
the prominent DL SHIQ and allow transitive roles in both the query and the
knowledge base. We show decidability of query answering in this setting and
establish two tight complexity bounds: regarding combined complexity, we prove
that there is a deterministic algorithm for query answering that needs time
single exponential in the size of the KB and double exponential in the size of
the query, which is optimal. Regarding data complexity, we prove containment in
co-NP.

本文研究 DL 中具有传递性角色的联接查询的可决定性和复杂度问题，并证明了在 SHIQ 中允许传递性角色的联接查询有一个完美的单指数时间算法及共 NP 复杂性。

SHIQ 描述逻辑的联合查询回答

Conjunctive Query Answering for the Description Logic SHIQ

Querying over disjunctive ASP with functions is a highly undecidable task in
general. In this paper we focus on disjunctive logic programs with stratified
negation and functions under the stable model semantics (ASP^{fs}). We show
that query answering in this setting is decidable, if the query is finitely
recursive (ASP^{fs}_{fr}). Our proof yields also an effective method for query
evaluation. It is done by extending the magic set technique to ASP^{fs}_{fr}.
We show that the magic-set rewritten program is query equivalent to the
original one (under both brave and cautious reasoning). Moreover, we prove that
the rewritten program is also finitely ground, implying that it is decidable.
Importantly, finitely ground programs are evaluable using existing ASP solvers,
making the class of ASP^{fs}_{fr} queries usable in practice.

该研究论文探讨了具有分层否定和函数的分离逻辑编程的可询问性，并介绍了一种有效的查询评估方法 —— 将魔法集技术扩展到该环境下，并证明了重写程序与原始程序等效。同时，证明了重写程序也是可评估的，这使得该类查询在实践中有用。