Query Answering in the Horn Fragments of the Description Logics SHOIQ and SROIQ
Magdalena Ortiz, Sebastian Rudolph and Mantas Simkus
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 use a finite representation of a universal model of a knowledge base to answer queries without explicitly building a model, by a combination of query partitioning and tree automata techniques. We show that in combined complexity of the problem is EXPTIME-complete for Horn-SHOIQ and 2-EXPTIME-complete for the more expressive Horn-SROIQ, but is P-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.