Towards Practical Query Answering for Horn-SHIQ.
Thomas Eiter, Magdalena Ortiz, Mantas Šimkus, Trung-Kien Tran, Guohui Xiao · VUBIR (Vrije Universiteit Brussel) · 2012
Query answering has become a prominent reasoning task in Description Logics. This is witnessed not only by the high number of publications on the topic in the last decade, but also by the increasing number of query answering engines. A number of systems provide full conjunctive query (CQ) answering capabilities, including [1, 23, 25, 4, 11]. A common feature of these approaches is that they rely on existing technologies for relational or deductive databases. They focus on lightweight DLs like DL-Lite and EL, and they use query rewriting to reduce the problem of answering a query over a DL ontology to a database query evaluation problem. For more expressive DLs that are not tractable in combined complexity, however, CQs (with the complete first-order semantics) are not yet supported by current reasoning engines. A range of algorithms has been designed, but they serve for theoretical purposes such as showing complexity bounds and are not amenable to practical implementation. The only exception is the rewriting algorithm implemented in the REQUIEM system, which covers ELHI [23], an expressive extension of EL for which standard reasoning is EXPTIME-hard. In this paper, we contribute to the development of practical query answering systems beyond DL-Lite and EL. We consider Horn-SHIQ, the Horn fragment of the popular DL SHIQ that underlies OWL DL. It combines all the expressive features of DL-Lite and EL, and simultaneously extends them with transitive roles, qualified number restrictions and some universal quantification. Standard reasoning tasks in Horn-SHIQ are already EXPTIME-hard in combined complexity but, due to the absence of disjunction, they are polynomial in data complexity. Since in Horn-SHIQ models are significantly more complex than in DL-Lite and (most dialects of) EL, extending existing query rewriting techniques is not straightforward. The main contribution of this paper is a query answering method for Horn-SHIQ that appears to be promising for practicable systems, as confirmed by the experimental evaluation of a prototype implementation. – The core of the method is a novel query rewriting technique which transforms an input query q into a union Q of CQs (a UCQ) such that the answers of q over an ontology O = 〈T ,A〉 with TBox T and ABox A coincide with the answers over A