Query Answering in the Horn Fragments of the Description Logics SHOIQ and SROIQ

As more and more application areas require higher scalability, the study of fragments of expressive The high computational complexity of the expressive DLs with better computational properties has become an Description Logics (DLs) that underlie the important area of research. OWL standard has motivated the study of their Horn fragments of DLs, which are obtained by restricting Horn fragments, which are usually tractable in data the syntax of a DL in such a way that disjunction is not complexity and can also have lower combined complexity, expressible, were first considered in [Hustadt et al., 2005] particularly for query answering. In this paper as expressive fragments with tractable data complexity (see we provide algorithms for answering conjunctive also [Krötzsch et al., 2007]). It was later identified that they 2-way regular path queries (2CRPQs), a nontrivial can also exhibit lower combined complexity when it comes generalization of plain conjunctive queries, to query answering. Indeed, answering conjunctive queries in the Horn fragments of the DLs SHOIQ and (CQs), a kind of database-inspired queries that have become SROIQ underlying OWL 1 and OWL 2. We show the standard for querying DLs, is in ExpTime for the Horn that the combined complexity of the problem is ExpTime-complete fragment of the prominent SHIQ [Eiter et al., 2008], while it for Horn-SHOIQ and 2ExpTimecomplete is already 2ExpTime-hard for quite restricted (non Horn) fragments for the more expressive Horn-SROIQ, of SHIQ, like ALCI [Lutz, 2008] and SH [Eiter et but is PTime-complete in data complexity for both.