It has recently been demonstrated in [10] that FO-rewritings of ontology-mediated queries can be e ciently computed in practice, in a sound and complete way, when the ontology is formulated in EL and the actual query is an atomic query (AQ). In this paper, we show how to lift this approach, which is based on a decomposed version of backwards chaining, from AQs to (rooted) conjunctive queries (rCQs). While we achieve a polynomial time reduction when the quanti ed parts of the CQ are tree-shaped, a more subtle approach is required in the general case. We conduct experiments based on real-world ontologies which show promising results.
One of the most important technical tools in ontology-mediated querying is query
rewriting : reformulate a given ontology-mediated query (OMQ) in an
equivalencepreserving way in a query language that is supported by a database system used
to store the data. Since SQL is the dominating query language in conventional
database systems, rewriting into SQL and into rst-order logic (FO) as its logical
core has attracted particularly much attention [
In this paper, we focus on the description logic EL and aim to push the
frontier of e ciently computing FO-rewritings of OMQs from atomic queries
(AQs) to conjunctive queries (CQs). As usual, we use (L; Q) to denote the OMQ
language that consists of all OMQs (T ; ; q) where T is a TBox formulated in
the description logic L and q is a query formulated in the query language Q (and
is an ABox signature). It has been shown in [
We intend to lift this approach from AQs to CQs. Note that it was shown
in [
T = f9r:A v A; 9s:> v Ag = fA; r; sg q(x) = 9y (A(x) ^ s(x; y)) then Q = (T ; ; q) is FO-rewritable into 9y s(x; y), but the only AQ A(x) that occurs in q is not FO-rewritable. In fact, a black box reduction does not seem to be possible in general. Thus, we consider mildly restricted forms of CQs and exhibit reductions that are not completely black box, but make certain assumptions on the algorithm used to compute FO-rewritings in (EL; AQ)|all of them satis ed by the decomposed backwards chaining algorithm implemented in Grind.
We rst consider the class of tree-quanti ed CQs (tqCQs) in which the quanti ed parts of the CQ are tree-shaped. In this case, we indeed achieve a black box polynomial time reduction for FO-rewritability. To also transfer actual FO-rewritings from the OMQ constructed in the reduction to the original OMQ, we make the assumption that the rewriting of the former takes the form of a UCQ in which every CQ is tree-shaped and that, in a certain sense made precise in the paper, atoms are never introduced into the rewriting `without a reason'. Both conditions are very natural in the context of backwards chaining and satis ed by the decomposed algorithm.
We then move to rooted CQs (rCQs) in which every quanti ed variable must be reachable from some answer variable (in the query graph). We consider this a mild restriction and expect that almost all queries in practical applications will be rCQs. In the rCQ case, we do not achieve a black box reduction. Instead, we assume that FO-rewritings of the constructed OMQs from (EL; AQ) are obtained from a certain straightforward backwards chaining algorithm or a re nement thereof as implemented in the Grind system. We then show how to combine the construction of (several) OMQs from (EL; AQ), similar to what we have done in the black box reduction in the tqCQ case, with a modi cation of the assumed algorithm to decide FO-rewritability in (EL; rCQ) and to construct actual rewritings. The approach involves exponential blowups, but only in parameters that we expect to be very small in practical cases and that, in particular, only depend on the actual query contained in the OMQ but not on the TBox.
We have implemented our approach in the Grind system and carried out
experiments on ve real-world ontologies with 10 hand-crafted CQs for each. The
average runtimes are between 0.5 and 19 seconds (depending on the ontology),
which we consider reasonably short given that we are dealing with a complex
static analysis problem. For the proofs, see the Appendix of [
We use standard notation for EL-TBoxes (sets of concept inclusions), for ABoxes,
for conjunctive queries (CQs), and for unions thereof (UCQs), see for example [
Unless noted otherwise, we allow equality in CQs, but we assume w.l.o.g. that equality atoms contain only answer variables, and that when x = y is an equality atom in q, then y does not occur in any other atoms in q. Other occurences of equality can be eliminated by identifying variables. With var(q), we denote the set of all variables used in the CQ q and use avar(q) for the set of all answer variables. We do not distinguish between a CQ and the set of atoms in it and associate with each CQ q a directed graph Gq := (var(q); f(x; y) j r(x; y) 2 qg), de ned in the expected way (equality atoms are not re ected). A CQ q is treeshaped if Gq is a directed tree and r(x; y); s(x; y) 2 q implies r = s. A tree CQ (tCQ) is a tree-shaped CQ with the root the only answer variable, and a tree UCQ (tUCQ) is a disjunction of tree CQs. Clearly, every EL concept can be viewed as a tCQ and vice versa, and we will not always distinguish between the two representations. For example, we might write 9r:q to denote an EL concept when q is a tree-shaped CQ. If convenient, we also view a CQ q as an ABox Aq which is obtained from q by dropping equality atoms and then replacing each variable with an individual (not distinguishing answer variables from quanti ed variables). A rooted CQ (rCQ) is a CQ q such that in the undirected graph induced by Gq, every quanti ed variable is reachable from some answer variable. A tree-quanti ed CQ (tqCQ) is an rCQ q such that after removing all atoms r(x; y) with x; y 2 avar(q), we obtain a disjoint union of tCQs. We call these tCQs the tCQs in q.
An ontology-mediated query (OMQ) is a triple Q = (T; ; q) where T is
a TBox, an ABox signature, and q a CQ. The semantics is de ned in the
standard way via certain answers. In particular, we write A j= Q(a) if a is a
certain answer to the OMQ Q on the ABox A; we again refer to [
An OMQ Q = (T ; ; q) is FO-rewritable if there is a rst-order (FO) formula
' such that A j= Q(a) i A j= '(a) for all -ABoxes A. In this case, ' is
an FO-rewriting of Q. When ' happens to be a UCQ, we speak of a
UCQrewriting and likewise for other classes of queries. It is known that FO-rewritability
coincides with UCQ-rewritability for OMQs from (EL; CQ) [
We shall sometimes refer to the problem of (query) containment between two OMQs Q1 = (T1; ; q1) and Q2 = (T2; ; q2); we say Q1 is contained in Q2 if A j= Q1(a) implies A j= Q2(a) for all -ABoxes A and a Ind(A). If both OMQs are from (EL, rCQ) and T1 = T2 = T , then we denote this with q1 T q2.
We now introduce two more involved notions that are central to the technical
constructions in Section 4, fork rewritings and splittings. Both notions have been
used before in the context of ontology-mediated querying, see for example [
For a CQ q and V variables in V .
var(q), we use qjV to denote the restriction of q to the De nition 2 (Splitting). Let T be an EL-TBox, q a CQ, and A an ABox. A splitting of q w.r.t. A and T is a tuple = hR; S1; : : : ; S`; r1; : : : ; r`; ; i, where R; S1; : : : ; Sn is a partitioning of var(q), r1; : : : ; r` are role names, : f1; : : : ; `g ! R assigns to each set Si a variable from R, : R ! Ind(A), and the following conditions are satis ed: 1. avar(q) R and x = y 2 q implies (x) = (y); 2. if r(x; y) 2 q with x; y 2 R, then r( (x); (y)) 2 A; 3. qjSi is tree-shaped and can thus be seen as an EL concept CqjSi , for 1 i `; 4. if r(x; x0) 2 q then either (i) x; x0 belong to the same set R; S1; : : : ; S`, or (ii) x 2 R and, for some i, r = ri and x0 root of qjSi .
The following lemma illustrates the combined use and raison d'^etre of both fork
rewritings and splittings. A proof is standard and omitted, see for example [
We provide a polynomial time reduction from FO-rewritability in (EL; tqCQ) to FO-rewritability in (EL; AQ) and, making only very mild assumptions on the algorithm used for solving the latter problem, show that rewritings of the OMQ produced in the reduction can be transformed in a straightforward way into rewritings of the original OMQ. The mild assumptions are that the algorithm produces a tUCQ-rewriting and that, informally, when constructing the tCQs of the tUCQ-rewriting it never introduces atoms `without a reason'|this will be made precise later.
Let Q = (T; ; q0) be from (EL; tqCQ). We can assume w.l.o.g. that q0 contains only answer variables: every tCQ in q with root x can be represented as an EL concept C and we can replace the tree with the atom AC (x) (unless it has only a single node) and extend T with C v AC where AC is a fresh concept name that is not included in . Clearly, the resulting OMQ is equivalent to the original one.
We show how to construct an OMQ Q0 = (T 0; 0; q00) from (EL; AQ) with the announced properties; in particular, Q is FO-rewritable if and only if Q0 is. Let CN(T ) and RN(T ) denote the set of concept names and role names that occur in T , and let subL denote the of concepts that occur on the left-hand side of a concept inclusion in T, closed under subconcepts. Reserve a fresh concept name Ax for every A 2 CN(T ) and x 2 avar(q0), and a fresh role name rx for every r 2 RN(T ) and x 2 avar(q0). Set 0 = frx j r 2 RN(T ) \ [ fAx j A 2 CN(T ) \ and x 2 avar(q0)g: and x 2 avar(q0)g [ Additionally reserve a concept name A9xr:E for every concept 9r:E 2 subL(T ) and every x 2 avar(q0). De ne
T 0 := T [ fCLx v DRx j x 2 var(q0) and C v D 2 T g [ f9rx:C v A9xr:C j x 2 var(q0) and 9r:C 2 subL(T )g
y [ fCL v A9xr:C j r(x; y) 2 q0 and 9r:C 2 subL(T )g [ fA(xu)2q0
Ax v N g where for a concept C = A1 u and CRx are given by u An u 9r1:E1 u
u 9rm:Em, the concepts CLx CLx = A1x u CRx = A1x u u Axn u A9xr1:E1 u u Axn u 9r1x:E1 u u A9xrm:Em u 9rmx:Em
Before proving that the constructed OMQ Q0 behaves in the desired way,
we give some preliminaries. It is known that, if an OMQ from (EL; AQ) has an
FO-rewriting, then it has a tUCQ-rewriting, see for example [
A conformant tUCQ is then de ned in the expected way. The notion of conformance captures what we informally described as never introducing atoms into the rewriting `without a reason'. By the following lemma, FO-rewritability of the OMQs constructed in our reduction implies conformant tUCQ-rewritability, that is, there is indeed no reason to introduce any of the atoms that are forbidden in conformant rewritings.
Lemma 2. Let Q be from (EL; tqCQ) and Q0 the OMQ constructed from Q as above. If Q0 is FO-rewritable, then it is rewritable into a conformant tUCQ.
When started on an OMQ produced by our reduction, the algorithms
presented in [
The proof strategy is to establish the `moreover' part and to additionally show how certain UCQ-rewritings of Q can be converted into UCQ-rewritings of Q0. More precisely, a CQ q is a derivative of q0 if it results from q0 by exchanging atoms A(x) for EL concepts C, seen as tree-shaped CQs rooted in x. We are going to prove the following lemma in Section 4.
Lemma 3. If an OMQ (T; ; q0) from (EL; tqCQ) is FO-rewritable, then it has a UCQ-rewriting in which each CQ is a derivative of q0.
Let q be a UCQ in which every CQ is a derivative of q0. Then the corresponding UCQ for Q0 is the UCQ q0 obtained by taking each CQ from q, replacing every atom A(x), x answer variable, with Ax(x0), every atom r(x; y), x answer variable and y quanti ed variable, with rx(x0; y), and deleting all atoms r(x1; x2), x1; x2 answer variables. The answer variable in q0 is x0. Note that q0 is a tUCQ. To establish the \only if" direction of Proposition 1, we show that when q is a UCQ-rewriting of Q in which every CQ is a derivative of the query q0, then the corresponding UCQ for Q0 is a rewriting of Q0.
We replace tqCQs with the more general rCQs. In this case, we are not going to achieve a black box reduction, but rely on a concrete algorithm for solving FO-rewritability in (EL; AQ), namely a straightforward (and not necessarily terminating) backwards chaining algorithm or a (potentially terminating) re nement thereof. We show how to combine the construction of (several) OMQs from (EL; AQ) with a modi cation of the assumed algorithm to decide FO-rewritability in (EL; rCQ) and to construct actual rewritings.
We start with introducing the straightforward backwards chaining algorithm mentioned above which we refer to as bcAQ. Central to bcAQ is a backwards chaining step based on concept inclusions in a TBox. Let C and D be EL concepts, E v F a concept inclusion, and x 2 var(C) (where C is viewed as a tree-shaped CQ). Then D is obtained from C by applying E v F at x if D can be obtained from C by { removing A(x) for all concept names A with j= F v A; { removing r(x; y) and the tree-shaped CQ G rooted at y when j= F v 9r:G; { adding A(x) for all concept names A that occur in E as a top-level conjunct (that is, that are not nested inside existential restrictions); { adding 9r:G as a CQ with root x, for each 9r:G that is a top-level conjunct of E.
Let C and D be EL concepts. We write D C if D can be obtained from C by removing an existential restriction (not necessarily on top level, and potentially resulting in D = > when C is of the form 9r:E). We use to denote the re exive and transitive closure of and say that D is -minimal with T j= D v A0 if T j= D v A0 and there is no D0 D with T j= D0 v A0.
Now we are in the position to describe algorithm bcAQ. It maintains a set M of EL concepts that represent tCQs. Let Q = (T ; ; A0) be from (EL; AQ). Starting from the set M = fA0g, it exhaustively performs the following steps: 1. nd C 2 M , x 2 var(C), a concept inclusion E v F 2 T , and D, such that
D is obtained from C by applying E v F at x;
2. nd a D0 D that is -minimal with T j= D0 v A0, and add D0 to M .
Application of these steps might not terminate. We use bcAQ(Q) to denote the
potentially in nitary UCQ W M j where M is the set obtained in the limit and
qj denotes the restriction of the UCQ q to those disjuncts that only use symbols
from . The following is standard to prove, see [
Lemma 4. Let Q be an OMQ from (EL; AQ). If bcAQ(Q) is nite, then it is a UCQ-rewriting of Q. Otherwise, Q is not FO-rewritable.
The algorithm for deciding FO-rewritability in (EL; AQ) presented in [
We next introduce a generalized version bcA+Q of bcAQ that takes as input an OMQ Q = (T; ; A0) from (EL; AQ) and an additional EL-TBox T min, such that termination and output of bcA+Q agrees with that of bcAQ when the input satis es T min = T . Starting from M = fA0g, algorithm bcA+Q exhaustively performs the following steps: 1. nd C 2 M , x 2 var(C), a concept inclusion E v F 2 T , and D, such that
D is obtained from C by applying E v F at x; 2. nd D0 D that is -minimal with T min j= D0 v A0, and add D0 to M . We use bcA+Q(Q; T min) to denote the potentially in nitary UCQ W M j , M obtained in the limit. Note that bcA+Q uses the TBox T for backwards chaining and T min for minimization while bcAQ uses T for both purposes. The re ned version of bcAQ implemented in the Grind system can easily be adapted to behave like a terminating version of bcA+Q.
Our aim is to convert an OMQ Q = (T; ; q0) from (EL; rCQ) into a set of pairs (Q0; T min) with Q0 an OMQ from (EL; AQ) and T min an EL-TBox such that Q is FO-rewritable i bcA+Q(Q0; T min) terminates for all pairs (Q0; T min) and, moreover, if this is the case, then the resulting UCQ-rewritings can straightforwardly be converted into a rewriting of Q.
Let Q = (T; ; q0). We construct one pair (Qqr ; Tqmrin) for each fork rewriting qr of q0. We use core(qr) to denote the minimal set V of variables that contains all answer variables in qr and such that after removing all atoms r(x; y) with x; y 2 V , we obtain a disjoint union of tree-shaped CQs. We call these CQs the trees in qr. Intuitively, we separate the tree-shaped parts of qr from the cyclic part, the latter identi ed by core(qr). This is similar to the de nition of tqCQs where, however, cycles cannot involve any quanti ed variables. In a forest model of an ABox and a TBox as mentioned before Lemma 1, the variables in core(qr) must be mapped to the ABox part of the model (rather than to the trees attached to it). Now (Qqr ; Tqmrin) is de ned by setting Qqr = (Tqr ; qr ; N (x)) and Tqr = T [ fCRx v DRx j x 2 core(qr); C v D 2 T g [ fC(x) a utree in qr
CRx v N g where CRx is de ned as in Section 3, and qr is the extension of with all concept names Ax and role names rx used in Tqr such that A; r 2 .
It remains to de ne Tqmrin, which is Tqr extended with one concept inclusion for each fork rewriting q of q0 and each splitting = hR; S1; : : : ; S`; r1; : : : ; r`; ; i of q w.r.t. Aqr , as follows. For each x 2 avar(qr), the equality atoms in qr give rise to an equivalence class [x]qr of answer variables, de ned in the expected way. We only consider the splitting of q if it preserves answer variables modulo equality, that is, if x 2 avar(q), then there is a y 2 [x]qr such that (x) = y. We then add the inclusion
A(ux)2q with x2R
A (x) u
r ( (i)):CqjSi
1 ui ` 9 i
v N
It can be shown that, summing up over all fork rewritings and splittings, only
r ( (i)):CqjSi are introduced (this is similar to the
polynomially many concepts 9 i
proof of Lemma 6 in [
It can be seen that when bcA+Q(Qqr ; Tqmrin) is nite, then it is a conformant tUCQ in the sense of Section 3. Thus, we can also de ne a corresponding UCQ q for Q as in that section, that is, q is obtained by taking each CQ from q0, replacing every atom Ax(x0) with A(x) and every atom rx(x0; y) with r(x; y), and adding all atoms r(x; y) from qr such that x; y 2 core(qr). The answer variables in q are those of q0. We aim to prove the following.
Proposition 2. Let Q = (T ; ; q0) be an OMQ from (EL; rCQ). If bcA+Q(Qqr ; Tqmrin) is nite for all fork rewritings qr of q0, then Wqr qbqr is a UCQ-rewriting of + Q, where qbqr is the UCQ for Q that corresponds to bcAQ(Qqr ; Tqmrin). Otherwise, Q is not FO-rewritable.
There are two exponential blowups in the presented approach. First, the number of fork rewritings of q0 might be exponential in the size of q0. We expect this not to be a problem in practice since the number of fork rewritings of realistic queries should be fairly small. And second, the number of splittings can be exponential and thus the same is true for the size of each Tqmrin. We expect that also this blowup will be moderate in practice. Moreover, in an optimized implementation one would not represent Tqmrin as a TBox, but rather check the existence of fork rewritings and splittings that give rise to concept inclusions in Tqmrin in a more direct way. This involves checking whether concepts of the form r ( (i)):Cq0jSi are derived, and the fact that there are only polynomially many 9 i di erent such concepts should thus be very relevant regarding performance.
To prove Proposition 2, we introduce a backwards chaining algorithm for computing UCQ-rewritings of OMQs from (EL; rCQ) that we refer to as bcrCQ. In a sense, bcrCQ is the natural generalization of bcAQ to rCQs. We rst need to generalize some relevant notions underlying bcAQ.
Let q be a CQ, q0 q, and r(x; y) 2 q. Then q0 is a tree subquery in q with link r(x; y) if q0 is tree-shaped and the restriction of q to the variables reachable from y in the directed graph Gq, var(q0) \ avar(q) = ;, and s(u; z) 2 q with u 2= var(q0) and z 2 var(q0) implies s(u; z) = r(x; y). Note that, taken together, r(x; y) and q0 can be viewed as an EL-concept 9r:q0. Let q and q0 be CQs, C v D a concept inclusion, and x 2 var(q). Then q0 is obtained from q by applying C v D at x if q0 can be obtained from q by { removing A(x) for all concept names A with j= D v A; { for each tree subquery q0 of q with link r(x; y) such that j= D v 9r:q0, removing r(x; y) and q0; { adding A(x) for all concept names A that occur in C as a top-level conjunct; { adding 9r:E as a CQ with root x, for each 9r:E that is a top-level conjunct of C.
Let q; q0 be CQs. We write q0 q if q0 can be obtained from q by selecting a tree subquery q00 in q with link r(x; y) and removing both r(x; y) and q00. We use to denote the re exive and transitive closure of and say that q0 is -minimal with q0 T q0 if q0 T q0 and there is no p q0 with T j= p v A0.
Started on OMQ Q = (T; ; q0), algorithm bcrCQ starts with a set R that contains for each fork rewriting qr of q0 a CQ p qr that is -minimal with p T q0 and then exhaustively performs the same steps as bcAQ: 1. nd q 2 R, x 2 var(q),
applying at x; 2. nd a q00 q0 that is -minimal with q00 2 T , and q0 such that q0 is obtained from q by
T q0, and add q00 to R.
We use bcrCQ(Q) to denote the potentially in nitary UCQ W Rj , R obtained in the limit.
The following establishes the central properties of the bcrCQ algorithm. Lemma 5. Let Q = (T; ; q0) be an OMQ from (EL; rCQ). If bcrCQ(Q) is nite, then it is a UCQ-rewriting of Q. Otherwise, Q is not FO-rewritable.
We use Lemmas 4 and 5 and the construction of the queries Qqr and TBoxes Tqmrin to prove Proposition 2. Essentially, one shows that the run of bcrCQ(Q) is isomorphic to the union of the runs bcA+Q(Qqr ; Tqmrin). Note that Lemma 3 is a consequence of Lemma 5 and the fact that, when Q = (T; ; q0) is from (EL; tqCQ), then bcrCQ(Q) contains only derivatives of q0 (since the only fork rewriting of a tqCQ is the query itself). 5
We have extended the Grind system [
Experiments were carried out on a Linux (3.2.0) machine with a 3.5 GHz quad-core processor and 8 GB of RAM. For the experiments, we use (the EL part of) the ontologies ENVO, FBbi, SO, MOHSE, and not-galen. They are listed in Table 1, along with information about the number of concept inclusions (CI), concept names (CN), and role names (RN) they contain. For each TBox, we hand-crafted 10 conjunctive queries (three tqCQs and seven rCQs), varying in size from 2 to 5 variables and showing several di erent topologies.
The runtimes are reported in Table 1. Only three queries did not terminate in 30 minutes or exhausted the memory. For the successful ones, we list fastest (Min CQ), slowest (Max CQ), and average runtime (Avg CQ). For comparison, the Avg AQ column lists the time needed to compute FO-rewritings for all queries (T; ; A(x)) with A(x) an atom in q0. This check is of course incomplete for FO-rewritability of Q, but can be viewed as a lower bound.
In summary, we believe that the outcome of our experiments is promising. While runtimes are higher than in the AQ case, they are still rather small given that we are dealing with an intricate static analysis task and that many parts of our system have not been seriously optimized. The queries with long runtimes or timeouts contain AQs that are not FO-rewritable, which forces the decomposed algorithm implemented in Grind to enter a more expensive processing phase. 6
We remark that our approach can also be used to compute FO-rewritings of
OMQs from (EL; CQ) even if the CQs are not rooted, as long as they are not
Boolean (that is, as long as they contain at least one answer variable). This follows
from (a minor variation of) an observation from [
Acknowledgements. We acknowledge support by ERC grant 647289 `CODA'.