Description Logics are a key technology in data management scenarios such as Ontology-Based Data Access (OBDA), a paradigm in which a DL ontology is used to provide a conceptual view of the data [1]. An OBDA system transforms a conjunctive query over the ontology into a query over the data sources [2]. This transformation is independent of the data, so the OBDA approach can thus be used in settings where the data sources provide read-only access to the data, and where the data changes frequently. Most existing OBDA systems are based on the DL-Lite family of lightweight Description Logics [1], which is also the basis for the QL pro le of the OWL 2 ontology language. Logics in this family have been designed to allow a conjunctive query posed over the ontology to be rewritten as a rst order query over the data sources|that is, queries are rst-order rewritable. The query rewriting procedure is independent of the data, and the resulting queries can be evaluated using highly scalable relational database technology. To achieve this, however, the expressive power of DL-Lite is very restrictive. This prevents the OBDA approach from being applied in the life science domain, where many ontologies use DLs from the E L family [3, 4]. This family provides the basis for the EL pro le of OWL2, and many prominent ontologies, such as SNOMED-CT, were developed using this language. The problem of answering conjunctive queries in E L has already been studied in the literature, and two orthogonal approaches have been proposed. First, Rosati proposed a pure query rewriting technique which transforms an E L TBox T and a conjunctive query q into a Datalog program PT ;q [5]. Second, Lutz et al. introduced a \combined" approach [6, 7]. This technique rst materializes certain facts entailed by the ontology in a precomputation step. Then, each user query is rewritten into a polynomial rst-order query that, when evaluated over the materialized facts, computes the answers to the user's query. Unfortunately, these two approaches exhibit several shortcomings when applied in the context of OBDA. In particular, Rosati's rewriting technique computes for each user query a fresh Datalog program whose size depends on both the query and the terminology, which could be very ine cient when dealing with large scale ontologies. The approach by Lutz et al. produces smaller rst order rewritings, but the use of materialization means that the technique is only applicable when the data sources provide read/write access to the data; furthermore, materialization can be ine cient if the data changes frequently.
? This work was supported by EPSRC and Alcatel-Lucent.
In this paper, we present a pure query rewriting technique to query answering in E L. Our approach reinterprets the combined approach proposed by Lutz and colleagues in terms of Datalog. Our rewriting procedure consists of two distinct steps. The rst step rewrites a TBox T into a Datalog program PT , whose size depends linearly on the size of T . Then, at query time, the conjunctive query q is rewritten into a Datalog query hQP ; QC i, whose size depends polynomially on q. The two rewriting steps are such that, given an ABox A, deciding whether QP (a1; : : : ; ak) follows from PT [ QC [ A is equivalent to deciding whether ha1; : : : ; aki is a certain answer to q over a knowledge base hT ; Ai.
At last, we summarize our main contributions. First, our rewriting approach,
unlike Rosati's, separates the rewriting of the TBox and the query into two
distinct steps, thus reducing ine ciency when dealing with large ontologies. Second,
our technique does not require the materialization of entailed facts, hence our
solution is in the spirit of OBDA and it avoids the problems associated with
the materialization of large models. Finally, we set the stage for assessing the
utility and the applicability to PT [ QC [ A of optimized Datalog evaluation
techniques, such as magic sets and SLG resolution [
Let NC , NR, NI be pairwise disjoint in nite sets of atomic concepts, atomic roles, and individuals. Together, the sets NC , NR, and NI form the signature of an E L language. Whenever the distinction between atomic concepts and atomic roles is immaterial, we call an element of NC [ NR a predicate. The set of E L concept expressions is inductively de ned starting from atomic concepts A 2 NC and atomic roles R 2 NR according to the syntax rule: C ! A j C1 u C2 j 9R:C j >.
An E L TBox T is a nite set of concept inclusions of the form C v D; an E L ABox A is a nite set of assertions of the form A(a) or R(a; b) with a and b individuals; and an E L knowledge base (KB) is a tuple K = hT ; Ai, where T is an E L TBox and A is an E L ABox. We denote with Ind(A) the set of all individuals occurring in the ABox A. Furthermore, for E either a TBox or an ABox, Pred(E ) is the set of all predicates occurring in E .
Semantics is given as usual in terms of rst-order interpretations I = h I ; I i,
where I is a nonempty domain and I is an interpretation function; please
refer to [
J = pathsA(I)
aJ = aI
AJ = fp 2 pathsA(I) j tail(p) 2 AI g
RJ = fhaJ ; bJ i j R(a; b) 2 Ag [ fhp; p R ci j fp; p R cg
pathsA(I)g
In this paper, we deal only with normalized E L TBoxes. Let A1, A, and B be
arbitrary concepts from NC [ f>g. We say that an E L TBox T is in normal
form if each axiom in T is in one of the following forms: A v B; A u A1 v B,
A v 9R:B, or 9R:A v B. Given an arbitrary E L TBox T , we can compute a
normalized TBox Tnorm of T in linear time [
Let NV be an in nite set of variables disjoint from NI . Together, NV and NI form
the set NT of terms. A rst-order query q is a rst-order formula constructed
from the terms in NT and the predicates from NC [ NR [
Datalog
Let NB be a nonempty set of built-in predicates [
S(~u)
S1(~u1); : : : ; Sn(~un); Bn+1(~un+1) : : : ; Bm(~um); where n; m 0, fS; S1; : : : ; Sng NC [ NR, fBn+1; : : : ; Bmg NB, and ~u and ~ui are tuples of terms of suitable length. A rule is safe if each variable occurring in ~u [ ~un+1 [ : : : [ ~um also occurs in ~u1 [ : : : [ ~un. Atom S(~u) is the head of the rule, and atoms S1(~u1); : : : ; Bm(~um) constitute the body of the rule. Whenever the body of a rule r is empty, we call r a fact, and we write the rule as S(~u). A Datalog program P is a set of safe Datalog rules. Finally, sch(P ) is the set of predicates occurring in P .
Next, we de ne the semantics of a Datalog program P using Herbrand
interpretations [
I [ B j= 8~x(Bm(~un) ^ : : : ^ Bn+1(~un+1) ^ Sn(~un) ^ : : : ^ S1(~u1) ! S(~u));
where ~x is a tuple consisting of all variables occurring in the rule. The semantics
of a Datalog program P is de ned as the minimal Herbrand interpretation I
satisfying P w.r.t. B, written MB(P ). Whenever the program does not contain
built-in predicates, we do not consider the interpretation B and we simply write
M(P ). The semantics of Datalog programs can be de ned also by means of a
xpoint construction. Then, TP is the immediate consequence operator that maps
instances I over sch(P ) to instances over sch(P ) as follows. For each rule r in P ,
if there exists a match for S1(~u1) ^ : : : ^ Sn(~un) ^ Bn+1(~un+1) ^ : : : ^ Bm(~um)
in I [ B, then S(a1; : : : ; ak) is contained in TP (I) with ai = (ui) for each ui 2 ~u.
One can prove that TP has a minimum xpoint TP! such that TP! = MB(P ) [
Finally, a Datalog query is a tuple hQP ; QC i where QP is a predicate symbol and QC is a Datalog program. A tuple of individuals ha1; : : : ; aki is an answer to hQP ; QC i over Datalog program P if P [ QC j= QP (a1; : : : ; ak). 3
Datalog Rewriting for E L TBoxes In this section, we show how to transform an E L TBox T into a Datalog program PT whose size depends linearly on T . The transformation is such that, for an arbitrary E L ABox A, we can use the unraveling of M(PT [A) to compute the answers to conjunctive queries over hT ; Ai. Let T be a TBox over an arbitrary E L signature. Intuitively, for each axiom occurring in T , the program PT contains a set of Datalog rules which encode the constraint imposed by . To achieve this, we have to overcome two issues.
First, E L concept inclusions of the form A v 9R:B require the use of either
existential quanti cations or Skolem terms in rule heads; however, Datalog
does not allow neither of the two. In order to solve this issue, we use a technique
that has been introduced for representing canonical models of E L knowledge
bases [
B(X) B(X)
Set of rules ( ) R(X; oB)
B(X)
A(X) B(oB) A1(X); A2(X) R(X; Y ); A(Y )
A(X)
A(X) auxiliary individual oB, which represents the class of existentially quanti ed individuals of type B. Then, for each axiom of the above form, the program PT contains the following two rules:
R(X; oB)
A(X);
B(oB)
A(X):
Second, E L allows for > to occur in concept expressions. Hence, we need to de ne in PT a unary predicate >, whose extension|given an ABox A|coincides with the Herbrand universe of PT [ A. To achieve this, we restrict our study to a subset of all E L ABoxes. In particular, we consider only those ABoxes A such that Pred(A) Pred(T ). That is, each predicate occurring in the ABox A must occur also in the TBox T . Then, in our Datalog program, for each atomic concept A and for each atomic role R occurring in T , we add the following rules: >(X)
A(X); >(X)
R(X; Y ); >(Y )
R(X; Y ):
This is only one of the several ways in which we can encode such a predicate.
In fact, another possibility would be|as suggested by Rosati in [
Next, we formalize the transformation of a TBox T into a Datalog program PT . Let Aux = foA j A 2 NC g [ fo>g be a set of auxiliary individuals distinct from NI . Then, the program PT is constructed from terms in NT [ Aux and predicates in NC [ NR [ f>g as follows. The transformation uses the function , shown in Figure 1, to transform each axiom in the (normalized) TBox T into a set of Datalog rules. The Datalog program PT is then de ned as follows.
PT = S ( )
S 2T
A2Pred(T )\NC >(X) SR2Pred(T )\NR >(X)
A(X) R(X; Y ); >(Y )
R(X; Y ) The following result readily follows from the de nition of the program. Proposition 1. For an arbitrary E L TBox T , Datalog program PT can be computed in time linear in the size of T .
Consider an arbitrary EL ABox A. Next, we prove that the unraveling U w.r.t. A of M(PT [A) can be used to answer conjunctive queries over K = hT ; Ai. We do so in two distinct steps. First, we introduce the notion of chase of an EL knowledge base K. Second, we show that the chase of K is isomorphic to U .
The chase of an EL knowledge base K = hT ; Ai, written chase(K), is a possibly in nite Herbrand interpretation de ned inductively by starting from A and then applying axioms occurring in the TBox to assertions occurring in the ABox. In our de nition of the chase, we use function terms to denote existentially quanti ed individuals. Hence, the de nition of ABox assertion is extended in a natural way to accommodate for assertions over function terms. We denote with u and w terms that can be either individuals or function terms. Next, we de ne an operator T that chases an ABox by applying the axioms occurring in the TBox T . In the de nition, we use assertions of the form >(u) to assert that u is a member of the EL concept expression >. For S an arbitrary ABox, T (S) is the smallest ABox containing S and closed under the following chasing rules. (cr1) If fA(u)g S and A v B 2 T , then fB(u)g T (S). (cr2) If fA1(u); A2(u)g S and A1 u A2 v B 2 T , then fB(u)g (cr3) If fR(u; w); A(w)g S and 9R:A v B 2 T , then fB(u)g (cr4) If fA(u)g S and A v 9R:B 2 T , then
T (S).
T (S). fR(u; f (u; R; B)); B(f (u; R; B))g
T (S): (cr5) If u occurs in S, then f>(u)g T (S).
We now de ne an in nite sequence of nite ABoxes Ai for i 2 N.
It is clear that our construction of the chase of K is fair. In fact, for each i 2 N we
have that Ai+1 is the result of exhaustively applying|to all possible assertions
occurring in Ai|all applicable axioms in T . At last, we want to point out that
chase(K) can be used to compute the certain answers to a CQ q over K.
Proposition 2 ([
So, by proving that the unraveling U of M(PT [A) is isomorphic to chase(K), we establish that U can be used to answer conjunctive queries over K. To prove the structural equivalence of U and chase(K), we de ne a function h mapping Finally, the chase of K is the in nite union of all such ABoxes Ai.
A0 = A Ai+1 =
T (Ai) chase(K) = [ Ai i2N paths occurring in U to terms in chase(K). We de ne h by induction on the depth of paths occurring in U as follows.
Base Case. Consider an arbitrary p 2 U with dep(p) = 1. We set h(p) := p.
Inductive Step. Let p = t1 R2 t2 tn 1 Rn tn be a path occurring in U such that h(p) has not been de ned yet, but h(t1 Rn 1 tn 1) = u. We distinguish between two cases depending on the type of the individual tn. 1. If tn occurs in the ABox, we set h(p) := tn. 2. If tn is of the form oB, we set h(p) := f (u; Rn; B).
Theorem 1 shows that h is an isomorphism between the two structures. Intuitively, for the only-if direction, we show that h is an injective homomorphism from U to chase(K) by induction on the depth of paths occurring in U ; for the if-direction, by induction on the construction of chase(K) we prove that h is a surjective function and that it is a homomorphism from chase(K) to U . Theorem 1. Function h is an isomorphism from U to chase(K).
Since the unraveling of M(PT [ A) is generally in nite, this result alone does not provide us with an algorithm for answering queries in E L. In the next section, we show how to rewrite a user query q into a Datalog query hQP ; QC i such that PT [ A [ QC j= QP (a1; : : : ; ak) if and only if ha1; : : : ; aki 2 cert(q; K) and thus solve the problem. 4
In the previous section, we have seen that for an arbitrary E L KB K = hT ; Ai evaluating a conjunctive query q over the unraveling of the Herbrand model of PT [ A is equivalent to computing the certain answers to q over K. In this section, we develop a query rewriting procedure that reduces the computation of cert(q; K) to the problem of evaluating a suitably constructed Datalog query over PT [ A. We achieve this in two steps. First, we present an interesting property of a certain class of interpretations. Second, we show how this result can be used to develop a query rewriting procedure in our Datalog setting.
We use the notions of A-connected and split interpretations from [
Then, let J be the unraveling w.r.t. A of a split and A-connected
interpretation I and let q be a conjunctive query. Lutz et al. in [
We now brie y outline how we can construct such an FO rewriting q for
q [
Pred( ; R) = ft 2 NT (q) j R(t; t0) occurs in q with t0 2 g Next, we de ne three sets of terms that correspond to the above mentioned cases. { Fork= is the set of all pairs hPred( ; R); t i such that is an equivalence class of q and jPred( ; R)j > 1. { Fork6= is the set of all quanti ed variables v 2 qvar(q) for which atoms R(s; v) and S(s0; t) exist in q such that R 6= S and v q t. { Cyc is the set of all variables v 2 qvar(q) for which atoms
R0(t0; t00); : : : ; Rm(tm; t0m); : : : ; Rn(tn; t0n) exist in q such that m; n 0; for some i n we have that ti q v; for each j < n we have that t0j q tj+1; and t0n q tm.
We are now ready to formally specify the FO query rewriting q . In the de nition,
we assume that Aux is a fresh predicate not occurring in q and K and that every
interpretation I interprets Aux as I n faI j a 2 Ind(A)g. Then, formulae q1 and
q2 are de ned as follows.
Finally, we set q = q^q1^q2. It turns out that q can be computed in polynomial
time w.r.t. q [
I j= q [a1 : : : ; ak] if and only if J j= q[a1 : : : ; ak]:
This result applies to our Datalog rewriting of E L TBoxes. Indeed, for an arbitrary E L KB K = hT ; Ai, we have that M(PT [A) is a split and A-connected interpretation. The intuition behind the argument is as follows. We show that M(PT [ A) is split by noticing that rules encoded in PT do not allow for the derivation of facts of the form R(oB; a) for a 2 Ind(A) and oB 2 Aux. To see that M(PT [ A) is A-connected, we just recall that M(PT [ A) is minimal and, hence, all the derived facts must be \grounded" w.r.t. the facts in A. Theorem 2. Let K = hT ; Ai be an E L knowledge base. Then, M(PT [ A) is a split and A-connected interpretation.
Hence, for an arbitrary k-ary CQ q and for each k-tuple of individuals ha1; : : : ; aki, we have that M(PT [ A) j= q [a1 : : : ; ak] if and only if ha1; : : : ; aki 2 cert(q; K).
Note that q is a rst-order query, and we are unaware of systems
capable of evaluating rst-order queries over Datalog programs. Therefore, we
next show how to transform q into a Datalog query hQP ; QC i such that
ha1; : : : ; aki 2 cert(q; K) if and only if PT [ A [ QC j= QP (a1 : : : ; ak). We
construct such a Datalog query hQP ; QC i by applying to q a simpli ed version
of the Lloyd-Topor transformation [
De nition 1 (Datalog Rewriting). Let q(~x) be a k-ary CQ whose quantied variables are among ~y; let Cyc, Fork6=, and Fork= be as speci ed above; let hPred( 1; R1); t1i, : : :, hPred( n; Rn); tni be an arbitrary enumeration of Fork=; let p0; p1; : : : ; pn be fresh predicates; and let Named be a built-in with a predetermined, possibly in nite Herbrand interpretation N = fNamed(a) j a 2 NI g. Query QC then contains the following safe Datalog rules: p0(~x; ~y) q;
^ v2avar(q)[Fork6=[Cyc
Named(v) pi(~x; ~y)
pi 1(~x; ~y); Named(ti ) pi(~x; ~y)
pi 1(~x; ~y); QP (~x) pn(~x; ~y)
^ t;t02Pred( i;Ri) t = t0 for 1 for 1 i i n n (1) (2) (3) (4) One may think that the recursive de nition of predicates pi for 1 i n could be simpli ed by writing QP (~x) p0(~x; ~y) : : : pn(~x; ~y) and by de ning each pi as: pi(~x; ~y)
Named(ti ) pi(~x; ~y)
Vt;t02Pred( i;Ri) t = t0 Unfortunately, these rules are not safe. Safe rules, on the one hand, provide us with a clear and unambiguous semantics. On the other hand, unsafe rules are also computationally more expensive for bottom-up computation, since each variable in the head may be bound to an arbitrary individual in the universe of the program. For this reason, we prefer our, slightly more involved, solution. Proposition 4. For an arbitrary k-ary conjunctive query q, query hQP ; QC i can be computed in polynomial time w.r.t. the size of q.
Proof. We note that q can be computed in polynomial time w.r.t. the size of
q [
In [
ha1; : : : ; aki 2 cert(q; K) if and only if PT [ A [ QC j= QP (a1; : : : ; ak): Finally, we investigate the complexity of our rewriting procedure. Theorem 4. Let K = hT ; Ai be an EL KB, let q be a k-ary CQ, and let ha1; : : : ; aki be a tuple of individuals. We can decide PT [A[QC j= QP (a1; : : : ; ak) in polynomial time w.r.t. the size of K and in non-deterministic polynomial time with respect to the size of both K and q.
Proof. We have already argued that the size of Datalog program PT depends
linearly on the size of the TBox T and that the Datalog rewriting hQP ; QC i
can be computed in Ptime w.r.t. q. Also, we note that the arity of predicates
and the number of variables occurring in PT [ A [ QC do not depend on K.
Finally, from an implementation point-of-view (as suggested in [
In this paper, we introduce a query rewriting approach to query answering in EL. In our approach, the process of computing the certain answers to a CQ q over an EL KB K = hT ; Ai is divided into two distinct steps. A rst preprocessing step in which the TBox T is transformed into a Datalog program PT , whose size is linear in T . Then, at query time, the query q is independently rewritten into a Datalog query hQP ; QC i, whose size is polynomial in q. Finally, computing cert(q; K) amounts to evaluating the Datalog query hQP ; QC i over PT [ A. dr. Lutz et al.
In future, we plan to extend our approach to deal with ELH?
have already proposed a combined approach for query answering in this DL [