Query answering has become a prominent reasoning task in Description Logics. This is witnessed not only by the high number of publications on the topic in the last decade, but also by the increasing number of query answering engines. A number of systems provide full conjunctive query (CQ) answering capabilities, including [1, 23, 25, 4, 11]. A common feature of these approaches is that they rely on existing technologies for relational or deductive databases. They focus on lightweight DLs like DL-Lite and E L, and they use query rewriting to reduce the problem of answering a query over a DL ontology to a database query evaluation problem. For more expressive DLs that are not tractable in combined complexity, however, CQs (with the complete first-order semantics) are not yet supported by current reasoning engines. A range of algorithms has been designed, but they serve for theoretical purposes such as showing complexity bounds and are not amenable to practical implementation. The only exception is the rewriting algorithm implemented in the REQUIEM system, which covers E LHI [23], an expressive extension of E L for which standard reasoning is EXPTIME-hard. In this paper, we contribute to the development of practical query answering systems beyond DL-Lite and E L. We consider Horn-SHIQ, the Horn fragment of the popular DL SHIQ that underlies OWL DL. It combines all the expressive features of DL-Lite and E L, and simultaneously extends them with transitive roles, qualified number restrictions and some universal quantification. Standard reasoning tasks in Horn-SHIQ are already EXPTIME-hard in combined complexity but, due to the absence of disjunction, they are polynomial in data complexity. Since in Horn-SHIQ models are significantly more complex than in DL-Lite and (most dialects of) E L, extending existing query rewriting techniques is not straightforward. The main contribution of this paper is a query answering method for Horn-SHIQ that appears to be promising for practicable systems, as confirmed by the experimental evaluation of a prototype implementation. - The core of the method is a novel query rewriting technique which transforms an input query q into a union Q of CQs (a UCQ) such that the answers of q over an ontology O = hT ; Ai with TBox T and ABox A coincide with the answers over A ? This work was supported by the Austrian Science Fund (FWF) grants P20840 and T515.
of a Datalog program comprising Q and some rules to complete A, showing Datalogrewritability of CQ answering in Horn-SHIQ.
– Naturally, the set Q may be exponential in the size of q in the worst case, but in practice we obtain rewritings Q that are of manageable size for real world ontologies. This is mostly due to the fact that new queries are only generated taking into account the anonymous domain elements implied by the terminology. Notably our algorithm is worst-case optimal in both data and combined complexity.
– We describe a prototype implementation of the approach that uses off-the-shelf Datalog reasoners. Despite being preliminary and lacking sophisticated optimizations, it shows that the approach is promising. It can answer queries efficiently over HornSHIQ ontologies and scales down nicely to DL-Lite, where it is competitive with state of the art query rewriting systems.
– The technique works for full Horn-SHIQ and arbitrary CQs, but the implemented version does not support transitive (or more generally, non-simple) roles in the query. To keep presentation simple, we present here only the case without transitive roles, and refer to [6, 9] for a more general version with transitive roles and richer queries formulated in weakly DL-safe Datalog. 2
Horn-SHIQ The syntax and semantics of Horn-SHIQ is defined in the usual way. A role is a role name p or its inverse p . A Horn-SHIQ TBox T in normal form is a set of role inclusion axioms r v s, transitivity axioms trans(r), and general concept inclusion axioms (GCIs) of the forms (F1) A1 u: : :uAn vB, (F2) A1 v8r:B, (F3) A1 v 9r:B, and (F4) A1v 61 r:B,where A1; : : : ; An; B are concept names and r; s are roles. Axioms (F3) are called existential. W.l.o.g. we consider only Horn-SHIQ TBoxes in normal form [16, 17]. We call s transitive in T , if trans(s) 2 T or trans(s ) 2 T , and we call s simple in T , if there is no transitive r in T s.t. r vT s, where v is the reflexive transitive closure of f(r; s) j r v s 2 T or inv(r) v inv(s) 2 T g. Only simple roles are allowed in axioms of the form (F4).
An ABox A is a set of assertions A(a) and r(a; b), where A is a concept name, r a role, and a, b are individuals; the set of all individuals is denoted by NI. An ontology is a pair (T ; A) of a TBox T and an ABox A. The semantics is given by interpretations I = h I ; I i in the usual way.
A Horn-ALCHIQ TBox is a Horn-SHIQ TBox with no transitivity axioms. HornALCHIQu TBoxes are obtained by allowing the conjunction r1 u r2 of roles r1 and r2, interpreted (r1 u r2)I = r1I \ rI . We let inv(r1 u r2) = inv(r1) u inv(r2) and 2 assume w.l.o.g. that for each role inclusion r v s of a Horn-ALCHIQu TBox T , (i) inv(r) v inv(s) 2 T , and (ii) s 2 fp; p g for a role name p. For a set W and a concept or role conjunction = 1 u : : : u m, we write W for f 1; : : : ; mg W . Conjunctive Queries A conjunctive query (CQ) is an expression of the form q(u) p1(v1); : : : ; pm(vm) where each pi(vi) is an atom of the form A(x) or r(x; y), where A is a concept name and r is a role, x; y are variables, and q is a special query predicate not occurring elsewhere. For convenience, we may identify such a CQ with the set of its atoms, and use q(u) (or simply q) to refer to it. We call u S1 i m vi the distinguished variables of q. A match for q in I is a mapping from variables in q to elements in I such that (t) 2 pI for each atom p(t) of q. The answer to q over O is the set of all c 2 Njuj I such that in every model I of O some match for q exists with (u) = (c)I . Elimination of Transitivity. As usual, transitivity axioms roles can be eliminated from Horn-SHIQ TBoxes. To obtain a Horn-ALCHIQ TBox T that is also in normal form, we can use the transformation from [16]. This transformation preserves satisfiability and, provided that queries contain only simple roles, also query answers (answers are not preserved for arbitrary queries unless the notion of match is suitably relaxed). In the rest of the paper we describe a procedure for answering CQs in Horn-ALCHIQu. 3
For answering CQs in Horn DLs usually the canonical model property is employed [7,
21, 2]. In particular, for a consistent Horn-ALCHIQu ontology O = (T ; A), there
exists a model I of O that can be homomorphically mapped into any other model I0 of
O. We show that such an I can be built in three steps:
(
For Step (
B(y)
B(x) r(x; y) ?(x) Definition 1. Let T be a Horn-ALCHIQu TBox and let I be an interpretation. A GCI M v 9S:N is applicable at e 2 I if (a) e 2 M I , (b) there is no e0 2 I with (e; e0) 2 SI and e0 2 N I , (c) there is no axiom M 0 v 9S0:N 0 2 T such that e 2 (M 0)I , S S0, N N 0, and S S0 or N N 0. An interpretation J obtained from I by an application of an applicable axiom M v 9S:N at e 2 I is defined as: - J = I [ fdg with d a new element not present in I (we call d a successor of e), - For each concept name A and each o 2 J , we have o 2 AJ if (a) o 2 I and o 2 AI ; or (b) o = d and A 2 N . - For each role name r and o; o0 2 J , we have (o; o0) 2 rJ if (a) o; o0 2 I and (o; o0) 2 rI ; or (b) (o; o0) = (e; d) and r 2 S; or (c) (o; o0) = (d; e) and inv(r) 2 S. We denote by chase(I; T ) a possibly infinite interpretation obtained from I by applying the existential axioms in T . We require fairness: the application of an applicable axiom can not be infinitely postponed.
We note that chase(I; T ) is unique up to renaming of domain elements. As usual in DLs, it can be seen as a ‘forest’: the application of existential axioms simply attaches ‘trees’ to an arbitrarily shaped model I.
Theorem 1. Let O = (T ; A) be a Horn-ALCHIQu ontology. Then O is consistent iff A [ cr(T ) consistent. Moreover, if O is consistent, then (a) chase(MM (A [ cr(T )); (T )) is a model of O, and (b) chase(MM (A [ cr(T )); (T )) can be homomorphically mapped into any model of O.
The proof of Theorem 1 can be found in [9]; see [21] for a proof of a similar result.
Observe that checking consistency of O = (T ; A) reduces to evaluating the Datalog program A [ cr(T ). We note that (T ) can be computed in exponential time in the size of T : the calculus only infers axioms of the form M v B and M v 9S:N , where M; N are conjunctions of atomic concepts, B is atomic and S is a conjunction of roles, and there are exponentially many such axioms. 4
The following theorem, which is immediate from Theorem 1, allows us to concentrate on models obtained by the chase procedure.
r1 A v 9(r u r2):(B u A3) r1
A3 (a) Example 1 A1 x1 r2 x3 A2; A
r3 A4 x4
A3
r3; r4 (b) Example 2 q1 A1 x1 A2 x2 r2
r3 x3 A3 A4 x4 Theorem 2. Let O = (T ; A) be a Horn-ALCHIQu ontology. Then A [ cr(T ) is consistent iff O is consistent. Moreover, if O is consistent, then ans(O; q) = ans(IO; q), where IO = chase(MM (A [ cr(T )); (T )).
Computing ans(IO; q) is still not trivial, as IO can be infinite. Hence, we rewrite q into a set Q of CQs such that ans(IO; q) = Sq02Q ans(MM (A [ cr(T )); q0), that is, we can evaluate them over the finite MM (A [ cr(T )).
The intuition is the following. Suppose q has a non-distinguished variable x, and that there is some match in IO such that (x) is an object in the ‘tree part’ introduced by the chase procedure, and it has no descendant in the image of . Then for all atoms r(y; x) of q, the “neighbor” variable y must mapped to the parent of (x). A rewrite step makes a choice of such an x, and employs an existential axiom from (T ) to ‘clip off’ x, eliminating all query atoms involving it. By repeating this procedure, we can clip off all variables matched in the tree part and obtain a query with a match in MM (A [ cr(T )).
Definition 2 (Query rewriting). For a CQ q and a Horn-ALCHIQu TBox T , we write q !T q0 if q0 can be obtained from q in the following steps: (S1) Select in q an arbitrary non-distinguished variable x such that there are no atoms of the form r(x; x) in q. (S2) Replace each role atom r(x; y) in q, where y is arbitrary, by the atom inv(r)(y; x). (S3) Let Vp = fy j 9r : r(y; x) 2 qg, and select some M v 9S:N 2 (T ) such that (a) fr j r(y; x) 2 q ^ y 2 Vpg S, and (b) fA j A(x) 2 qg N . (S4) Drop from q each atom containing x. (S5) Rename each y 2 Vp of q by x. (S6) Add the atoms fA(x) j A 2 M g to q.
We write q !T q0 if q = q0 and q0 = qn for some finite rewrite sequence q0 !T q1 !T qn, n 0. Furthermore, we let rewT (q) = fq0 j q !T q0g. Example 1. The query q1(x1) A1(x1); r1(x1; x2); A2(x2); r2(x2; x3); A3(x3); r3(x2; x4); A4(x4) is depicted on the left hand side of Figure 1a. The node in bold corresponds to the answer variable x1. Assume that Av9(r u r2):(B u A3) and Av9(r u r3 u r4 ):(B O q
(
Query Rewriting Saturation (4) (6) (5)
Datalog Translation (7)
Datalog
Engine
answers
(
(7) Datalog rules uA3) are in (T ). If we pick for (S1) the variable x3, we get Vp = fx2g and we can select A v 9(r u r2):(B u A3) 2 (T ), as it satisfies (S3.a) and (S3.b). After performing (S4), (S5) and (S6) we obtain the rewritten query q10(x1) A1(x1); r1(x1; x3); A2(x3); A(x3); r3(x3; x4); A4(x4). Intuitively, we can safely remove from q1 all atoms containing x3 because the added atom A(x3) ensures that whenever q10 has a match so does q1. Example 2 (ctd). Now we consider the query q2(x1) A1(x1); r2(x1; x2); A2(x2); r3(x2; x3); A3(x3); r1(x1; x4); A4(x4); r4(x3; x4) in Figure 1b. We choose the variable x3, replace r4(x3; x4) by r4 (x4; x3) in step (S2), and get Vp = fx2; x4g. Intuitively, if (x3) is a leaf in a tree-shaped match , then x2 and x4 must both be mapped to the parent of (x3). Since the GCI A v 9(r u r3 u r4 ):(B u A3) in (T ) satisfies (S3.a,b), we can drop the atoms containing x3 from q2, and perform (S5) and (S6) to obtain the rewritten query q20(x1) A1(x1); r1(x1; x3); r2(x1; x3); A4(x3); A2(x3); A(x3).
Now we can state our main result (see [9] for the proof of a more general result): Theorem 3. Suppose O = (T ; A) is a consistent Horn-ALCHIQu ontology and let q be a CQ. Then ans(O; q) = Sq02rewT (q) ans(MM (A [ cr(T )); q0).
By the above reduction, we can answer q over O = (T ; A)) by evaluating rewT (q) over MM (A[cr(T ) or, equivalently, by evaluating the Datalog program rewT (q)[A[ cr(T ) and collecting the tuples u with q(u) in the minimal model. We note that rewT (q) is finite and computable in time exponential in the size of T and q: rules in rewT (q) use only relation names and variables that occur in q and T . Furthermore, the grounding of rewT (q) [ A [ cr(T ) is exponential in the size of O, but polynomial for fixed T and q. By the complexity of Datalog, it follows that the resulting algorithm is exponential in combined but polynomial in data complexity; this is worst-case optimal [7].
To evaluate the feasibility of the new rewriting, we have implemented a prototype system CLIPPER,3 which supports CQ answering over Horn-SHIQ ontologies (non-simple 3 http://www.kr.tuwien.ac.at/research/systems/clipper/ Algorithm 1: Answering CQs via Query Rewriting
Input: Horn-SHIQ ontology O = (T ; A), Conjunctive Query q Output: query results T Normalize(T ) ; T ElimTrans(T ) ;
(T ) Saturate(T ) ; Q Rewrite(q; (T )) ; cr(T ) CompletionRules(T ) ; P = A [ cr(T ) [ Q ; ans fu j q(u) 2 MinimalModel(P)g; return ans ;
B Eliminate Transitive Roles
B TBox Saturation
B Query Rewriting
B Completion Rules
B Datalog Translation B Call Datalog Reasoner roles are disallowed in queries). To the best of our knowledge, it is the first such system for Horn-SHIQ (under the standard semantics of first-order logic), and in expressiveness subsumes similar DL-Lite and E L reasoning engines (see below).
We describe the architecture of CLIPPER in Figure 2, and the main steps in
Algorithm 1. CLIPPER is implemented in Java and uses OWLAPI 3.2.2 [13] for parsing
ontologies. It accepts an ontology O = (T ; A) and a CQ q in the SPARQL syntax as
input. For efficiency reasons we implemented a lightweight ontology representation: all
concepts, roles and individuals are encoded as integers; the conjunction of concepts and
roles are stored in hash sets. Since we often need to manipulate large tables of axioms,
we built inverted indexes over such axioms to support fast lookup and matching.
Ontology Preprocessing. This component is responsible for (
Query Preprocessing. This component simply parses CQs in SPARQL syntax and converts them into the internal format.
Saturation. This component exhaustively applies the saturation rules in Table 1 on TBox. We use the index structure to find which rules can be applied and the new axioms are generated incrementally.
Query Rewriting. This component uses Algorithm 2 to rewrite the input q. It implements the rewriting step from Definition 2, exhaustively traversing all existential axioms in (T ) for all the non-distinguished variables. The index structure helps the system efficiently search through the set of existential axioms while rewriting. Datalog Translation. This component generates a Datalog program with the rewritten set of queries Q, the completion rules cr(T ) in Table 2, and the facts in A. Datalog Engine. The resulting program is evaluated using the Datalog engine DLV20101014 [18] or Clingo 3.0.3 [10]. If the program (and hence the ontology) is consistent, its minimal model is returned and the answer tuples are filtered from it. 6
We tested CLIPPER on a Pentium Core2 Duo 2.00GHZ with 2GB RAM under Ubuntu 10.04 and 512MB heap for the Java VM. We conducted the following experiments.
Algorithm 2: Rewrite(q, T )
Input: CQ q with only simple roles; TBox T Output: Rewritten queries of q w.r.t. T rewT (q) ; ; B will be updated from the sub procedure rewrite(q) ; B Call sub procedure return rewT (q); Sub Procedure rewrite (q) rewT (q) rewT (q) [ fqg; foreach non-distinguished variables x of q do if r(x; x) 62 q then
Replace each r(x; y) in q by r (y; x) ; S fr j r(y; x) 2 qg ; P fy j r(y; x) 2 qg ; N foreach M v 9S0N 0 2 T do if S S0 and N N 0 then
Obtain q0 from q by:
begin
(
1. Downscaling test. We compared CLIPPER with other query rewriting systems for DL-Lite, viz. REQUIEM (Perez-Urbina et al. [23]) and PRESTO [25], and found that it is competitive and scales down well on DL-Lite ontologies. We used the ontologies and queries (Q1–Q5) from the REQUIEM test suite, which have been widely used for system tests; in addition we considered the queries in Table 3a.
Table 3b shows the number of rewritten queries and the rewriting time for the ontologies ADOLENA (A), STOCK-EXCHANGE (S), VICODI (V), and UNIVERSITY (U); the rewriting time excludes loading and preprocessing. CLIPPER and PRESTO generated in most cases rule sets of comparable size, and in short time. In a few cases PRESTO generated significantly less rules than CLIPPER, and only for V PRESTO was notably faster. REQUIEM generated in several cases significantly more rules, despite considering the G-version which generates optimized rules (and hence uses considerably more time). The difference seems to be caused by rule unfolding required in their rewriting.
For UNIVERSITY, the only ontology in the suite having an ABox, we evaluated the rewritten queries over four different ABoxes (67k to 320k assertions) using DLV. Interestingly, in all cases the execution times for the three rewritings were very similar; the average runtime of each query on the four ABoxes is shown in brackets. 2. Full Horn-SHIQ. To test CLIPPER on a full Horn-SHIQ ontology, we modified the UOBM ontology [19], which is in SHOIN (D), by dropping or strengthening (in case of disjunctions) non-Horn-SHIQ TBox axioms; the final ontology has 196 TBox axioms. We used ABoxes Ai, 1 i 4, with 20k, 80k, 140k and 200k assertions. The test queries in Table 4a were tailored to require reasoning with Horn-SHIQ constructs A S U unavailable in DL-Lite and E L. Table 4b shows the number of rewritten queries, rewriting time and DLV running time. We see that CLIPPER answered all queries in reasonable time and scaled well (time printed A1/ A2 / A3 /A4). The rewriting times for all the queries are small and at most within a factor of 3. The high number of rules generated for Q3 is due to many different possibilities for deriving some atoms in the query, like Person(x). However, the evaluation still performs well (it stays within a small factor). 7
Since Calvanese et al. introduced query rewriting in their seminal work on DL-Lite [3], many query rewriting techniques have been developed and implemented, e.g. (PerezUrbina et al. [23], Rosati and Almatelli [25], Chortaras et al. [4], Gottlob et al. [11]), usually aiming at an optimized rewriting size. Some of them also go beyond DL-Lite; e.g. Perez-Urbina et al. cover E LHI , while Gottlob et al. consider Datalog . Most approaches rewrite a query into a (union of) CQs; in [25] a non-recursive Datalog program is generated, while Perez-Urbina et al. produce a CQ for DL-Lite and a (recursive) Datalog program for DLs of the E L family. Our approach rewrites a CQ into a union of CQs, but generates possibly recursive Datalog rules to capture the TBox. The closest DL to Horn-S HIQ for which a rewriting technique has been implemented is E LHI [23]. Unlike E LHI , Horn-S HIQ can express functionality, a feature supported by DL-Lite considered relevant for applications. A comparison of both systems on ontologies beyond DL-Lite remains for future work. Our technique resembles Rosati’s for CQs in E L [24], which incorporates the CQ into the TBox before saturation and then (after saturation) translates it into Datalog, resulting in a best-case exponential algorithm. We avoid this by doing a rewrite step only if the TBox has an applicable existential axiom.
Rewriting approaches for more expressive DLs are less common. The most notable exception is Hustadt et al.’s translation of SHIQ terminologies into disjunctive Datalog [15], which is implemented in the KAON2 reasoner. The latter can be used to answer queries over arbitrary ABoxes, but supports only instance queries. An extension to CQs (without transitive roles) is given in [14], but it is not implemented. To our knowledge, also the extension of the rewriting in [23] to nominals remains to be implemented [22]. In [20] a Datalog rewriting is used to establish complexity bounds of standard reasoning in the Horn fragments of SHOIQ and SROIQ, but it does not cover CQs. 8
We presented a rewriting-based algorithm for answering CQs over Horn-SHIQ ontologies. Our prototype implementation shows potential for practical applications, and further optimizations will improve it. Future versions of CLIPPER will support transitive roles and queries formulated in weakly DL-safe Datalog, for which the theoretic foundations have been already developed here and in [9].
As an interesting application, we mention that our method allows to improve reasoning with DL-programs, which loosely couple rules and ontologies [5]. To avoid the overhead caused by the interaction of a rule reasoner and an ontology reasoner of traditional methods, the inline evaluation framework translates ontologies into rules [12, 8]. The techniques of this paper can be faithfully integrated into the inline evaluation framework to efficiently evaluate DL-programs involving Horn-SHIQ ontologies. 2. Cal`ı, A., Gottlob, G., Lukasiewicz, T.: Datalog : a unified approach to ontologies and integrity constraints. In: ICDT’09. pp. 14–30. ACM (2009) 3. Calvanese, D., Giacomo, G.D., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. Autom. Reasoning 39(3), 385–429 (2007) 4. Chortaras, A., Trivela, D., Stamou, G.: Optimized query rewriting for OWL 2 QL. In:
CADE’11. pp. 192–206. Springer-Verlag (2011) 5. Eiter, T., Ianni, G., Lukasiewicz, T., Schindlauer, R., Tompits, H.: Combining answer set programming with description logics for the Semantic Web. Artificial Intelligence 172(1213), 1495–1539 (2008) 6. Eiter, T., Ortiz, M., Sˇ imkus, M., Tran, T., Xiao, G.: Query rewriting for Horn-SHIQ plus rules. In: AAAI’12 (2012), (To appear) 7. Eiter, T., Gottlob, G., Ortiz, M., Simkus, M.: Query answering in the description logic Horn
SHIQ. In: JELIA’08. pp. 166–179. Springer (2008) 8. Eiter, T., Krennwallner, T., Schneider, P., Xiao, G.: Uniform evaluation of nonmonotonic
DL-programs. In: FoIKS’12. LNCS, vol. 7153, pp. 1–22. Springer (March 2012) 9. Eiter, T., Ortiz, M., Sˇimkus, M., Tran, T., Xiao, G.: Query rewriting for Horn-SHIQ plus rules. Tech. Rep. INFSYS RR-1843-12-04, TU Vienna (2012), http://www.kr. tuwien.ac.at/research/reports/rr1204.pdf 10. Gebser, M., Kaufmann, B., Kaminski, R., Ostrowski, M., Schaub, T., Schneider, M.T.:
Potassco: The potsdam answer set solving collection. AI Commun. 24(2), 107–124 (2011) 11. Gottlob, G., Orsi, G., Pieris, A.: Ontological queries: Rewriting and optimization. In:
ICDE’11. pp. 2 –13 (2011)
12. Heymans, S., Eiter, T., Xiao, G.: Tractable reasoning with DL-programs over
Datalogrewritable description logics. In: ECAI’10. pp. 35–40. IOS Press (2010)
13. Horridge, M., Bechhofer, S.: The OWL API: A java API for OWL ontologies. Semantic Web
2(
2040–2045 (2009) 17. Kro¨ tzsch, M., Rudolph, S., Hitzler, P.: Complexity boundaries for Horn description logics.
In: AAAI’07. pp. 452–457. AAAI Press (2007) 18. Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S., Scarcello, F.: The DLV system for knowledge representation and reasoning. ACM ToCL 7(3), 499–562 (2006) 19. Ma, L., Yang, Y., Qiu, Z., Xie, G.T., Pan, Y., Liu, S.: Towards a complete OWL ontology benchmark. In: ESWC’06. pp. 125–139. Springer (2006) 20. Ortiz, M., Rudolph, S., Simkus, M.: Worst-case optimal reasoning for the Horn-DL fragments of OWL 1 and 2. In: KR’10. AAAI Press (2010) 21. Ortiz, M., Rudolph, S., Simkus, M.: Query answering in the Horn fragments of the description logics SHOIQ and SROIQ. In: IJCAI’11. pp. 1039–1044. IJCAI/AAAI (2011) 22. Pe´rez-Urbina, H., Motik, B., Horrocks, I.: Tractable query answering and rewriting under description logic constraints. J. Applied Logic 8(2), 186–209 (2010) 23. Pe´rez-Urbina, H., Motik, B., Horrocks, I.: A comparison of query rewriting techniques for
DL-Lite. In: DL’09. CEUR-WS.org (2009) 24. Rosati, R.: On conjunctive query answering in EL. In: DL’07. CEUR-WS.org (2007) 25. Rosati, R., Almatelli, A.: Improving query answering over DL-Lite ontologies. In: KR’10.
AAAI (2010)