One of the most prominent reasoning techniques for query answering is query rewriting. The last years a wide variety of query rewriting systems has been proposed. All of them accept as input a CQ Q and a xed ontology O and produce a rewriting for Q, O. However, in many real world applications ontologies are very often dynamic|that is, new axioms can be added or existing ones removed frequently. In this paper we study the problem of computing a rewriting for a CQ over an ontology that has been evolved (i.e., a set of new axioms has been added to O), by exploiting the information computed for the extraction of the initial rewriting. Our goal is to avoid computing the target rewriting from scratch or repeating computations that have already been conducted for the initial rewriting. We study the problem theoretically and we specify the form that the input information must have for the e cient computation of the new rewriting based on some of the known query rewriting systems (QuOnto, Requiem, Rapid, Naya). Moreover, we present a practical algorithm which we implemented and evaluated against the query rewriting system Requiem obtaining encouraging results.
Conjunctive query answering constitutes a central problem of many applications
which involve managing datasets consisting of very large sets of data assertions.
The last years conjunctive query answering has become one of the most
prominent reasoning tasks in Description Logics. This is witnessed by both the high
number of publications on this research area, to mention only few [
Unfortunately, it is proved that the problem of answering conjunctive queries
over ontologies expressed using expressive ontology languages (like those
underpinning the Web Ontology Language OWL 2) is of high computational
complexity [
Hitherto, numerous query rewriting systems have been developed in the
literature [
Recently we studied the problem of computing a query rewriting of a CQ w.r.t. an ontology that has been contracted directly from a rewriting of the CQ w.r.t. the initial ontology [19]. In the current paper we study the following problem: Given a query Q, an ontology O, a set R computed for the extraction of a rewriting of Q w.r.t. O and a set of axioms ON , compute a rewriting of Q w.r.t. O [ ON from R and O without repeating the same computations8. Firstly, we study the problem theoretically and we specify the form that the input R must have according to query rewriting system used (Requiem, QuOnto, Naya and Rapid). Next, we provide a novel algorithm that computes a rewriting for the extended ontology which is compatible with the inference systems underpinning these rewriting systems. We prove that our algorithm is correct in the sense that when evaluating the computed rewriting over the system's data we obtain the whole set of correct answers. 1 http://www.dis.uniroma1.it/quonto/ 2 http://www.cs.ox.ac.uk/isg/tools/Requiem/ 3 http://ontop.inf.unibz.it/ 4 http://mais.dia.uniroma3.it/Nyaya/Home.html 5 http://www.image.ece.ntua.gr/~achort/rapid.zip 6 http://code.google.com/p/iqaros/ 7 https://wiki.nci.nih.gov/display/VKC/NCI+Thesaurus+Terminology 8 Note that we assume O [ ON to be consistent w.r.t. the input data and we don't handle cases where inconsistencies need to be resolved
Finally, we have optimised and implemented our algorithm using Requiem and conducted an experimental evaluation using both benchmark ontologies and an E LHI fragment of the realistic medical ontology GALEN. We compared the performance of our system to the performance of the query rewriting system Requiem and we obtained encouraging results.
The algorithm proposed in this paper can be exploited by cutting-edge
technologies like ontology-based data access and ontology-based data integration.
For instance, an innovative algorithm for ontology-based data integration under
ontology evolution has recently been suggested in the literature [
In this section we introduce all necessary terminology and demonstrate the relevant de nitions assuming that the reader is familiar with rst-order logic.
We use standard notions of rst-order constants, variables, function symbols terms, substitutions, predicates, atoms, (ground) formulae, sentences, clauses and entailment (j=). A fact is a ground atom and an instance is a nite set of facts. A tuple (vector) of variables (constants) is denoted by ~x (~a). For a formula, with (~x) we denote that ~x are the free variables of , while for a substitution, is the result of applying to . Satis ability and entailment are de ned as usual.
Existential Rules An existential rule [
Many popular Horn ontology languages, such as DL-LiteR [
Every existential rule of a normalised E LHI or DL-LiteR ontology can be translated to at most two clauses. We often make no distinction between an existential rule and its equivalent representation as one or two clauses. Also, as query rewriting algorithms operate over clauses, for the rest of this work we assume that ontologies are sets of clauses.
Given two clauses c1, c2 we say that c1 subsumes c2 if there exists a substitution such that every literal in c1 appears in c2.
Queries A query Q is a nite set of sentences containing a distinct query predicate Q. A tuple of constants ~a is an answer to Q w.r.t an ontology O and instance I if the arity of ~a agrees with the arity of Q and O [ I [ Q j= Q(~a). We denote with cert(Q; O [ I) the answers to Q w.r.t. O [ I. A query Q is a union of conjunctive queries (UCQ) if it is a set of datalog rules containing Q in the head but not in the body. A UCQ is a conjunctive query (CQ) if it has exactly one rule. To simplify the presentation, we often abuse notation and identify a CQ with the only rule it contains.
Query Rewriting Intuitively, a rewriting of Q w.r.t. O is another query that
captures all the information from O relevant for answering Q over an arbitrary
instance I [
De nition 1. A datalog rewriting of a CQ Q w.r.t. an ontology O is a set of datalog rules R s.t. for each instance I using only predicates from O we have cert(Q; O [ I) = cert(R; I) The rewriting R is a UCQ rewriting if it is a UCQ with query predicate Q whose body atoms contain only predicates from O.
Inference Rules An inference rule is a n+1 relation on clauses. We denote the
elements of such a relation as hc1; : : : cn; ci, and we call them inferences. We say
that an inference hc1; : : : cn; ci is sound if fc1; : : : cng j= c. An inference system
is a collection of inference rules. Proof of a clause c from a set of clauses N
w.r.t. is a sequence of clauses c1; : : : ; cm, s.t. c = cm and each ci is either an
element of N or else the conclusion of an inference by from N [ fc1; : : : ; ci 1g.
For a set of clauses N and a clause c, we denote with N ` c, if there exists a
proof of c from N using the rules of the inference system . A set of clauses N
is called saturated with respect to , and we denote it as N , if the conclusion
of any inference from N by is an element of N [
In this section we present an algorithm for computing a rewriting of a query Q w.r.t. an ontology O0, given a set R computed for the extraction of the initial rewriting of Q w.r.t. an ontology O such that O O0. We specify the nature of R according to the inference system used. Our goal is to reuse as much of the information in R as possible, focusing on computing only the new elements that are due to the information in O0 n O. The input data are assumed to be consistent w.r.t. the input ontology O0 and under this assumption one can ignore the constraint rules.
The next example illustrates the key ideas behind the algorithms we will present next.
Example 1. Consider an ontology O consisting of the following clauses: c1 = P (x; y) c2 = S(x; f (x))
S(x; y) A(x) and consider also the query Q = Q(x) S(x; y) ^ P (x; y). Applying QuOnto or Rapid to compute a rewriting for Q w.r.t. O will produce the following inferences: hQ; c1; Q1i, where Q1 = Q(x) hQ1; c2; Q2i, where Q2 = Q(x)
S(x; y) A(x) The set of queries R = fQ; Q1; Q2g consists a rewriting of Q w.r.t. O.
Assume now that the original ontology O is revised by a domain expert who adds the new clause c3 = S(x; f (x)) B(x), obtaining the new ontology O0 = O [ fc3g. A rewriting for Q w.r.t. O0 consists of the set R0 = R [ fQ3g, where Q3 = Q(x) B(x) which can again be computed using any state-of-theart algorithm.
However, in the process of computing R0 all systems we are aware of would recompute also all queries in R0 n fQ3g although these have been computed before. Instead, R0 can be computed from R by applying the inference rules of a rewriting algorithm using only the newly added clauses. For example, by the inference hQ1; c3; Q3i, we can obtain Q3 in one step, without recomputing Q1 and Q2. }
The previous example suggests that to compute a rewriting for an extended ontology we can only perform the new inferences that are \activated" by the newly added clauses. Initially, these will be the inferences that contain in their premises a clause from the new set of clauses. However, these inferences will trigger new ones since their conclusions along with clauses from O0 may infer new clauses, which again, in the same way, may \activate" new inferences, and so forth until no new inferences can be triggered.
The ability to e ciently compute a rewriting for an extended ontology given a precomputed rewriting depends greatly on the inference system used to compute the input rewriting. Many inference systems, like the ones that underpin Rabid and QuOnto, consist of inference rules whose conclusion is always a CQ. Next, we de ne formally this class of inference systems.
De nition 2. A query-oriented inference rule is an inference rule of the form hQ; c1; : : : ; cn; Q0i, where Q, Q0 are CQs and c1; : : : ; cn are clauses. A queryoriented inference system is an inference system that consists of query-oriented inference rules.
However, the rewriting algorithms that rely on query-oriented inference
systems can only support ontologies of low expressivity, like DL-LiteR ontologies.
For more expressive ontologies, such as E LHI-ontologies, rewriting algorithms
that rely on di erent inference systems are required. As the following example
illustrates, one such system whose inference system does not satisfy De nition
2 is Requiem [
Example 2. Consider the ontology O of Example 1 and the query Q = Q(x) R(x; y) ^ P (x; y). Requiem will initially compute the saturation of Q, O by conducting the following inferences: hc1; c2; c4i, where c4 = P (x; f (x))
A(x); hQ; c4; Q0i, where Q0 = Q(x)
R(x; f (x)) ^ A(x) obtaining the saturation set Rs = fc4; Q; Q0g [ O. Then, Requiem will return the rewriting R = fQ; c1g of Q w.r.t. O by extracting the function-free subset of Rs. Assume now that the knowledge in O is revised and we add the clause c5 = R(x; y) P (x; y) hence obtaining the new ontology O0 = O [ fc5g. A rewriting for Q w.r.t. O0 consists of the set R0 = fQ; Q1; c1; c5g, where Q1 = Q(x) A(x).
Suppose that we attempt to compute R0 from R and O0. Then, according to the inference system that underpins Requiem, the inferences (2), (3) and the inferences: hc5; c4; c6i, where c6 = R(x; f (x))
A(x) hQ; c6; Q00i, where Q00 = Q(x)
A(x) ^ P (x; f (x)) hQ0; c6; Q1i and hQ00; c4; Q1i, where Q1 = Q(x)
A(x) will be performed to compute the new rewriting. In contrast to the previous example, we observe that R0 cannot be computed from R, O0 without repeating the intermediate inferences (2) and (3).
However, we can avoid repeating these inferences by applying the inference rules of Requiem to the set fc5g [ Rs. In this way, Requiem will compute R0 by performing only the inferences (4), (5), (6) and (7). } The previous example suggests that there are query rewriting algorithms that compute a rewriting by producing new intermediate clauses which may be discarded from the output. It also illustrates that for such algorithms, the rewriting of an extended ontology can be e ciently computed if, instead of the initial rewriting R for a CQ Q and an ontology O, the saturation of the set Q [ O by the inference system of the algorithm is provided. Intuitively, this is a reasonable claim since a clause with functionals, which is not contained in the nal rewriting, and a new clauses can trigger new inferences, crucial for the nal form of the rewriting.
Next we de ne formally the class of inference systems that these algorithms are relied on.
De nition 3. An axiom-oriented inference rule is an inference rule of the form hc1; : : : ; cn; ci, where the set of clauses fc1; : : : ; cng contains at most one query and c is either a query or a clause. An axiom-oriented inference system is an inference system that consists of axiom-oriented inference rules. 3.1
The Add Algorithm As described previously, it is possible to compute a rewriting of a query Q w.r.t. an ontology O0, given an inference system and a set of clauses R generated (2) (3) (4) (5) (6) (7) Algorithm 1 Add(O; R; ON ; )
system.
Output: R0 new rewriting an inference
Pick clauses c01; : : : ; c0j 1 2 R, clauses c0j ; : : : ; c0k 1 2 ON , clauses c0k; : : : ; c0m 2 O s.t. hc01; : : : ; c0m; c0i is an inference by .
Pick clauses c010; : : : ; c0s0 1 2 Rnew, clauses c0s0; : : : ; c0t0 2 ON [ O [ R s.t. hc010; : : : ; c0t0; c00i is an inference by .
from Q and an ontology O, with O O0, by performing only the necessary new inferences. The nature of the set R depends on the type of the inference system. If is query-oriented then R constitutes a rewriting of Q w.r.t. O, while if is axiom-oriented then R is the set (Q [ O) . It is reasonable to store R, as for large ontologies its recomputation from scratch can be a very time consuming process.
Such a detailed algorithm that relies on a query-oriented or an axiom-oriented inference system is depicted in Algorithm 1. Algorithm Add accepts as input the ontology O, the set of clauses R, the set of new clauses ON = O n O and a sound 0 inference system . Then, the algorithm proceeds as follows. First, it initialises a new set Rnew which will contain the new inferred clauses. Next, it attempts to produce a new clause from R and ON via the inference system (line: 3). The new clause is added to the set Rnew. However, the inference of the rst step may not produce new clauses, as clauses from O do not necessarily appear in its premises, although they may be required for this purpose. For instance, if R is a UCQ rewriting then the clauses of O are not contained in R. For this reason, the algorithm conducts an extra inference which contains in its premises clauses from R and from both O and ON (line: 5). The algorithm adds the produced clause to Rnew. Then, the algorithm adds to Rnew the conclusion of any inference that has in its premises clauses from Rnew and from any of the sets ON , O, R (line: 7). The algorithm iterates over these three types of inferences until no new clauses can be produced up to variable renaming. When this process terminates, the algorithm returns the function-free subset of Rnew [ R.
It is easy to see that the worst-case complexity of Add is the same with the complexity of the query rewriting system based on the inference system , since Add performs only inference rules of . Next we show the correctness of Algorithm 1.
Theorem 1. Let O be an ontology, let Q be a CQ and be a sound query (resp. axiom)-oriented inference system. Let R be a UCQ rewriting for Q, O (resp. R = (Q [ ON ) ) and let ON be a nite set of clauses. When applied to O, R, ON and Algorithm 1 terminates. Let R0 be the set of clauses produced by the algorithm; then, R0 is a UCQ (resp. datalog) rewriting for Q; O [ ON . Proof. First we will show that the algorithm terminates. Since the rewriting of Q w.r.t. O [ ON is nite and , on which Algorithm 1 is based on, is sound we conclude that the algorithm does not produce in nite set of clauses up to variable renaming. Also, given that it stops when no new clauses up to variable renaming can be produced we conclude that the algorithm will terminate.
It su ces to prove for each istance I that cert(R0; I) = cert(Q; O [ ON [ I). It is obvious that cert(R0; I) cert(Q; O [ ON [ I), since the algorithm is based on a sound inference system and hence, produces only sound clauses.
Now we will prove that cert(Q; O [ ON [ I) cert(R0; I). Let R00 be a UCQ (resp. datalog)-rewriting for Q, O [ ON resulted from a rewriting algorithm that relies on the query (axiom)-oriented inference system . Since cert(Q; O [ ON [ I) = cert(R00; I), it su ces to prove that for every clause c s.t. R00 ` c it holds that R0 ` c. Since R R0, we will prove this only for the clauses resulted from a sequence of inferences that at least one of them contains in its premises clauses from ON . The proof will be by induction.
Suppose that c is produced by one inference, i.e. that c1; : : : ; ci 1 2 R, ci; : : : ; cj 1 2 O, cj ; : : : ; cn 2 ON exist s.t. hc1; : : : ; ci; : : : ; cj ; : : : ; cn; ci is an inference by . Then, it is obvious from the structure of the algorithm that either c 2 R0 or there is a c0 2 R0 s.t. c0 is equivalent up to variable renaming with c, i.e. R0 ` c. Suppose that c is produced after k inferences, i.e. Q [ O [ ON ` ck and c1; : : : ; cn 1 2 O, cn; : : : ; cm 2 ON exist s.t. hck; c1; : : : ; cn; : : : ; cm; ci is an inference by . Since ck 2 R0, from induction hypothesis, it is easy to conclude from the structure of Algorithm 1 that either c 2 R0 or there is a c0 2 R0 s.t. c0 is equivalent up to variable renaming with c, i.e. R0 ` c tu
A potential performance bottleneck of Algorithm 1 is that it may perform unnecessary inferences. For example, if a clause c produced from the inference of line 3 is subsumed from another clause of R or Rnew then every inference that has in its premises c or any of its descendants is unnecessary since both c and its descendants are redundant. Hence, in each of the lines 4, 6, 8 a produced clause should be added to Rnew only if it is not subsumed from another clause of R or Rnew. Also, the performance of the algorithm will be further optimised if we execute the standard subsumption checking algorithm over the input set R and then serve the resulted set, instead of R, as input to the algorithm. 4
We have implemented Algorithm 1 enhanced with the optimisations described in the previous section in a prototype tool called AddOnto. AddOnto also performs subsumption checking before returning the nal rewriting. Our implementation relies on the query rewriting system Requiem9. We have evaluated AddOnto tool using both benchmark ontologies expressed in DL-LiteR and a realistic ontology expressed in ELHI.
Regarding DL-LiteR, we used the framework proposed in [
For the evaluation of our tool we proceeded as follows. Initially we removed a rule r from each test ontology for every query. Next, we transformed the rules of the contracted ontology to clauses obtaining the set O and we computed the saturation R (since the inference system that underpins Requiem is axiom-oriented) of Q [ O via . Then, we executed AddOnto with input hO n ON ; R0; ON ; i, where the set ON contains the clauses that correspond to the rule r and R0 is R after the subsumption checking and is computed o -line. This process was repeated for each rule of the ontology, and we recorded the mean time among the total set of its rules. Tables 1, 2 show the average computation time (in ms) for every ontology and query. Since our implementation is based on Requiem we compare our implementation against the standard (nonmodi ed) version of Requiem. For Requiem we measured the time to compute the rewriting of each query w.r.t. the whole respective ontology from scratch. Note that both tools returned rewritings of the same size so we do not present these numbers for brevity. 9 However, we plan to use other systems as well in the future.
From the results demonstrated in the Tables 1 and 2, we note that in most cases the time required to calculate the new rewriting is negligible. In half of the DL-LiteR ontologies and queries (Table 1) AddOnto computes a new rewriting almost instantaneously in less than 0.05 seconds. The results obtained for the GALEN ontology were also encouranging (Table 2) and especially for the query Q5 compared to the corresponding performance of Requiem. Concerning the DL-LiteR ontologies, a large di erence compared to Requiem can be noticed in P 5X as well as in ontologies U X and AX which are particularly hard. Note, however, that we were not able to obtain results for ontology AX query Q5 as Requiem that we based AddOnto on did not terminate after 9 hours. It is clear from both tables that AddOnto outperforms Requiem. This is an expected result since AddOnto is provided with the saturation of (O n frg) [ Q and has to compute only the new inferences resulted from the addition of r.
Concerning the case of the ontology AX and the query Q5 we noticed in [19] that there is a speci c rule (r98 = AssistiveDevice(x) ! Device(x)) in AX whose removal reduces the size of the rewriting signi cantly. Hence, we removed this rule from the ontology and we calculated with Requiem a rewriting of Q5 w.r.t. AX n fr98g. The output minimal rewriting was computed in 29 seconds and contained 2,546 CQs. Then, we executed AddOnto with ON = fr98g obtaining, in 17 minutes, the nal minimal rewriting of Q5 w.r.t. AX, which contains 32,921 CQs. This result leads us to the conclusion that the rule r98 causes explosion of the size of the rewriting. Also, we conclude that the order by which the rules are taken during the resolution process is crucial for the e ciency of the algorithm.
Although in all cases AddOnto outperforms Requiem, we notice that there are some relatively hard cases for AddOnto. Such cases are the computation of the rewriting of the queries Q4, Q5 w.r.t. ontology P 5X and of the rewriting of the queries Q2, Q3, Q4 w.r.t. ontology AX. We will further investigate the reasons for these time performances with graphs of the time performance vs the added rule, in order to observe the behaviour of each rule separately.
The graph of P 5X ontology that appears in Fig. 1 shows that the time performance increases signi cantly when the rules r4 (AUX0(x; y) ! edge(x; y)), r9 (AUX1(x; y) ! edge(x; y)) and r13 (AUX2(x; y) ! edge(x; y)) are added. This happens because, as it was pointed in [19] these rules are crucial for the nal form of the output rewriting, as when any of them was removed the size of the rewriting was greatly decreased. This can be easily explained by observing that Fig. 1. Time performance of AddOnto for the computation of the minimal rewriting for ontologies P 5X and AX for CQs Q4, Q5 and Q2{Q4 respectively when an rule r added. the atoms AUX0(x; y), AUX1(x; y), AUX2(x; y) have many descendants in the ontology, while the atom edge(x; y) appears in all test queries.
Regarding AX ontology, we notice from the corresponding graph of Fig. 1 that for every added rule and every query, the time performance of AddOnto is above a certain value. For instance, in the case of query Q3 the algorithm requires more than 15 seconds to compute the new rewriting, for any ON . This is a surprising result since it was shown in [19] that there are rules in AX, like the rule r151 = Ability(x) ! 9y:AUX0(x; y)), that do not a ect the rewriting. However, after further investigation of the time results of each subprocess, we noticed that the process of the subsumption checking that is performed in the end of AddOnto is mostly responsible for this behaviour. For instance, in the case of Q4, when rule r151 is added, then 5,386 ms are required only for the subsumption checking process. This can be explained by the large size (3,163 CQs) of the input set to the subsumption checking process. 5
In the current paper we have presented and studied a novel problem in the area of query rewriting. More precisely, we have studied query rewriting of xed queries over evolved ontologies|that is, over ontologies for which one or more axioms have been added. We presented a practical algorithm which, given a set of clauses R generated from an input query Q and an ontology O, and given a set of axioms ON to be added to O, computes a rewriting R0 for Q, O [ ON without recomputing the same clauses. Our algorithm is compatible with rewriting calculi such as those underpinning Requiem, QuOnto, Naya and Rapid. We have implemented and evaluated the algorithm over the rewriting system Requiem and have obtained encouraging results.
Regarding future work we plan to investigate the same problem under the assumption that the new set of axioms may introduce inconsistencies in the Knowledge Base. We also plan to further evaluate our algorithm rstly by using larger and more realistic ontologies and secondly against other state-of-the-art rewriting systems. 18. Rosati, R., Almatelli, A.: Improving query answering over DL-Lite ontologies. In: Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning (KR 2010) (2010) 19. Tsalapati, E., Stoilos, G., Stamou, G.B., Koletsos, G.: Query rewriting under ontology contraction. In: Krotzsch, M., Straccia, U. (eds.) RR. Lecture Notes in Computer Science, vol. 7497, pp. 172{187. Springer (2012) 20. Venetis, T., Stoilos, G., Stamou, G.: Incremental query rewriting for OWL 2 QL.
In: Proceedings of the 25th International Workshop on Description Logics (DL 2012), Rome, Italy (2012)