期刊名称：Journal of Automation, Mobile Robotics & Intelligent Systems (JAMRIS)
印刷版ISSN：1897-8649
电子版ISSN：2080-2145
出版年度：2008
卷号：31
页码：157-204
出版社：Industrial Research Inst. for Automation and Measurements, Warsaw
摘要：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.
