Hybrid Query Answering Over DL Ontologies

ABSTRACT. Query answering over SROIQ TBoxes is an important reasoning task for many modern applications. Unfortunately, due to its high computational complexity, SROIQ reasoners are still not able to cope with datasets containing billions of data. Consequently, application developers often employ provably scalable systems which only support a fragment of SROIQ and which are, hence, most likely incomplete for the given input. However, this notion of completeness is too coarse since it implies that there exists \emph{some} query and \emph{some} dataset for which these systems would miss answers. Nevertheless, there might still be a large number of user queries for which they can compute all the right answers even over SROIQ TBoxes. In the current paper, we investigate whether, given a (ground) query Q over a SROIQ TBox T and a system ans, it is possible to identify in an efficient way if ans is complete for Q,T and every dataset. We give sufficient conditions for (in)completeness and present a hybrid query answering algorithm which uses ans when it is complete, otherwise it falls back to a fully-fledged SROIQ reasoner. However, even in the latter case, our algorithm still exploits ans as much as possible in order to reduce the search space of the SROIQ reasoner. Finally, we have implemented our approach using a concrete system ans and SROIQ reasoner obtaining encouraging results.