Rewriting the input TBox T (and query Q) into a datalog program, called T rewriting ((Q,T )-rewriting ), is a prominent approach to ontology-based data access [1]. It was used as early as the KAON2 system [5] and it currently consists of (perhaps) the standard approach to answering queries over ontologies expressed in the languages DL-Lite [2, 12] and E LHI [8, 16]. Apart from computing a rewriting, a problem that has been proven very di cult is how to subsequently (e ectively) evaluate it over the data. In many cases, due to its size and/or complexity, additional techniques need to be devised [11, 9, 10]. Unfortunately, all of them have so far been applied only on DL-Lite while for more expressive languages, apart from the work in [3], to the best of our knowledge, no other integrated query answering system has been reported or evaluated with large and complex ontologies. An interesting observation is that T -rewritings are usually of a particular form|that is, they can be translated back into an RL TBox [14].1 Hence, scalable RL system, like OWLim, can be used to evaluate them over the data. More precisely, it was shown how, given a SROIQ TBox T and an RL system ans, a rewriting of T can be used to compute a set of axioms R (called repair ) such that for every CQ Q with only distinguished variables (i.e., SPARQL CQs) and every ABox A we have cert(Q; T [ A) ans(Q; T [ R [ A). That is, after repairing, ans is indistinguishable from a SROIQ reasoner w.r.t. SPARQL CQs. Although, the experimental results in [14] provided with encouraging results, these were quite preliminary. First, the implementation used an arguably obsolete system (Requiem) and had no optimisations. Second, the evaluation was based on LUBM (an arguably trivial TBox) and a small fragment of Galen. Hence, it was unclear whether repairing can be applied to large and complex TBoxes. Third, the approach could only handle SPARQL CQs. In the current paper we attempt to extensively study repairing as an approach to OBDA over expressive TBoxes. First, we propose several optimisations and re nements to the rst prototype in order to handle large and complex TBoxes. Second, we show how arbitrary queries can be supported. Third, we perform an extensive experimental evaluation which showed that we can handle very large and complex TBoxes (e.g., Galen, GO, Fly) and answer arbitrary CQs over one of them (Fly) within milliseconds. This is an extended abstract of paper [13].
Let T be a TBox and let ans be an RL system. Roughly speaking, a repair R of ans for T is computed by rst computing a T -rewriting (Rew) for T , then removing from Rew the parts that ans can already handle, and nally, minimising the resulting set. For example, if T = fA v 9R; 9R v Bg, then Rew = fA(x) ! B(x); R(x; y) ! B(x)g is a T -rewriting of T , while R = fA v Bg is the desirable repair for ans. We call Repair(T ) the overall procedure.
Compared to [
Let Q be an arbitrary CQ with query predicate Q, let T be a TBox, and let RewD ] RewQ be a (Q; T )-rewriting (RewD is a datalog program not mentioning Q and RewQ a UCQ that mentions Q). Since RewD does not mention Q it captures only ground entialments of T over some A. But, after repairing, ans is complete w.r.t. all ground entailments for any A; hence cert(Q; T [ A) ans(RewQ; T [ Repair(T ) [ A). The following summarises our approach: 1. Compute a repair R of T for ans using procedure Repair. 2. Load the dataset A, the input TBox T , and the repair R to ans. 3. For a CQ Q, if Q is SPARQL then evaluated it over ans; otherwise compute a (Q; T )-rewriting RewD ] RewQ and evaluate RewQ over ans.
Note that most steps, i.e., steps 1 and 2, can be done only once as a pre-processing (changes in A can be handled incrementally). 4
We have implemented a prototype ontology repair and query answering tool
called Hydrowl.2 The tool uses Rapid [
Using Hydrowl we managed to compute repairs for 151 out of the 152
ontologies of our dataset, which contained some large and highly complex ones. In the
vast majority of cases a repair could be computed in less than a second, only a
handfull required up to a few minutes, and only the very large ones several
minutes; Table 1 presents results for the latter. Despite their size and complexity we
see that we can compute repairs for them in a reasonable amount of time (recall
this is usually done only once). Actually, if we discard a very expensive
minimisation step, then we can compute some (non-minimal) repair very e ciently while
its size is not considerably larger than the minimal one (see Table 1 numbers in
parenthesis). The system in [
Next, Table 2 presents loading experiments to OWLim using UOBM (1 to 20 universities) and Fly (ABox multiplied up to 5 times). As can be seen, the overhead introduced by repairing is signi cantly noticeable only in Fly, mostly due to the size of the computed repair (R), however, recall that loading is usually performed once. In Fly we have also loaded the non-minimal repair (R ) and as it turns out there is no signi cant di erence compared to the minimal one.
The Fly ontology comes with 4 non-SPARQL queries. Table 3 presents the results of our technique from Section 3. As we can see in most cases we were able to compute and evaluate a rewriting almost instantaneously. This greatly outperformes previous approaches on Fly [17, 18] which require several seconds per query. The good behaviour of our approach can be attributed to the fact that most hard work is pushed to a pre-processing step while RewQ, the only thing computed on-line, is usually small and of simple structure. 17. Yujiao Zhou, Bernardo Cuenca Grau, Ian Horrocks, Zhe Wu, and Jay Banerjee.
Making the most of your triple store: Query answering in OWL 2 using an RL reasoner. In Proc, WWW 2013, pages 1569{1580, 2013. 18. Yujiao Zhou, Yavor Nenov, Bernardo Cuenca Grau, and Ian Horrocks. Complete query answering over horn ontologies using a triple store. In Proc. of the 12th International Semantic Web Conference (ISWC). Springer LNCS, 2013.