A key application of Description-Logic based ontologies is Ontology-Based Data Access (OBDA) [9]. In such scenarios a TBox is used to describe the schema of the application while answers to conjunctive queries re ect both the schema and the data. Unfortunately, it is well-known that conjunctive query (CQ) answering over expressive Description Logics (DLs) is of very high computational complexity [7, 5]. The need for e cient query answering has motivated the development of (families of) lightweight ontology languages, such as the DL-Lite family [3, 2]. Query answering in these languages is usually performed via a technique called query rewriting. According to this technique, a query and a DL-Lite ontology are transformed into a union of conjunctive queries (often called a UCQ rewriting ) such that, the answers of the union of conjunctive queries over the input data and discarding the ontology are precisely the answers of the original query over the data and the ontology. In the last years a large number of di erent algorithms and systems for computing rewritings for DL-Lite ontologies has been presented. Examples of such systems are QuOnto [1], Requiem [8], Presto [10], Nyaya [6], and Rapid [4]. Roughly speaking, all systems apply a set of equivalence-preserving transformations over the input query and TBox producing new queries until a x-point is reached. In several previous approaches [3, 8, 6] this process is largely bruteforce, in the sense that the algorithm iterates over the currently computed set of queries, over the atoms of the query and over the TBox axioms, and if some of the rules of the algorithm applies then a new query is generated. It was shown recently that given a query q, a TBox T and an atom of q, a UCQ rewriting for q; T can be computed by rst computing a UCQ rewriting u for query q n f g (i.e., q without the atom ) and then `extending' this rewriting with additional information from T that only regards [11]. Using this idea we present a novel algorithm for computing a UCQ rewriting for queries over DL-LiteR-TBoxes1 incrementally. Roughly speaking, given a query q with atoms 1; : : : ; n the algorithm rst computes UCQ rewritings ui for `special' queries that contain only a single body atom i. Finally, these UCQs are iteratively `combined' until a UCQ rewriting for the input query has been computed. Compared to several previous approaches our algorithm is signi cantly guided. At each step all the knowledge of T that regards a single atom i is `materialised'
1 DL-LiteR is a popular member of the DL-Lite family [
Furthermore, to further increase the e ciency of the algorithm, we additionally present a list of optimisations which considerably decrease its computation time. Many of the optimisations are intended to increase the e ciency of our nal backward-subsumption (redundancy elimination) algorithm.
Finally, we have implemented the proposed algorithm and optimisations and
we have compared them against several available state-of-the-art systems. Our
results show that computing a UCQ rewriting incrementally is in the vast
majority of cases more e cient than all systems. More precisely, our algorithm requires
less time and computes the smallest UCQ rewriting in nearly all ontologies.
Interestingly, when compared to the original DL-Lite algorithm [
An extended version of the paper with detailed proofs of correctness can be found online.2 2
Let C, R, and I be countable, pairwise disjoint sets of atomic concepts, atomic roles, and individuals. A DL-LiteR-role is either an atomic role P or its inverse P . DL-LiteR-concepts are de ned inductively by the grammar B := A j 9R, where A 2 C and R is a DL-LiteR-role. A DL-LiteR-TBox is a nite set of axioms of the form B1 v B2 or B1 u B2 v ?, with B(i) DL-LiteR-concepts and ? the bottom concept that is empty in all interpretations, or of the form R1 v R2 with R(i) DL-LiteR-roles. An ABox is a nite set of assertions of the form A(c) or P (c; d) for A 2 C, P 2 R and c; d 2 I. A DL-LiteR-ontology O = T [ A consists of a TBox and an ABox.
A conjunctive query (CQ) q is an expression of the form f~x j f 1; : : : ; mgg
where f 1; : : : ; mg is called the body of the query with i a concept or role
atom of the form A(t) or R(t; t0) (for t; t0 function-free terms and A; R atomic)
and ~x = (x1; : : : ; xn) is a tuple of variables called the distinguished (or answer)
variables, each appearing in at-least some atom i. The remaining variables of q
are called undistinguished. We use var(q) to denote all the variables appearing in
q and avar(q) to denote all its distinguished variables. We often abuse notation
and use q to refer to the set of its atoms, i.e., f 1; : : : ; mg. Hence, for an
atom and q a CQ, q [ f g denotes a new CQ that consists of the atoms of q
plus and the same distinguished variables as q. For the rest of the paper, and
without loss of generality, we will assume that queries are connected [
Given CQs q1; q2 with distinguished variables ~x and ~y, respectively, we say that q2 subsumes q1, if there exists a substitution from the variables of q2 to the 2 http://image.ece.ntua.gr/~gstoil/main.pdf variables of q1 such that the set [fQ(~y)g [ q2] is a subset of the set fQ(~x)g [ q1, where Q is a predicate of the same arity as ~x and ~y that does not appear in q1 or q2. Finally, for a UCQ u and CQ q, we say that q is redundant in u if another query in u exists that subsumes q; otherwise it is called non-redundant.
For a DL-LiteR-TBox, a UCQ rewriting u for q; T can be computed using the
perfect reformulation algorithm (PerfectRef) [
Let G = hU; Ei be a graph. For a; b 2 U we say that b is reachable from a, written a G b, if c0; : : : ; cn with n 0 exist where c0 = a, cn = b and hci; ci+1i 2 E for each 0 i < n. An element c 2 U is called top in G if for each c0 2 U we have c G c0. 3
It has been shown in [
Example 1. Consider the following DL-LiteR-TBox and CQ:
T = fProfessor v 9teaches; 9teaches v Studentg q = fx j fteaches(x; y)gg
and the UCQ rewriting u = fq; q1g where q1 = fx j fProfessor(x)gg for q; T
computed using PerfectRef. Assume now, that q is extended in order to retrieve
only those individuals that teach students|that is, q is extended to q0 = fx j
fteaches(x; y); Student(y)gg. In order to compute a UCQ rewriting for q0; T the
algorithm presented in [
First, it constructs the query q = fy j fStudent(y)gg that consists of the
single body atom and its distinguished variables are the common variables
between and q. Then, a UCQ rewriting u = fq ; q0 g for q ; T is computed
using PerfectRef, where q0 = fy j fteaches(z; y)gg for z a fresh variable.
Subsequently, the algorithm initialises an empty UCQ u0 and iterates over the sets u
and u constructing and adding new queries to u0 as follows:
1. The atoms of q are added to q; hence, query q0 is added to u0.
2. The atoms of q0 are added to q; hence, query q10 = q [ fteaches(z; y)g is
added to u0.
3. The algorithm identi es that the body atom of q0 can be uni ed into the
body of q; the result (i.e., CQ q) is added to u0. Additionally, since after this
uni cation CQ q is part of the target UCQ u0 all queries that are produced
in u due to q also need to be added; hence, query q1 is also added to u0.
4. No query is generated from q1 and q (or q0 ) since q1 does not contain all
the distinguished variables of q (or q0 ), i.e., avar(q ) * var(q1).
It can be veri ed that the set u0 = fq0; q10; q; q1g is a UCQ rewriting for q0; T . }
Intuitively, the above approach is possible because the process of rewriting is
to a large extend `local' with respect to the atoms of a query. For example,
the application of reformulation on some query atom is independent from the
other atoms of the query, hence the information from T that regards can be
materialised and then used to extend the queries in u. The only exception is the
reduction step where two di erent atoms are uni ed. This step was introduced
in [
In Example 1, for q0 and q we have mergeCQs(q0 ; q) = fz 7! xg, hence q as well as all queries that are produced in u due to q (i.e., q1) are added to the result. To accomplish the latter, however, the algorithm needs to be aware of the dependencies of the queries in the given (pre-computed) UCQ u. To capture this information, instead of a UCQ, the algorithm accepts as input a graph G of queries which encodes the dependencies between the queries in u. De nition 1. Let q be a CQ and let T be a DL-LiteR-TBox. A rewriting graph for q; T is a directed graph G = hu; H; mi, where u is a UCQ rewriting for q; T , H is a binary relation over u, and each node qi 2 u is labelled with a substitution m(qi). Moreover, G satis es the following properties: (i) If hq1; q2i 2 H, then q2 is produced from q1 by the application of a reformulation or reduction step, and (ii) for each hq1; q2i 2 H if q2 is produced by a reformulation step, then m(q2) = m(q1), while if it is produced by a reduction step with the mgu, then m(q2) = m(q1) .
Algorithm 1 IncrementalRew(q; T )
A rewriting graph for a query q over a DL-LiteR-TBox can be easily
computed by a straightforward extension of the PerfectRef algorithm, which we call
ex-PerfectRef. The details of the algorithm have been presented in [
The previous results show that a rewriting for a given ( xed) query over some
TBox can be computed incrementally by considering one of its atoms at a time.
For example, for query q0 = fx j fteaches(x; y); Student(y)gg of Example 1 we
can st select atom 1 := teaches(x; y) compute a UCQ rewriting u 1 for q 1 =
fx j fteaches(x; y)gg (which consists of the set fq; q1g of the example) and then
pick the last atom, compute a UCQ u 2 for q 2 := fy j fStudent(y)gg and nally
extend u 1 with atoms of queries from u 2 as shown in Example 1. In general,
given a ( xed) query one can pick one of its atoms, compute a rewriting (graph)
for it, and then iteratively add the rest of its atoms by extending the previously
computed rewriting. When all the atoms have been processed a UCQ rewriting
for the given query would have been computed. In contrast to our previous work
[
This idea is illustrated in Algorithm 1. The algorithm rst selects some atom
such that some of its variables appear as distinguished variables in q (line 2)
and computes a rewriting graph Gi for the query fvar( ) \ avar(q) j f gg (line
4). Hence, initially a rewriting graph for a query that contains only atom of
q, variables cv := var( ) of q and distinguished variables av := var( ) \ avar(q)
of q have been computed. Then, the algorithm selects one-by-one the remaining
atoms and extends the previously computed rewriting graph (lines 5{14). More
Algorithm 2 joinGraphs(qh; q ; G0; G; G ; av; jv)
input: Rewriting graphs G0 = hu0; H0; m0i, G = hu; H; mi and G
and two sets of variables jv and av.
= hu ; H ; m i
precisely, at the beginning of the i-th iteration the algorithm has computed a
rewriting graph Gi for a query qi that contains i atoms of q, cv contains the
variables of q that appear in qi, while av the distinguished variables of q that
appear in qi. Hence, it picks another atom 0 such that some of its variables also
appear in cv (line 6), it adds the variables of 0 that are distinguished in q to
av (line 8), it computes a rewriting graph G for the query fvar( 0) \ cv j f 0gg
(line 9) and then, it joins G with G 0 using function joinGraphs (line 12) storing
the result to G0. Finally, after processing all atoms of the query it uses the
well-known redundancy elimination algorithm proposed in [
Function joinGraphs is shown in Algorithm 2. Intuitively, this algorithm computes the Cartesian product of the two input rewriting graphs (modulo cases where queries should be merged). The intuition is that if hq; q0i 2 G (i.e., q0 is produced by q) and q is a vertex in G , then the same step would also be applicable to query q [ q |that is, q [ q will produce the CQ q0 [ q (for-loop in line 13). Similarly, for q a vertex in G and hq ; q0 i 2 G (for-loop in line 10). In addition the algorithm also checks whether a CQ from G can be merged into some CQ qh from G (line 4). If this is the case then the queries that have been produced in G due to qh are copied to the new rewriting graph (see lines 7{9).
Note that the graphs can be cyclic but standard graph-traversal algorithms can be used to guarantee termination.
Example 2. Consider the TBox T and CQ q0 = fx j fteaches(x; y); Student(y)gg of Example 1. A run of Algorithm 1 is the following:
(1.) First, it selects atom s.t. var( ) \ avar(q0) 6= ; (line 2). The only atom that satis es this condition is = teaches(x; y). Subsequently, algorithm ex-PerfectRef is executed for q = fx j fteaches(x; y)gg and T . This creates the rewriting graph Gi = hu; H; mi, where u = fq; q1g is as de ned in Example 1, H = fhq; q1ig and m(q) = m(q1) = ; (line 4). At this point cv = fx; yg and av = fxg.
(2.) Next, the algorithm picks another atom 0 of q0 s.t. var( 0) \ cv 6= ;. One such atom is 0 = Student(y). Hence, using again algorithm ex-PerfectRef it computes for q = fy j fStudent(y)gg and T (line 9) the rewriting graph G = hu ; H ; m i, where u = fq ; q0 g is as de ned in Example 1, H = fhq ; q0 ig and m(q ) = m(q0 ) = ;. Subsequently, it calls algorithm joinGraphs with parameters q, q , G0, Gi (as computed in the previous step), G and the variable sets av = fxg and jv = fyg in order for G0 to re ect the new graph. This algorithm proceeds as follows: rst, it selects q from Gi and q from G and creates the query q0 = fx j fteaches(x; y); Student(y)g (by adding atoms of q to q) (line 3). Then, it proceeds to the child of q , (i.e., to q0 ) and it creates the CQ q10 = fx j fteaches(x; y); teaches(z; y)gg (by adding atoms of q0 to q) (line 11). Moreover, it also adds the relation hq0; q10i to G0. Subsequently, a recursive call to joinGraphs is made with rst two parameters q and q0 . In this call, in line 4, mergeCQs(q0 ; q) returns fz 7! xg, hence tuples hq10; qi and hq; q1i are added to G0, and m(q) = m(q1) = fz 7! xg. (Note that q = q and q1 = q1) Then, the algorithm returns from the recursive call and proceeds in line 13 to the child of q (i.e., q1) but canBeJoined(q1; m(q1); jv) returns false for the reasons explained in Example 1 item 4. Hence, the algorithm terminates and we have G0 = hu0; H0; m0i where u0 = fq0; q10; q; q1g (as de ned in Example 1), H0 = fhq0; q10i; hq10; qihq; q1ig and m(q0) = m(q10) = ;, m(q) = m(q1) = fz 7! xg. } 5 5.1
As explained earlier, Algorithm 2 computes the cartesian product between two rewriting graphs. The structure of the computed graph is important while processing the atoms of the query, however, it is not important after processing the last atom of the input query. Consequently, in the last iteration, Algorithm 1 can call a simpli ed version of Algorithm 2 that constructs a set of CQs rather than a rewriting graph. Algorithm 3 depicts the simpli ed algorithm. Roughly speaking, it is obtained from Algorithm 2 by, removing the for-loop starting in line 13, computing for the last selected atom a set u rather than a rewriting graph G , and adding the computed queries to a UCQ rather than a graph. 5.2
In line 15 Algorithm 1 applies the well-known redundancy elimination algorithm
from [
In the last iteration and before calling Algorithm 3 it executes the standard subsumption checking algorithm over G and stores all subsumption relations. Note that, the size of G at this point is expected to be signi cantly smaller than that of the nal UCQ, hence the algorithm should behave well in practice. Then, when executing Algorithm 3 it identi es redundant queries as follows: { In line 10, it adds a query fav j q0g to U only if for q the subsumer of q0 (if it exists) fav j qg is not already in U . { Let q selected in line 4. If a subsumer q0 of q exists such that, either fav j q0g is already in U , or q0 q, m(q0) = m(q), and canBeJoined(q0; m(q0); jv) = true, then the algorithm `skips' q|that is, it adds each q00 such that hq; q00i 2 G to Q and it continues with the next CQ.
Also, Algorithm 3 is modi ed to identify non-redundant queries as follows: { At the beginning it initialises an empty set N R of non-redundant queries. { In line 10, if fav j q0g = fav j q0g and q0 is non-redundant in u it adds fav j q0g to N R. { In line 6, it adds fav j q [ (q )m(q)g to N R if none of the predicates in q appear in any CQ in u and if for each q0 2 u we have mergeCQs(q0 ; q) = ;. { Finally, it returns both the UCQ U and the set N R.
Subsequently, the returned set N R is used by method removeRedundant as
follows: All queries that are in the set N R are excluded from redundancy checking.
We have implemented Algorithms 1{3 in a prototype tool called IQAROS3 and
have compared it against PerfectRef [
Table 1 presents the results for each system, where the columns annotated as
\Size of UCQ" present the size of the computed UCQ before the nal redundancy
elimination (after redundancy elimination all systems return the same UCQ, as
the ones reported in [
First we compare the di erent versions of IQAROS. We observe that the size of the computed UCQs decreases from Inc1 to Inc3. The di erence between Inc1 and Inc2 is justi ed by the fact that the latter uses the simpler algorithm (Algorithm 3) which does not compute the Cartesian product between the graphs. The bene ts of using this algorithm are also re ected in the computation times of Inc2 compared to Inc1. Inc3 computes the smallest UCQ of the three versions due to its techniques for eliminating redundant queries. Regarding execution time Inc3 performs similarly to Inc2 and sometimes slightly worse, due to the overhead of implementing the various optimisations. However, when considering the total time the bene ts of the optimisations become apparent. Inc3 is significantly faster in ontologies A and AX and is actually the only con guration of IQAROS that can process query 5 in AX in only 27 seconds. This is heavily due to the optimisation of tracking non-redundant queries.
Compared to PerfectRef, and Nyaya, all versions of IQAROS (even Inc1) are much faster, in some cases even for several orders of a magnitude. Moreover, Inc2 and Inc3 compute signi cantly smaller UCQs. Since in their core all these systems are based on the same approach for materialising knowledge from T , we concluded that this improvement is due to the incremental rewriting strategy that provides a much more guided and localised strategy compared to the blind brute-force application of the reformulation and reduction steps. Also Nyaya supports n-arry predicates and its factorisation step is signi cantly more involved that our merge function.
Compared to Rapid, Inc3 (the fastest of the three con gurations) computes similarly small UCQs with some small exceptions (either against or in favor) in queries 3{5 in ontology P5X, in queries 1 and 3 in ontology A and in queries 1, 2, 4 and 5 in ontology AX. Moreover, Rapid is notably faster5 only in queries 4 and 5 in P5 and 5 in S and A. However, even in these cases the di erence between the systems is rather marginal as it never exceeds 253 milliseconds. In all the other cases Inc3 is faster with most notable cases queries 4 and 5 in P5X and 2{5 in AX. Moreover, we can also see that redundancy elimination algorithm of Inc3 is much more e cient than that of Rapid with again notable case query 5 in ontology AX. Once more, this is justi ed by the optimisations used in Inc3. 5 We consider a system to be `notably faster' if it is faster for more than 20 milliseconds.
In the current paper we presented a novel algorithm for query rewriting over DL-LiteR ontologies. The algorithm is based on a novel approach that processes each atom separately and then combines the results to compute a nal UCQ rewriting. It is signi cantly guided and our experimental evaluation showed that it is generally faster than all available systems known to us.
We feel that our techniques have several important practical and theoretical
consequences and give opportunities for future work. First, we strongly feel that
this approach can be used in other First-Order rewritable languages, like
LinearDatalog [
Acknowledgments Work supported by project EUscreen (ECP-2008-DILI518002) within EU's eContentplus Programme. Giorgos Stoilos is supported by a Marie Curie FP7-Reintegration-Grants within European Union's Seventh Framework Programme (FP7/2007-2013) under REA grant agreement 303914.