We propose a new type of algorithm for computing rstorder (FO) rewritings of concept queries under EL-TBoxes that is tailored towards e cient implementation. The algorithm outputs a non-recursive datalog rewriting if the input is FO-rewritable and otherwise reports non-FO-rewritability. We carry out experiments with ontologies from practical applications which show that our algorithm performs very well in practice, and that EL-TBoxes originating from real-world applications admit FO-rewritings (of reasonable size) in almost all cases, even when in theory such rewritings are not guaranteed to exist.
Query rewriting is an important technique for implementing ontology-based data
access (OBDA) based on a relational database system (RDBMS), thus taking
advantage of those systems' e ciency and maturity [
In this paper, we consider the computation of FO-rewritings of concept
queries under TBoxes that are formulated in the description logic EL, where
a concept query takes the form C(x) with C an EL-concept. It has recently been
shown in [
The aim of this paper is to design algorithms for computing FO-rewritings
of concept queries under EL-TBoxes that are complete, terminating, and feasible
in practice. To this end, we start with a marriage of approaches (ii) and (iii)
to get the best of both worlds; in particular, (ii) appears to be practically more
feasible than (iii) while (iii) provides a way to achieve termination. The resulting
algorithm is conceptually simple and constitutes a signi cant step towards our
goal. However, it produces FO-rewritings that are unions of conjunctive queries
(UCQs), which results in two signi cant drawbacks: rst, recent experiments [
To address these shortcomings, we re ne our original algorithm to what we call a decomposed algorithm. While the original algorithm uses tree-shaped conjunctive queries (CQs) as an internal data structure, the new algorithm only represents single nodes of CQs together with information of how to reassemble these nodes into full tree-shaped CQs. This can be seen as a way to implement structure sharing and it also allows us to directly produce rewritings that are non-recursive datalog programs, avoiding UCQ-rewritings altogether. The algorithm runs in exponential time, is capable of deciding the existence of FOrewritings in ExpTime, and produces monadic non-recursive datalog rewritings that are of at most exponential size (but much smaller in practice). Technically, the decomposed algorithm is much more subtle than the original one.
We then evaluate the decomposed algorithm by carrying out experiments with seven ontologies from practical applications. We ask for an FO-rewriting for every concept query A(x), with A a concept name from the ontology under consideration. Out of 15970 requests in total, the decomposed algorithm times out only on 158 inputs, with a timeout of 15 seconds. We also analyze the size of the generated non-recursive datalog rewritings, with extremely encouraging results. Our experiments show that the decomposed algorithm performs very well on inputs from practical applications. They also con rm our initial belief that EL-ontologies from practical applications often admit FO-rewritings. In particular, only 31 of 15970 queries turn out to not be FO-rewritable.
Proof details can be found in the long version available at:
3 For approaches to FO-rewritability for non-Horn DLs we refer the reader to [
We use NC and NR to denote countably in nite sets of concept names and role names, respectively. An EL-concept is formed according to the syntax rule C ::= A j > j C u C j 9r:C, a concept inclusion (CI) takes the form C v D with C and D EL-concepts, and a TBox is a nite set of CIs. The semantics of concepts and TBoxes is de ned as usual. We write T j= C v D when C is subsumed by D under T .
An ABox A is a set of assertions of the form A(a) and r(a; b) with A a concept name, r a role name, and a; b individual names from a countably in nite set NI. We use ind(A) to denote the set of individual names that occur in A. A concept query is an expression C(x) with C an EL-concept and x a variable. We write A; T j= C(a) if a is a certain answer to C given the ABox A and TBox T . For an FO-query q(x) with one free variable, we write A j= q(a) if A (viewed as a structure) satis es q under the assignment that maps x to a.
A concept query C(x) is FO-rewritable under a TBox T if there is an
FOformula '(x) such that for all ABoxes A and individuals a, we have A; T j= C(a)
i A j= '(a). In this case, we call '(x) an FO-rewriting of C(x) under T . An
FO-formula '(x) is a partial FO-rewriting of A under T if for all ABoxes A and
a 2 ind(A), A j= '(a) implies A; T j= A(a). Thus a partial FO-rewriting is an
FO-rewriting that is sound, but not necessarily complete. When studying
FOrewritability of concept queries C(x), we can assume w.l.o.g. that C is a concept
name since C(x) is FO-rewritable under a TBox T i A(x) is FO-rewritable
under T [ fC v Ag where A is a fresh concept name [
We will also consider more speci c forms of FO-rewritings, in particular UCQ-rewritings and non-recursive datalog rewritings. Although, strictly speaking, non-recursive datalog rewritings are not FO-rewritings, the existence of either kind of rewriting coincides with the existence of an FO-rewriting. In particular, non-recursive datalog rewritings can be viewed as a compact representation of a UCQ-rewriting that implements structure sharing. By a monadic datalog rewriting, we mean a datalog rewriting in which all intensional (IDB) predicates are unary.
For our technical constructions, it will be convenient to view EL-concepts as CQs that take the form of a directed tree. We will represent such queries as sets of atoms of the form A(x) and r(x; y) with A a concept name, r a role name and x; y variables, not distinguishing between answer variables and quanti ed variables. Tree-shapedness of a conjunctive query q then means that the directed graph (V; f(x; y) j r(x; y) 2 qg) is a tree, where V is the set of variables in q, and that r(x; y); s(x; y) 2 q implies r = s. In the following, we will not distinguish explicitly between an EL-concept C and its query representation. We thus use var(C) to denote the set of variables that occur in C and x" to denote the root variable in C. For an x 2 var(C), we use Cjx to denote the EL-concept represented by (the subtree rooted at) x. When we speak of a top-level conjunct (tlc) of an EL-concept C, we mean a concept name A such that A(x") 2 C or a concept 9r:D such that r(x"; y) 2 C and D = Cjy. We use tlc(C) to denote the set of all top-level conjuncts of C. For any syntactic object (such as a concept or a TBox), we de ne its size to be the number of symbols used to write it. 3
Let T be an EL-TBox and A0 a concept name for which an FO-rewriting is
to be constructed. The algorithm presented in this section constructs a set of
partial rewritings of A0 under T by starting from fA0g and then exhaustively
applying the concept inclusions in T as rules in a backwards chaining manner.
Let C and D be EL-concepts and ' = E v F an EL-concept inclusion. Further,
let x 2 var(C) and let there be at least one tlc G of Cjx with j= F v G. Then D
is obtained from C by applying ' at x if D can be obtained from C by
{ removing A(x) for all concept names A with j= F v A;
{ removing the subtree rooted at y whenever r(x; y) 2 C and j= F v 9r:(Cjy);
{ adding A(x) for all concept name A that are a tlc of E;
{ adding the subtree 9r:H to x for each 9r:H that is a tlc of E.
When the exact identity of x is not important, we say that D is obtained from C
by applying '. This corresponds to a backwards chaining step based on so-called
piece uni ers in [
Lemma 1. If T j= C v A0 and D can be obtained from C by applying some CI in T , then T j= D v A0.
Apart from applying CIs from the TBox as rules, our algorithm will also minimize the generated partial rewritings to attain completeness and termination. To make this precise, we introduce some notation. For EL-concepts C and D, we write C D if there is x 2 var(D) such that C = D n Djx, that is the concept C is obtained from D by dropping the subtree Djx from D. We use to denote the transitive closure of and say that C is -minimal with T j= C v A0 if T j= C v A0 and there is no C0 C with T j= C0 v A0. Note that if T j= C v A0, then it is possible to nd in polynomial time a C0 C that is minimal with T j= C0 v A0 (since subsumption in EL can be decided in PTime).
The constructions in [
T T The algorithm is formulated in Figure 1. Note that, by Lemma 1, the concept D considered in the condition of the while loop satis es T j= D v A0. We are thus guaranteed to nd the desired D0 inside the while loop. Also note that there are potentially many di erent D0 that we could use, and each of them will work. procedure nd-rewriting(A0(x); T )
M := fA0g while there is a C 2 M and a concept D such that
nd a D0
D that is minimal with T j= D0 v A0 if D0 is blocked then
return `not FO-rewritable' add D0 to M return the UCQ W M . It is illustrative to try Example 1 without applying the minimization step. We then nd a blocked concept in M , which shows that without minimization the algorithm is incomplete. It can also be seen that dropping minimization results in non-termination since the out-degree of concepts in M can grow unboundedly.
We now establish correctness and termination, showing rst that, if the algorithm claims to have found an FO-rewriting, then this is indeed the case. Proposition 1 (Soundness). If the algorithm returns W M , then W M is an FO-rewriting of A0 under T .
Proof.(sketch) Let A be an ABox. We have to show: (1) if A j= W M (a0), then A; T j= A0(a0); (2) if A; T j= A0(a0), then A j= W M (a0). For Point 1, assume that A j= W M (a0). Then there is a C 2 M with A j= C(a0). Consequently A; T j= C(a0). By construction of M , all its elements C satisfy T j= C v A0, thus A; T j= A0(a0) as required.
For Point 2, we essentially follow the proof strategy from [
Proposition 2 (Completeness). If the algorithm returns `not FO-rewritable', then A0 has no FO-rewriting under T .
Proof. By Theorem 2 in [
Fact. If there is a concept C that is blocked with variables x1; x2; x3 2 var(C), T j= C v A0, and T 6j= C n Cjx3 v A0, then ( ) holds.
Now assume the algorithm returns `not FO-rewritable'. Then there is a concept
D that is minimal with T j= D v A0 and that is blocked with variables x1; x2; x3.
By minimality of D, T 6j= (D n Djx3 ) v A0 and ( ) follows. o
We prove in the appendix that the algorithm always terminates by showing that
all concepts in M have outdegree at most n and depth at most 22n, n the size
of T . As remarked in [
The algorithm presented in this section consists of three phases. In the rst phase, a certain set is computed that can be viewed as a decomposed representation of the set M from Section 3 in the sense that we store only single nodes of the tree-shaped concepts in M , rather than entire concepts. In the second phase, we compute a certain set that enriches the node representation provided by with sets of logical consequences as mentioned in Point 2 of the de nition of blocked concepts. In the third phase, we rst execute a certain cycle check on , which corresponds to checking the existence of a blocked concept in M . If no cycle is found, we can read o a rewriting from .
Assume that T is a TBox and A0 a concept name for which we want to compute an FO-rewriting. To present the algorithm, it is convenient to decompose conjunctions on the right-hand side of CIs, that is, to assume that T consists of CIs of the form C v A, A a concept name, or C v 9r:D. We start with describing the construction of , whose elements we call node pairs. A node pair has the form (C; S), where C 2 sub(T ) and S sub(T ) is a set of concept names and concepts of the form 9r:C. Intuitively, a node pair (C; S) describes a set of concepts D (subtrees of concepts in ) such that T j= D v C and the following conditions are satis ed: (i) if A 2 S for a concept name A, then A is a tlc of D; (ii) if 9r:E 2 S, then there is a tlc 9r:E0 of D such that T j= E0 v E. The computation of starts with f(A0; fA0g)g and proceeds by exhaustively applying the following two rules: (r1) if (C; S) 2 , D v A 2 T and A 2 S, then add pair (C; (S n fAg) [ tlc(D)) (r2) if (C; S) 2 , D v 9r:F 2 T , and there is an 9r:G 2 S with T j= F v G, then add the pair (C; (S n f9r:G j T j= F v Gg) [ tlc(D)) After applying either rule, we also have to add the pair (G; tlc(G)) for every 9r:G 2 sub(D) to trigger further derivation.
The set represents a (potentially in nitary) UCQ-rewriting of A0 under T in a sense that we make precise now. Let b be the set obtained as the limit of the sequence of sets b0; b1; : : : de ned as follows: { b0 := f(C; u S) j (C; S) 2 and S NCg. { bi+1 is bi extended with all pairs (C; D) such that there are (C; S) 2 (G; Cr;G) 2 bi for each 9r:G 2 S and D = A2uS\NC A u 9r:uG2S 9r:Cr;G: and Proposition 3 (Soundness and Completeness of b). For all ABoxes A and a 2 ind(A), we have A; T j= A0(a) i there is a (A0; D) 2 b with A j= D(a). Note that provides us with a su cient condition for FO-rewritability and suggests a way to produce a non-recursive datalog rewriting. In fact, if is acyclic in the sense that the directed graph
G
= ( ; f((C; S); (C0; S0)) j S contains a concept 9r:C0g) contains no cycle, then b is nite and we obtain a non-recursive datalog program that is a rewriting of A0 under T by taking the rule
PC (x) ^ A(x) ^
^ ( r(x; yr;D) ^ PD(yr;D) ) A2S
9r:D2S for each (C; S) 2 and using A0 as the goal predicate. However, if is not acyclic, then A0 could still be FO-rewritable under T , but the above program will be recursive. To deal with this problem, we need the next two phases.
We construct a set of node tuples from by further annotating and duplicating the pairs in . A node tuple takes the form t = (Ct; St; cont; st; xcont) where Ct and St have the same form as the components of node pairs in , cont sub(T ), st is an existential restriction in St or the special symbol \ ", and xcont is either a subset of sub(T ) or the special symbol \ ". Intuitively, a node tuple t 2 describes a set of concepts D (subtrees of concepts in ) such that (Ct; St) describes D in the way described above and the following additional conditions are satis ed: (iii) for each E 2 sub(T ), we have T j= D v E i E 2 cont; (iv) in the subtree of D rooted at st there is a leaf node such that for the concept D0 obtained by dropped this node and each E 2 sub(T ), we have T j= D0 v E i E 2 xcont.
When St contains no existential restrictions, we use \ " in the last two components. To understand st, it is useful to think of D as a tree and of st as a selected successor of the root of that tree. We start the construction of with 0 := f(C; S; conT (S); ; ) j (C; S) 2 with S
NCg;
where for a set of concepts M , conT (M ) denotes the set of concepts D 2 sub(T )
such that T j= u M v D. We call the tuples in 0 leaf tuples. The nal set
is constructed by exhaustively applying the following rule:
(r3) If t is a node tuple such that 9r0:D0; : : : ; 9rn:Dn are the existential
restrictions in St, st = 9r`:D`, and t0; : : : ; tn 2 with Cti = Di for 0 i n,
then add t to if the following conditions are satis ed:
there is a node pair (Ct; S) 2 with St S and S \ NC = St \ NC;
cont = conT (M ), where M = S(St\NC)[f9ri:G j i n and G 2 conti g;
xcont = conT (M 0), where M 0 is
[(St \ NC) [ f9r`:G j G 2 xcont` g [ f9ri:G j ` 6= i
n and G 2 conti g:
In Points 3, the concept 9r: (which might occur in the set M 0) is identi ed
with >. For t; t0 2 , we write t t0 if there are t0; : : : ; tn 2 that satisfy
the conditions listed in (r3) and such that t0 = t`, that is, t0 is the tuple that
was chosen for the selected successor. Note that the computation of the sets cont
and xcont is complete, relying on the following observation [
Lemma 2. For any concept C = A1 u u An u 9r1:G1 u u 9rm:Gm, conT (C) = conT (fA1; : : : ; Ang [
[ f9ri:D j D 2 conT (Gi)g) 1 i m We now describe the third and last phase of the algorithm, which rst checks whether an FO-rewriting exists at all and, if so, produces a rewriting that takes the form of a non-recursive monadic datalog program.
We start with introducing the relevant notion of a cycle. A tuple t 2 is a root tuple if A0 2 cont and A0 2= xcont. A path through is a nite sequence of node tuples t1; : : : ; tk from such that ti ti+1 for 1 i < k. A tuple t 2 is looping if there is a path t1; : : : ; tk through of length at least one such that t = t1, cont = contk , and xcont = xcontk . We say that contains a root cycle if there are tuples t; t0 2 such that t is a root tuple, t0 is a looping tuple, and t0 is reachable from t along .
Proposition 4. A0 is not FO-rewritable under T if and only if
root cycle.
contains a
Proof.(sketch) \if". Assume that contains a root cycle. Using this cycle as a
guide, we show how to nd a concept C that is blocked in the sense of Section 3
and satis es T j= C v A0 as well as T 6j= (C n Cjx3 ) v A0, where x3 is as in
the de nition of `blocked'. Once we have constructed such a concept C, we can
again rely on the results of [
\only if". Assuming that contains no root cycle, we show below how to constuct a non-recursive datalog-rewriting of A0 under T , thus A0 is FO-rewritable under T . o As suggested by Proposition 4, our algorithm rst checks whether contains a root cycle and, if so, returns `not FO-rewritable'. Otherwise, it constructs a non-recursive datalog program T ;A0 as follows. First, we drop from all tuples that are not reachable from a root tuple along an -path. For t; t0 2 and 9r:D 2 St, we write t 9r:D t0 if there is a tuple bt = (Ct; St; cont; 9r:D; xconbt) 2 such that bt t0. Note that, by de nition of \ ", t 9r:D t0 implies Ct0 = D. Now, T ;A0 contains for every t 2 , the rule
PCt;cont (x)
A(x) ^
(r(x; yr;D) ^ ^ A2St\NC
^ 9r:D2St
_ t02 jt 9r:Dt0
PD;cont0 (yr;D)) Note that the disjunctions can be removed by introducing auxiliary IDB predicates, without causing a signi cant blowup. The goal predicates of T ;A0 are all predicates of the form PA0;con(x) with A0 2 con.
Theorem 1. 1. The program T ;A0 is a rewriting of A0 under T . 2. If contains no root cycle, then T ;A0 is non-recursive.
Even if contains no root-cycles, the program T ;A0 may have up to (single) exponentially many IDB predicates. We observe that this cannot be signi cantly improved without giving up monadicity.
Theorem 2. There is a family of TBoxes T1; T2; : : : such that for all n 1,
Tn is of size O(n2), the concept name A0 is FO-rewritable under Tn, and the
smallest non-recursive monadic datalog rewriting has size at least 2n.
Let us brie y analyze the complexity of the decomposed algorithm. It is easy to
verify that the number of -pairs and -tuples is singly exponential in the size
of T and that all required operations for building and and for determining
the existence of a root cycle require only polynomial time. By Proposition 4,
we have thus found an ExpTime algorithm for deciding FO-rewritability of
ELconcept queries. This is almost optimal as the problem we are dealing with is
PSpace-complete and becomes ExpTime-hard if slightly varied, see [
We have implemented the decomposed algorithm in Java and conducted a number of experiments. The implementation is not highly optimized, but some aspects of handling the set are worth to point out. In particular, we use numbers
XP NBO
not-galen SO to represent subconcepts in T , store the S-component of each pair (C; S) 2 , which is a set of subconcepts of T , as an ordered set, and use so-called tries as a data structure to store . We remove pairs (C; S) 2 where S is not minimal, that is, for which there is a (C; S0) 2 with S0 ( S. It is easy to see that this optimization does not compromise correctness.
The experiments were carried out on a Linux (3.2.0) machine with a 3.5Ghz
quad-core processor and 8GB of RAM. Although a large number of EL-TBoxes
is available on the web and from various repositories, most of them are acyclic
TBoxes in the traditional DL sense, that is, the left-hand sides of all CIs are
concept names, there are no two CIs with the same left-hand side, and there
are no syntactic cycles. Since concept queries are always FO-rewritable under
acyclic EL-TBoxes [
For each of these TBoxes, we have applied the decomposed algorithm to every concept name in the TBox. In some rare cases, the set has reached excessive size, resulting in non-termination. We have thus established a 15 second timeout for the -phase of the algorithm. With that timeout, our algorithm was able to decide FO-rewritability in almost all of the cases, see Table 1. The overall runtime for all our experiments as a batch job (15970 invocations of the algorithm) took only 80 minutes. The generated non-recursive datalog-rewritings are typically of very reasonable size. The number of rules in the rewriting is displayed in the upper part of Figure 2; for example, for NBO, about 55% of all rewritings consist of a single rule, about 18% have two or three rules, about 10% have 4{7 rules, and so on. Note that the x-axis has logarithmic scale. The size of the rule bodies is typically very small, between one and two atoms in the vast majority of cases, and we have never encountered a rule with more than ten body atoms. It is also interesting to consider the number of IDB predicates in a rewriting, as intuitively these correspond to views that have to be generated by a database system that executes the query. As shown in the lower part of Figure 2, the number of IDB predicates is rather small, and considerably lower than the number of rules in the produced programs (we again use logarithmic scale on the x-axis). s e m a n t p e c n o c f o % s e m a n t p e c n o c f o % XP NBO
NBO
1 2 4 8 16 32 64
The experiments also con rm our initial belief that ontologies which are used in practical applications have a simple structure. As shown in Table 1, the number of concept names that are not FO-rewritable is extremely small. Moreover, if a concept name was FO-rewritable, then we were always able to determine this already in the -phase of our algorithm, without ever entering the -phase. Note, though, that for those cases that turned out to be not FOrewritable, we had to go through the full -construction. 6
We plan to optimize the implementation of the decomposed approach further to
eliminate the timeouts we encountered in the experiments. Moreover, we plan
to extend the algorithm and implementation in several ways. First, we plan to
generalize the approach from concept queries to conjunctive queries. Second, in
many applications the ABox signature (i.e., the concept and role names occurring
in the ABoxes) is a small subset of the signature of the TBox [