Query answering in the horn fragments of the description logics SHOIQ and SROIQ

Abstract

The high computational complexity of the expressive Description Logics (DLs) that underlie the OWL standard has motivated the study of their Horn fragments, which are usually tractable in data complexity and can also have lower combined complexity, particularly for query answering. In this paper we provide algorithms for answering conjunctive 2-way regular path queries (2CRPQs), a non-trivial generalization of plain conjunctive queries, in the Horn fragments of the DLs SHOIQ and SROIQ underlying OWL 1 and OWL 2. We show that the combined complexity of the problem is ExpTime-complete for Horn-SHOIQ and 2ExpTime- complete for the more expressive Horn-SROIQ, but is PTime-complete in data complexity for both. In contrast, even decidability of plain conjunctive queries is still open for full SHOIQ and SROIQ. These are the first completeness results for query answering in DLs with inverses, nominals, and counting, and show that for the considered logics the problem is not more expensive than standard reasoning.