Conjunctive queries play an important role as an expressive query language for Description Logics (DLs). Although modern DL reasoners usually provide highly optimised reasoning support for very expressive DLs, the standard implementations only provide support for restricted classes of conjunctive queries. One reason for the restrictions is that, to the best of our knowledge, it was not even known whether the problem of conjunctive query entailment is decidable in very expressive DLs such as SHIQ, SHOQ, or SHOIQ. In this talk, we show how we can devise a decision procedure for conjunctive query entailment in SHIQ and SHOQ. The devised algorithms run in deterministic time single exponential in the size of the KB and double exponential in the size of the query, which is known to be optimal for SHIQ. We further devise a non-deterministic decision procedure for SHIQ, which shows that the data complexity of the problem is co-NP-complete.
