Technical Report, Faculty of Computer Science, Free University of Bozen-Bolzano. Technical report 2005. Also available as CORR technical report at https://arxiv.org/abs/cs/0507059.
In [Levy&RoussetAIJ'98] the authors give an algorithm for answering conjunctive queries over ALCN R knowledge bases which is coNP in data complexity. Their technique is based on the tableau technique for checking satisfiability in ALCN R presented in [Buchheit&al.JAIR'93]. In their algorithm, the blocking conditions of [Buchheit&al.JAIR'93] are weakened in such a way that the set of models their algorithm yields suffices to check query entailment. The algorithm we propose consists on applying a similar technique to the tableaux algorithm in [Horrocks&al.CADE'00], which decides the satisfiability of SHIQ knowledge bases. As a result we have an algorithm for answering conjunctive queries over SHIQ knowledge bases that is also coNP in terms of data complexity.
@techreport{TR-FUB-2005-07,
title = "Data Complexity of Answering Conjunctive Queries over SHIQ
Knowledge Bases",
year = "2005",
author = "Magdalena Ortiz and Diego Calvanese and Thomas Eiter and
Enrico Franconi",
institution = "Faculty of Computer Science, Free University of
Bozen-Bolzano",
note = "Also available as CORR technical report at
https://arxiv.org/abs/cs/0507059",
}