We study conjunctive query answering in the description logic EL, the core of the designated OWL2-EL pro le of OWL2. In particular, we present an approach that allows the use of conventional relational database technology for conjunctive query answering in EL. This approach is inspired by the OWL support in Oracle Database 11g, semantic technologies.
The OWL ontology language is currently being revisited by a W3C working
group with the goal of designing a revised and extended version of OWL, called
OWL2 [
In contrast to OWL2-EL, the design goal of both OWL2-QL and OWL2-RL is to enable the use of database technology for query answering over OWL instance data: many applications access considerable amounts of such data, often in the range of millions of objects. This makes it necessary to store the data in secondary storage and to develop highly e cient querying mechanisms. Relational database systems often satisfy these needs and bene t from decades of research in academia and industry. Thus they are natural candidates for implementing a query processing solution for OWL. However, employing such an approach is rather challenging due to signi cant di erences between relational database systems and OWL: rst, relational systems adopt a closed-world semantics, i.e., all facts that are not explicitly stated to be true are assumed to be false. In contrast, OWL is based on an open world semantics which does not require one to x the truth value of every fact and is more similar to an incomplete database [10]. Second, database systems are unaware of the intensional part of an OWL ontology (called henceforth the TBox).
In OWL2-QL and OWL2-RL these di culties are addressed in di erent ways. In a nutshell, the OWL2-QL approach suggests employing a backward chaining approach while OWL2-RL suggests forward chaining. In both cases the instance data (called the ABox) is stored as a relational database instance. In OWL2-QL, a query q is rewritten into a new query q that takes into account the TBox. This rewriting is independent of the data. The resulting query q is passed to the database system to retrieve answers. In this way, OWL2-QL allows the use of an o -the-shelf relational database system with the help of an external query rewriting component. In contrast, query answering in OWL2-RL relies on a data preprocessing phase. This phase is initiated after each modi cation of the instance data and adds data that is entailed by the explicitly given data and the TBox. Data preprocessing is independent of the queries to be answered. To actually answer a query, it then su ces to pass it to the relational query engine without rewriting. The OWL2-RL approach thus suggests that the data management facilities of the database system should be modi ed to incorporate a data preprocessing phase, but the query engine is left untouched. Notably, OWL2-RL and the described approach to query answering is used in the Oracle Database 11g semantic technologies [18].
In this paper, we study conjunctive query answering in the description logic E L using relational database systems. Since E L can be viewed as the core of the OWL2-EL pro le and is successfully used in the design of large-scale ontologies, adding e cient querying capabilities is of immediate practical use, e.g., in applications of OWL in medical informatics in which an ABox is used to describe medical records and where a medical E L ontology, such as SNOMED CT, assigns a meaning to the medical terms used in these records [12, 13]. Unsurprisingly, very large ABoxes are frequently encountered in such applications and e cient querying is a crucial requirement. Conjunctive query answering in E L has also been studied in [9, 14, 8], but not in the context of database systems.
The pure backward chaining approach of OWL2-QL cannot be applied to E L since that approach is limited to DLs for which the data complexity of conjunctive query answering is in LogSpace, while it has been shown that E L is PTime-hard in this respect [6]. Pure forward chaining is not applicable either because it may cause the introduction of in nitely many new database objects (due to the use of existential restrictions on the right-hand side of concept inclusions in a TBox). For these reasons, we present a novel approach to conjunctive query answering that has some similarity to both of the approaches above. It can be summarized as follows similarly to Oracle 11g semantic technologies, we use a data preprocessing phase that adds new data to the database. This phase depends on the ABox and the TBox, but not on the queries to be answered. The data added during our preprocessing phase is auxiliary: it is only used internally by the ontology-aware database system for query answering and hidden from the user. To answer a query, we rst rewrite it and then pass it on to the database query engine. Hence, our approach shares the main virtues of the two approaches for OWL2-QL and OWL2-RL above; in particular it leaves the query engine of the relational database system unchanged. Technically, our approach relies on the fact that, in EL, conjunctive queries can be answered by considering a single canonical model. During the preprocessing phase, we complete the data in the database to such a model. The main challenge of pursuing this approach is to work with a nite canonical model while still giving correct answers to all conjunctive queries.
It is worth mentioning that the query rewriting in our approach is of a rather di erent nature than the rewriting done for OWL2-QL: it does not correspond to backward chaining and is independent of the data and of the TBox. Another signi cant di erence from OWL2-QL is that data preprocessing needs only quadratic time and query rewriting needs only linear time. In contrast, the query rewriting step of OWL2-QL may induce an exponential blowup.
The remainder of this paper is organized as follows. In Section 2, we introduce the description logic EL and conjunctive query answering. Section 3 then provides an overview of our approach, introduces canonical models, and provides a rst example. The data preprocessing phase is described in Section 4 and query rewriting is discussed in Section 5. In Section 6, we conclude with pointing out future research issues. 2
We brie y introduce the description logic EL and conjunctive queries. In EL, concepts are built according to the syntax rule
C ::= A j > j C u D j 9r:C where, here and in the remaining paper, A ranges over concept names taken from a countably in nite set NC, r ranges over role names taken from a countably in nite set NR, and C; D range over concepts. A TBox is a nite set of concept inclusions C v D, and an ABox is a nite set of concept assertions A(a) and role assertions r(a; b), where a; b range over a countably in nite set NI of individual names. A knowledge base is a pair (T ; A) with T a TBox and A an ABox.
As usual, an interpretation is a pair ( I ; I ) with I a non-empty domain and I an interpretation function that maps each concept name A to a subset AI I , each role name r to a binary relation rI I I , and each individual name a to an element aI 2 I The interpretation function is extended to composite concepts by setting
>I = I (C u D)I = CI \ DI (9r:C)I = fd 2
I j 9e 2
I : (d; e) 2 rI ^ e 2 CI g: An interpretation I satis es a concept inclusion C v D if CI DI , a concept assertion A(a) if aI 2 AI , and a role assertion r(a; b) if (aI ; bI ) 2 rI . I is a model of a TBox T (ABox A) if it satis es all concept inclusions in T (assertions in A). It is a model of a knowledge base K = (T ; A) if it is a model of T and A. For a concept inclusion or assertion , we write K j= if is satis ed in all models of K. If empty, A is simply omitted.
Let NV be a countably in nite set of variables. Together, the set of NV of variables and the set NI of individual names form the set NT of terms. A conjunctive query is an expression of the form 9u:'(v; u), where { u = u1; : : : ; un and v = v1; : : : ; vm are vectors of variables and { ' is a conjunction of concept atoms A(t) and role atoms r(t; t0), where A ranges over concept names, r over role names, and t; t0 are terms from the set v [ u [ NI.
The variables in u are called quanti ed variables, and the variables in v are answer variables. We call the query k-ary if there are k answer variables, use var(q) to denote the set of all variables in q, qvar(q) for the set of quanti ed variables, avar(q) for the set of answer variables, and term(q) for the terms in q. Slightly abusing notation, we write 2 q if the concept or role atom occurs in q.
Let I be an interpretation and q = 9u:'(v; u) a conjunctive query. A match for I and q is a mapping : term(q) ! I such that (a) = aI for all a 2 term(q) \ NI and all atoms in q are satis ed, i.e., { (t) 2 AI for all A(t) 2 q and { ( (t); (t0)) 2 rI for all r(t; t0) 2 q.
If v = v1; : : : ; vk with (vi) = aiI for 1 i k, then is called an (a1; : : : ; ak)match for I and q. If such a match exists, we write I j= q[a1; : : : ; ak]. A certain answer for a k-ary conjunctive query q and a knowledge base K is a tuple (a1; : : : ; ak) such that a1; : : : ; ak occur in K and, for each model I of K, there is an (a1; : : : ; ak)-match for I and q. We use cert(q; K) to denote the set of all certain answers for q and K. This de nes the querying problem studied in this paper: given an E L-knowledge base K and a conjunctive query q, we want to compute cert(q; K). Observe that the de nition of certain answers re ects the open world semantics of ABoxes: we quantify over all possible models of K instead of treating the ABox itself as a model.
Without loss of generality, we admit only concept names in a conjunctive query, instead of composite concepts. Indeed, it is easily possible to unfold an EL-concept into the query. For example, the query 9u:r(u; v) ^ (A u 9s:B)(u) can be unfolded into 9u; u0:r(u; v) ^ A(u) ^ s(u; u0) ^ B(u0).
In the remainder of this paper, we make the unique name assumption, i.e., we assume that aI 6= bI for all interpretations I and all a; b 2 NI with a 6= b. The following (easy to prove) lemma shows that assuming UNA does not impact the certain answers.
Lemma 1. Let K be a knowledge base, q a k-ary conjunctive query, and let a1; : : : ; ak 2 NI. If there is a model I of K and an (a1; : : : ; ak)-match for I and q, then there is a model I0 of K that respects the UNA and an (a1; : : : ; ak)match for I0 and q. 3
Every EL knowledge base K = (T ; A) has a canonical model IK that enjoys
many pleasant properties [
IK := Ind(A) [ NIaux AIK := fa 2 ind(A) j K j= A(a)g [ fxC 2 NIaux j K j= C v Ag rIK := f(a; b) 2 ind(A) ind(A) j r(a; b) 2 Ag[ f(a; xC ) 2 ind(A) NIaux j K j= 9r:C(a)g[ f(xC ; xD) 2 NIaux NIaux j K j= C v 9r:Dg aIK := a for all a 2 ind(K) Among the pleasant properties of IK is that it can be used to answer instance queries. Such a query has the form C(a) and is entailed by a knowledge base K if aI 2 CI for all models I of K. It is well-known that C(a) is entailed by K i a 2 CIK , and thus we can answer instance queries w.r.t. K by looking only at the single model IK [4]. Since A can be viewed as being a fragment of IK, this observation suggests that we can use a database system to answer instance queries as follows: we store A as a database, complete A to IK in a preprocessing phase, and then just pass instance queries to the database system.
In principle, it is the same approach that we want to use for conjunctive queries. Unfortunately, for conjunctive queries q it is not true that (a1; : : : ; ak) 2 cert(q; K) i IK j= q[a1; : : : ; qk] for all a1; : : : ; ak 2 NI with k the arity of q. To see this, let us consider four examples. First, take the knowledge base K1 = (T1; A1) with
T1 = fA v 9r:Bg A1 = fA(a); A(b); r(a0; c0); r(b0; c0)g q1 = 9u:r(v; u) ^ r(v0; u) We have (a; xB) 2 rIK1 and (b; xB) 2 rIK1 , and thus IK1 j= q[a; b]. However, (a; b) 2= cert(q1; K1) because it is easy to nd a model I of K1 with I 6j= q1[a; b]. Second, take Similarly to our rst example, it is not hard to see that IK2 j= q2[a], but a 2= cert(q2; K2). Our third example is K3 = (T3; A3) with
T2 = fA v 9r:B u 9s:Bg A2 = fA(a)g q2 = 9u:r(v; u) ^ s(v; u) T3 = fA v 9r:B; B v 9s:Bg A3 = fA(a)g q3 = 9u:r(v; u) ^ s(u; u) Again, IK3 j= q3[a], but a 2= cert(q3; K3). All the three examples above show situations in which matches can be found in the canonical model, matches that do not exist in the unraveling of this model. Our last example is K4 = (T4; A4) with
T4 = fA v Ag A4 = fB(a)g q4 = 9u:B(v) ^ A(u) illustrates a di erent di culty: while xA 2 AIK4 , in the unraveled model the interpretation of A is empty: hence, IK4 j= q4[a], but a 2= cert(q4; K4). This situation can be detected by observing that the value x4 is not reachable from a by a role chain in IK4 .
In principle, all of these problems can be overcome by replacing IK with its unraveling into a less constrained, tree-like model. In the following, we introduce unraveling as a general operation on models of a knowledge base. Let K be a knowledge base and I a model of K. We use Ind(A)I to denote the set faI j a 2 Ind(A)g. A path in I is a nite sequence d0r1d1 rndn, n 0, where d0 2 Ind(A)I and, for all i < n, (di; di+1) 2 riI+1. We use paths(I) to denote the set of all paths in I. If p 2 paths(I), then tail(p) denotes the last element dn in p. Now the unraveling J of I is de ned as follows:
J := paths(I) aJ := aI AJ := fp j tail(p) 2 AI g rJ := f(d; e) j d; e 2 Ind(A)I ^ (d; e) 2 rI g [ f(p; p re) j p; p re 2 I g where \ " denotes concatenation. The following result is proved in [8] for the extension of E L with inverse and functional roles and for the case of 0-ary queries. An extension to k-ary queries is straightforward.
Lemma 2. Let K be a knowledge base and UK the unraveling of IK. For all kary conjunctive queries q and individual names a1; : : : ; ak, we have (a1; : : : ; ak) 2 cert(q; K) i UK j= q[a1; : : : ; ak].
Alas, UK may be in nite and thus we cannot use it as a database. The solution is to continue working with IK, but to rewrite q into q such that each match of q in IK can be reproduced as a match of q in UK and vice versa, thus IK j= q [a1; : : : ; ak] i UK j= q[a1; : : : ; ak] for all a1; : : : ; ak 2 NI. We defer a formal de nition and concrete examples of this rewriting to Section 5. 4
We describe the data preprocessing phase of our approach to conjunctive query answering in E L, where we insert additional, auxiliary data. The purpose of this phase is to complete the ABox A initially stored in the database to (a fragment of) the canonical model IK. In principle, the auxiliary data has to be updated each time that A and T are modi ed (for the purposes of query answering, however, it makes sense to assume that T is essentially immutable). To keep the presentation simple, we concentrate on the case where the auxiliary data is computed from scratch. In an actual implementation, it would be preferable to modify the auxiliary data in an incremental way when data is inserted to or deleted from A.
Let K = (T ; A) be the knowledge base over which queries are to be answered. We store the ABox A as data in a database system in the obvious way: individual names become database objects, concept names become unary tables, and role names become binary tables. When we understand A as a database, we denote it with Adb and use ans(q; Adb) to denote the set of answers that a relational database system returns for q over the database Adb. As explained in the previous section, cert(q; K) and ans(q; Adb) are not identical in general. The precompletion phase extends Adb to a database Adb that represents (a fragment of) the canonical model IK. In the following, we present details of how this completion can be achieved using the query mechanism of a relational system.
In Adb, we use the elements of NIaux as additional database objects, assuming
that NIaux \ NI = ;. We also introduce an additional unary database table Aux
that is used to identify elements of NIaux and distinguish them from individual
names in A.4 First, we use a reasoner such as CEL [
IT := NIaux AIT := fxC 2 NIaux j T j= C v Ag rIT := f(xC ; xD) 2 NIaux NIaux j T j= C v 9r:Dg This model should not to be confused with the canonical model IK of the knowledge base K; in fact, IT is obviously a fragment of IK. It can be computed in polynomial time and its size is at most quadratic in the size of T . To properly insert IT into the database, we need a notion of reachability between domain elements of IT . For xC ; xD 2 IT , we say that xD is reachable from xC if there are xC0 ; : : : ; xCn 2 IT , n 0, such that xC0 = xC , xCn = xD, and for all i < n, 4 Thus, Aux denotes the complement of Ind(A)IK , as introduced in Section 3. for all C; A 2 sub(T ) such that for some C v D 2 T , A is a conjunct of D do extend the table A with ans(qC ; A(dib)) for all C; 9r:D 2 sub(T ) such that for some C v E 2 T , 9r:D is a conjunct of E do if ans(qC ; A(dib)) 6= ; then extend the table r with f(a; xD) j a 2 ans(qC ; A(dib))g extend the table Aux with Reach(xD) extend the table A with AIT \ Reach(xD), for each concept name A extend the table s with sIT \ (Reach(xD) Reach(xD)), for each role name s endif there is an r 2 NR with (xCi ; xCi+1 ) 2 rIT . We use Reach(xC ) to denote the set of those xD 2 IT that are reachable from xC (including xC itself). Now, the data preprocessing phase constructs a sequence of ABoxes A(d1b); : : : A(dkb) starting (0) = Adb and then repeatedly applying the procedure from Figure 1 to with Adb produce A(dib+1) from A(dib). In the gure, qC denotes the result of converting the concept C into a tree-shaped conjunctive query with one answer variable that denotes the root (c.f. the remark at the end of Section 2) and \C is a conjunct of D" includes the case where C = D. The repeated application of this procedure stops when no more changes to the data occur.
It is not hard to see that Adb represents IK restricted to those domain elements that are reachable (along roles) from some individual name in A. This restriction to reachable elements is not (only) an optimization: it is needed in order to eliminate the problem illustrated in the fourth example (K4; q4) in previous section. We now analyze the complexity of the preprocessing phase. Lemma 3. Let n be the number of individual names in A and m the number of subconcepts in T . Then the procedure in Figure 1 is applied at most n m times. We note that n and m are linear in the size of A and T , and that the bound given in Lemma 3 is only an upper bound that is unlikely to occur in practice. Let us use Adb to denote the nal database that is constructed in the preprocessing phase. It is not hard to see that the size of Adb is bounded by O(n m), where n and m are as in Lemma 3. 5
This section shows how to rewrite a given conjunctive query q into a (domain independent) rst-order query q such that cert(q; K) = ans(q ; Adb) for every knowledge base K = (T ; A), i.e., the answers that a relational system returns for q are precisely the certain answers for q and K. We assume that Adb (de ned in the previous section) is stored in a relational database system. We remind the reader that domain independent rst-order queries are nothing else but SQL queries. In particular, every domain independent FO query can be rewritten into an SQL query in linear time.
To proceed, we use several auxiliary de nitions. Let q denote the smallest relation on term(q) that includes the identity relation, is transitive, and satis es the following closure condition: ( ) if there are r(s; t); r(s0; t0) 2 q with t q t0, then s q s0.
The relation q is central to our rewriting procedure. Recall from Section 3 that the goal of query rewriting is to produce a query q such that matches of q in IK can be reproduced as matches of q in the unraveling UK of IK and vice versa. Intuitively, UK is produced from IK by keeping the Ind(A)-part of IK intact and relaxing the NIaux-part into a collection of trees. The importance of ( ) can be seen when assuming t = t0: then ( ) describes a non-tree situation in the query since t = t0 has two predecessors s and s0. Therefore, we should avoid matches of q to the NIaux-part of IK where (s) 6= (s0) as we will not be able to reproduce them in UK. The case where t q t0 instead of t = t0 can be understood similarly.
It is not hard to verify that q is an equivalence relation and can be computed in time polynomial in the size of q. For each equivalence class of q, choose a representative t 2 . Let { Fork= be the set of pairs (T; ) with T term(q) and an equivalence class of q such that for some r 2 NR, T = ft 2 term(q) j 9t0 2 : r(t; t0) 2 qg, and T is of cardinality at least two; { Fork6= qvar(q) be the set of quanti ed variables v such that for some s; s0; t 2 term(q) and r; r0 2 NR with r 6= r0, we have r(s; v); r0(s0; t) 2 q and v q t; { Cyc qvar(q) be the set of quanti ed variables v such that there are r0(t0; t00); : : : ; rn 1(tn; t0n) 2 q; n 0; with v = ti for some i
n and t0i q ti+1 mod n for all i < n.
It is not hard to see that Fork=, Fork6=, and Cyc can be computed in time polynomial in the size of q. The rewritten query q is de ned as q ^ q1 ^ q2, where q1 and q2 are as follows: q1 := q2 := ^ ^ v2avar(q)[Fork6=[Cyc (ft1;:::;tkg; )2Fork= :Aux(v) ( Aux(t ) ! (t1 = t2 ^ ^ tk 1 = tk) ) Note that the construction of q does not depend on K and can be carried out in polynomial time. Moreover, q is at most linear in the size of q. To see this, rst note that the number of conjuncts in q1 is bounded by the number of variables in q. Regarding q2, let Fork= = f(T1; 1); : : : ; (T`; `)g. It is not hard to see that v0 r Fig. 2. Example Query. jT1j+ +jT`j is bounded by the number of role atoms in q, and thus the number of conjuncts in q2 is also bounded linearly in the size of q. Since q is a conjunct of q , it is readily checked that q is domain independent.
The following theorem states the correctness of our approach to conjunctive query answering in E L using a database system. Its proof is given in the full version of this paper available at http://lat.inf.tu-dresden.de/ clu. Theorem 1. cert(q; K) = ans(q ; Adb).
We now give three examples for query rewriting: { For tree-shaped queries and for queries without quanti ed variables almost no query rewriting is needed: in both cases q = q ^ Vv2avar(q) :Aux(v). { The queries q1 to q3 from Section 3 are rewritten as follows. In the case of q1 = 9u:r(v; u) ^ r(v0; u), q consists of the equivalence classes fv; v0g and fug. Assume that the chosen representative for fv; v0g is v. In this example, q2 and Fork= are the most important ingredients of the rewriting, and we have q1 = 9u::Aux(v) ^ :Aux(v0) ^ r(v; u) ^ r(v0; u) ^ (Aux(u) ! v = v0): In the case of q2 = 9u:r(v; u) ^ s(v; u), the Fork6= part of q1 is the most important ingredient of the rewriting and we have
q2 = 9u::Aux(v) ^ :Aux(u) ^ r(v; u) ^ s(v; u): Finally, reconsider q3 = 9u:r(v; u) ^ s(u; u). Here, the Cyc part of the rewriting plays the crucial role, and we have
q3 = 9u::Aux(v) ^ :Aux(u) ^ r(v; u) ^ s(u; u) { Let q be the query shown in Figure 2, where all variables are quanti ed.
Then q consists of the equivalence classes fv0; v1; v2g, fv3; v4; v5g, fv6g, and fv7g. Assume that the chosen representative for fv3; v4; v5g is v3. Thus, we have q = q ^
Aux(v6) ! (v3 = v4) ^ Aux(v7) ! (v4 = v5) ^
Aux(v3) ! ((v0 = v1) ^ (v1 = v2)) { Let qnc be the query that has no answer variables and whose body is an n-clique, i.e., qnc = 9v0; : : : ; vn 1: ^ r(vi; vj ) i;j<n Then q consists of a single equivalence class fv0; : : : ; vn 1g. Assume that the representative is v0. Then we have (qnc) = qnc ^ :Aux(v0) ^ ^ :Aux(vn 1) ^
Aux(v0) ! ((v0 = v1) ^ ^ (vn 2 = vn 1)) which can be simpli ed to the equivalent qnc ^ :Aux(v0) ^ ^ :Aux(vn 1): As illustrated by the last example, we can drop a conjunct from q2 whenever the variable occurring in its precondition occurs in a conjunct of q1. 6
We nd it very satisfactory that for the widely-used E L fragment of OWL2 there is a rather direct way to use relational database systems for sound and complete query answering. The work presented in this paper, however, is only a rst step and leaves a lot of room for further investigation. In particular, it would be interesting to carry out experiments to evaluate the feasibility of our approach in practice. To reduce the (polynomial) blowup produced by the data preprocessing phase, one could study a more careful form of preprocessing that materializes only certain concept and role names in the database and takes care of the remaining ones using query rewriting. Another obvious direction is to extend the approach to more expressive variants of E L. For example, we conjecture that adding the bottom concept and role hierarchies is simple. In contrast, transitive roles and left/right identity statements might pose more di culties. Finally, one could also try to adopt the proposed technique for DL-Lite, thus establishing an alternative approach to query answering for that family of DLs. Since DLLite is lacking the nite model property, we cannot store a canonical model in a database (as in the case of E L). However, it is possible that a nite representation of such a model can be used. In that case, the query rewriting step can be expected to depend both on the original query and on the TBox. 4. F. Baader, S. Brandt, and C. Lutz. Pushing the EL envelope. In Proceedings of the Nineteenth International Joint Conference on Arti cial Intelligence (IJCAI'05), pages 364{369. Professional Book Center, 2005. 5. F. Baader, S. Brandt, and C. Lutz. Pushing the el envelope further. In In Proceedings of OWLED2008, 2008. 6. D. Calvanese, G. de Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Data complexity of query answering in description logics. In Proceedings of KR2006, pages 260{270. AAAI Press, 2006. 7. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, A. Poggi, and R. Rosati.
Linking data to ontologies: The description logic DL-LiteA. In Proceedings of OWLED2006, volume 216 of CEUR-WS, 2006. 8. A. Krisnadhi and C. Lutz. Data complexity in the EL family of DLs. In Proceedings of DL2007, volume 250 of CEUR-WS, 2007. 9. M. Krotzsch, S. Rudolph, and P. Hitzler. Conjunctive queries for a tractable fragment of OWL 1.1. In Proceedings of ISWC2007, volume 4825 of LNCS, pages 310{323. Springer, 2007. 10. A.Y. Levy. Obtaining complete answers from incomplete databases. In In Proceedings of VLDB1996, pages 402{412, 1996. 11. C. Lutz and F. Wolter. Conservative extensions in the lightweight description logic EL. In Proceedings of the 21th Conference on Automated Deduction (CADE-21), volume 4603 of LNAI, pages 84{99. Springer, 2007. 12. C. Patel, J.J. Cimino, J. Dolby, A. Fokoue, A. Kalyanpur, A. Kershenbaum, L. Ma, E. Schonberg, and K. Srinivas. Matching patient records to clinical trials using ontologies. In Proceedings of ISWC2007, volume 4825 of LNCS, pages 816{829.
Springer, 2007. 13. J. Patrick and P. Budd. Automatic conversion of clinical notes into snomed ct at point of care. In Proceedings of HIC2006 and HINZ2006, pages 209{213, 2006. 14. R. Rosati. On conjunctive query answering in EL. In Proceedings of DL2007, volume 250 of CEUR-WS, 2007. 15. N. Sioutos, S. de Coronado, M.W. Haber, F.W. Hartel, W.L. Shaiu, and L.W.
Wright. NCI thesaurus: a semantic model integrating cancer-related clinical and molecular information. Journal of Biomedical Informatics, 40(1):30{43, 2006. 16. K.A. Spackman. Managing clinical terminology hierarchies using algorithmic calculation of subsumption: Experience with SNOMED-RT. Journal of the American Medical Informatics Association, 2000. 17. H.J. ter Horst. Completeness, decidability and complexity of entailment for rdf schema and a semantic extension involving the owl vocabulary. Journal of Web Semantics, 3(2-3):79{115, 2005. 18. Z. Wu, G. Eadon, S. Das, E.I. Chong, V. Kolovski, M. Annamalai, and J. Srinivasan. Implementing an inference engine for RDFS/OWL constructs and userde ned rules in oracle. In Proceedings of ICDE2008, pages 1239{1248. IEEE, 2008.