We present an approach for using schema knowledge from the TBox to optimise the evaluation of SPARQL queries. The queries are evaluated over an OWL ontology using the OWL Direct Semantics entailment regime. For conjunctive instance queries, we proceed by transforming the query into an ABox. We then show how the TBox and this (small) query ABox can be used to build an equivalent query where the additional query atoms can be used for reducing the set of possible mappings for query variables. We also consider arbitrary SPARQL queries and show how the concept and role hierarchies can be used to prune the search space of possible answers based on the polarity of variable occurrences in the query.
In this paper, we consider the SPARQL 1.1 query language [
Over the last decade, much e ort has been spent on optimising standard reasoning
tasks such as entailment checking, classification, or realisation (i.e., the computation
of instances of all concepts and roles) [
The contribution of this paper is two-fold: first, we present an optimisation that is
applicable to conjunctive instance queries. We show that one can compute an equivalent
query qˆ for a given query q by replacing the variables in q with fresh individual names.
We then perform realisation, i.e., we materialise entailed concept and role assertions,
for the queried TBox and (small) query ABox. Replacing the individual names again
with the corresponding variable names then yields qˆ. The additional query atoms in qˆ
can then be used for reducing the set of possible mappings for query variables. Second,
we propose an optimisation for also reducing the possible mappings for concept and
role variables by exploiting the polarity of variable occurrences in the query and the
(precomputed) concept and role hierarchies. We provide a prototypical implementation
and evaluation of the polarity based optimisation, which shows that it can lead to an
improvement of up to two orders of magnitude in the execution times of some queries.
The polarity based optimisation can be found in more detail in our earlier work [
Due to lack of space, we do not introduce the Description Logic SH IQ, which we use
throughout the paper. For further details, we refer interested readers to the DL handbook
[
In this paper, we consider conjunctive instance queries and complex queries, which can also contain axioms with variables in place of concept or role names. Such queries are important in the context of SPARQL since SPARQL’s OWL Direct Semantics entailment regime allows for such queries. Conjunctive instance queries are a subset of all such SPARQL queries, but they di er from database-style conjunctive queries in that they do not allow for existentially quantified or non-distinguished variables. Definition 1 (Conjunctive Instance and Complex Queries). Let S = (NC; NR; NI) be a signature, K a knowledge base over S, and V = VC ]VR ]VI a countably infinite set of variable names (concept variables in VC, role variables in VR, and individual variables in VI) disjoint from NC, NR, and NI. Let A 2 NC, r 2 NR, and x; y 2 VI. A concept atom is an expression A(x) and a role atom is an expression r(x; y). A conjunctive instance query q is a non-empty set of (concept or role) atoms. The set of SH IQ concept templates (or concept templates for short) over S and V is built as the set of SH IQ concepts, where a concept variable can be used in place of a concept name, and a role variable in place of a role name. A role axiom template has the form r v s where r; s 2 NR [ VR. 4 http://trowl.eu 5 http://swertia.org
abbreviate c v d and d v c as c d. A finite set of role axiom templates, concept axiom templates, and (concept or role) atoms is called a complex query. We use Var(q) for the set of variables in q. and jVar(q)j is called the arity of q.
Let q = fat1; : : : ; atng be a (conjunctive instance or complex) query. A total function : Var(q) ! NC [NR [NI is a mapping for q over K if (v) 2 NC if v 2 VC, (v) 2 NR if v 2 VR, and (v) 2 NI if v 2 VI. Let X = fx1; : : : ; xng Var(q) a subset of the variables of q, and M = f 1; : : : ; mg a set of mappings for q. The projection of X over M is the set MjX = ffx 7! ag j 2 M; x 2 X and (x) = ag. A mapping is a certain answer for q over K if K j= (at) for each at 2 q, written K j= (q), where (at) ( (q)) is the result of replacing each v 2 Var(at) (Var (q)) with (v). We denote the set of all certain answers for q over K with ans(K ; q). 3
In this section, we use the DL SH IQ and we present a technique that uses
approximate reasoning algorithms in order to optimise the evaluation of conjunctive instance
queries. Approximate reasoning algorithms can either be sound and incomplete [
Similarly, we define approximate query answering algorithms: Definition 3 (Approximate Query Answering Algorithm). Let K = hT ; Ai be a knowledge base, and q a conjunctive instance query. An approximate query answering algorithm apprQA(K ; q) returns a pair of sets of (total) functions from Var(q) to individual names from K hK[q]; P[q]i such that: 1. if 2 K[q], then 2 ans(K ; q), and
Without loss of generality, in the rest of the paper we assume that for every approximate instance retrieval or query answering algorithm K[ ] \ P[ ] = ; holds. It is not di cult to see that an obvious approach to develop an approximate query answering algorithm apprQA is to use an approximate instance retrieval algorithm inst. A naive method to do this is to execute inst and take K[ ] [ P[ ] for each query atom and then compute the join of these sets, where we straightforwardly interpret the mappings as relations. The following example illustrates that some possible answers can be easily rejected.
For ease of presentation we represent mappings as tuples in the examples that follow, i.e., abusing notation, K[at] is a set of individuals for concept atoms and a set of pairs of individuals for role atoms and K[q] is a set of n-tuples, n being the arity of q. Example 1. Let K = hT ; Ai be a knowledge base and q = fC(x); r(x; y); D(y)g a query with variables hx; yi. Suppose that (possibly as a result of inst(K ; C(x)), inst(K ; r(x; y)) and inst(K ; D(y))) we have K[C(x)] = fag, P[C(x)] = fbg, K[r(x; y)] = fha; ci)g, P[r(x; y)] = fhb; di; hb; eig, K[D(y)] = fcg and P[D(y)] = fdg. Even if we do not know K , we can conclude that ha; ci is a certain answer to q, since a 2 K[C(x)], ha; ci 2 K[r(x; y)] and c 2 K[D(y)]. However, only hb; di is a possible answer for q since b 2 P[C(x)], hb; di 2 P[r(x; y)] and d 2 P[D(y)]; hb; ei cannot be an answer for q since although hb; ei 2 P[r(x; y)] and b 2 P[C(x)], e < K[D(y)] [ P[D(y)].
Algorithm intersecQans (see Algorithm 1) formalises this idea, which we also illustrate in Example 2: Example 2. If we take q from Example 1 in the order given, we first initialise K[q] to fag and P[q] to fbg. During the next iterations, the (preliminary) set K[q] is extended by performing a natural join with the known answers for the current atom at. The set P[q] is extended by performing a natural join of P[q] with both K[at] and P[at] and of K[q] with P[at]. For Example 1, we next process r(x; y) and obtain K[q] = fha; cig and P[q] = fhb; di; hb; eig. We finally process D(y) and keep K[q] = fha; cig and P[q] = fhb; dig.
Concerning the optimisation of algorithm intersecQans, in practice, one would use well-known ordering strategies from the area of databases for the atoms in q in order to reduce the number of intermediate results, e.g., one would prefer joins over connected atoms and join a small relation with a bigger one where possible. The question now is: given a knowledge base K and a query q, how we can further reduce the cardinality of P[q] computed by intersecQans with the aid of inst.
Example 3. Suppose that we have K and q = fC(x); r(x; y); D(y)g as in Example 1 and, in addition, we are given that K j= 9r:> u C v B and inst(K ; B(x)) = hfag; ;i. From Example 2, we have K[q] = fha; cig and P[q] = fhb; dig. In this case, hb; di is no longer Algorithm 1 intersecQans(K ; q) Require: K = hT ; Ai: a SH IQ knowledge base
q: a conjunctive query Ensure: hK[q]; P[q]i: K[q]; P[q] sets of known and possible answers for q 1: for at 2 q do 2: hK[at]; P[at]i := inst(K ; at) 3: if K[q] and P[q] not initialised then 4: hK[q]; P[q]i := hK[at]; P[at]i 5: else 6: K[q] := K[q] ./ K[at] 7: P[q] := (P[q] ./ P[at]) [ (K[q] ./ P[at]) [ (P[q] ./ K[at]) 8: end if 9: end for 10: return hK[q]; P[q]i a possible answer of q. If b would be a possible mapping for x, it would have an rsuccessor (since r(x; y) 2 q) and it would be an instance of C (since C(x) 2 q) and, hence, b should be in K[B(x)] [ P[B(x)] to satisfy the entailed axiom. We now define the notion of restricting atoms such as B(x).
Definition 4 (Restricting Atoms). Let K = hT ; Ai be a knowledge base, q a conjunctive instance query, at a query atom with V ar(at) V ar(q), and inst an approximate instance retrieval algorithm. Then we say that at restricts q if
P[q]jVar(at) \ (K[at] [ P[at])
where hK[q]; P[q]i = intersecQans(K ; q) and hK[at]; P[at]i = inst(K ; at). Example 4. Going back to Example 3, we find that B(x) is indeed a restricting atom for q according to Definition 4 since we have P[q]jfxg = fbg and P[q]jfxg \ (K[B(x)] [ P[B(x)]) = ;, which clearly is a subset of P[q]jfxg.
If we want to preserve the certain answers of q, we should only use restricting atoms that do not change the answers of q. Let q and q0 be conjunctive instance queries such that q0 = q [ fatg. If q and q0 are equivalent queries, i.e., q and q0 yield the same answers over a fixed TBox and any ABox, and at restricts q, then we can safely prune the set of possible answers for q with the help of at. Obviously, we could also use more than one restricting atom to even further restrict q. Since such atoms are not given as input, we address the problem of (e ciently) computing such restricting atoms within an approximate query answering algorithm after showing that using restricting atoms for queries indeed preserves the certain answers.
Lemma 2. Let K = hT ; Ai be a knowledge base, q and q0 two queries such that q0 = q [ fatg, ans(K ; q) = ans(K ; q0), hK[q]; P[q]i = intersecQans(K ; q), hK[at]; P[at]i = inst(K ; at), and at restricts P[q].
and q as input is an approximate query answering algorithm and
In order to define an improved approximate query answering algorithm based on
Lemma 2, we need to find a way of computing such restricting atoms. In the following,
we will see how we can use the TBox for this aim. The proposed query extension
technique is analogous to the use of the chase technique in relational database theory to
reason about conjunctive query containment [
tive function from Var(q) to a set of individual names from NI . The canonical ABox for q w.r.t. f is defined as follows:
Aqf = fB( f (x)) j B(x) 2 qg [ fr( f (x); f (y)) j r(x; y) 2 qg The extended canonical ABox Aˆqf for q w.r.t. f is defined as:
Aˆqf = fB(a) j B 2 NC; a 2 Ind(Aqf ) and hT ; Aqf i j= B(a)g [
fr(a; b) j r 2 NR; a; b 2 Ind(Aqf ) and hT ; Aqf i j= r(a; b)g: The extended query qˆ w.r.t. f and Aˆqf is: qˆ = fB( f (a)) j B(a) 2 Aq g [ fr( f (a); f (b)) j r(a; b) 2 Aˆqf g:
ˆ f fErxoammEplxeam5.pSleu3p.pIonsethwisechaasvee, KthesucacnhotnhiactaKlAj=Bo9xr:o>fuqCisvABqf a=ndfCq(=ax)fC;r((xa)x;;ra(yx);;yD);(Day()yg)g where f maps a variable v 2 fx; y; zg to the individual name av. The extended canonical ABox for the query q w.r.t. f is Aˆqf = fC(ax); r(ax; ay); D(ay); B(ax)g and the extended query w.r.t. Aˆqf is qˆ = fC(x); r(x; y); D(y); B(x)g. Please note that qˆ has the same answers as q (w.r.t. any ABox), because K j= 9r:> u C v B.
Intuitively (see Example 5), the extended query qˆ w.r.t. Aˆqf adds atoms to q that do not change the set of answers of q, which we formalise by the following Theorem:
Given a conjunctive instance query q and a knowledge base K = hT ; Ai, we can now compute the known and possible answers with Algorithm 1. We then compute the extended canonical ABox Aˆqf and the extended query qˆ for some suitable bijection f . Note that we do not have to consider the (often large) ABox A from K for computing qˆ. For each atom at 2 qˆ n q, we can then use our approximate instance retrieval algorithm to check whether at restricts q and reduce the set of possible answers P[q] accordingly.
Although K[ ] and P[ ] are often fast to compute (due to the use of simpler approximate reasoning algorithms or since the sets are simply extracted from a pre-model) and often cached, it is not very e cient to always retrieve all required such sets from the reasoner in order to perform the required joins. Hence, in our future work, we plan to just use the cardinalities of the sets K[ ] and P[ ]. The idea is to use the cardinalities of restricting atoms from qˆ to more precisely estimate the cardinalities of atoms in q. This will allow for a better ordering of the query atoms in cost-based query planning.
Since conjunctive instance queries are only a subset of the queries that are important in the context of SPARQL, we present, in this section, an optimisation that aims at improving the performance for evaluating arbitrary complex queries. In general for a complex query q = fat1; : : : ; atng, we partition q into two sets qs and qc such that qs is the maximal conjunctive instance sub-query of q and qc contains the axiom templates. We first evaluate qs, e.g., by employing optimisation techniques as described in the previous section. The intermediate results can then already be used to reduce the possible answers for qc. In order to optimise the evaluation of qc, we assume that the concepts and roles are classified (this is often done before a system accepts any queries), which means that axiom templates of the form x v A with x 2 VC, A 2 NC require only cache lookups. We use the hierarchies to prune the search space of solutions in the evaluation of certain axiom templates as illustrated with the following example: Example 6. Let q = fInfection v 9hasCausalLinkTo:xg with x 2 VC a concept variable and K some knowledge base. If, mapping x to the concept name A, does not yield an entailed axiom and K j= B v A holds, then B is also not a certain answer. Thus, when searching for certain answers, we choose the next binding to test by traversing the concept hierarchy top-down. When we find a non-answer A, the subtree rooted in A of the concept hierarchy can safely be pruned. Queries over ontologies with a large number of concepts and a deep concept hierarchy can, therefore, gain the maximum advantage from this optimisation. We employ similar optimisations using the role hierarchy.
In the example above, we can prune the subconcepts of A because x has positive polarity in the axiom, i.e., x occurs positively and not under a negation. In case a variable occurs negatively, e.g., directly or indirectly under a negation or positively on the lefthand side of an axiom, one can, instead, prune the superclasses. We next specify more precisely the polarity of a concept variable in a concept axiom template. Definition 6. Let x 2 VC be a concept variable and C; C1; C2; D concept axiom templates, r a role, and n 2 IN0. We define the polarity of x in D as follows: x occurs positively in x. Furthermore, x occurs positively (negatively) in – :C if x occurs negatively (positively) in C, – C1 u C2 or C1 t C2 if x occurs positively (negatively) in C1 or C2, – 9r:C, 8r:C, or > n r:C if x occurs positively (negatively) in C, – 6 n r:C if x occurs negatively (positively) in C – = n r:C if x occurs in C.
(positively) in C1 or positively (negatively) in C2. We further define a partial function polc that maps a concept variable x and a concept template C (axiom template of the form C1 v C2) to pos if x occurs only positively in C (C1 v C2) and to neg if x occurs only negatively in C (C1 v C2).
Note that x can also occur both positively and negatively. Note also that no matter whether x occurs positively or negatively in a concept C, in any concept of the form (= n r:C), x occurs positively as well as negatively. This is due to the fact that (= n r:C) is equivalent to the concept template 6 n r:C u > n r:C in which x occurs positively as well as negatively in C.
Since the function polc is not defined for variables that appear both positively and negatively, the concept hierarchy cannot be exploited in this case. For example, consider the concept axiom template :x t 9r:x with x 2 VC (i.e., x v 9r:x), where x appears negatively in :x and positively in 9r:x. Now, let 2 I be an arbitrary element from a model I = ( I; I) of the queried knowledge base. It is obvious that if is an instance of :A t 9r:A and either A v B or B v A holds, we cannot deduce that is an instance of :B t 9r:B.
The following theorem holds for every axiom template of the form C1 v C2. We use C (x)=A with A 2 NC to denote the concept obtained by applying the extension of that also maps x to A.
Theorem 2. Let K be a knowledge base, A; B concept names such that K j= A v B, C1; C2 concept templates, C = :C1 t C2, x 2 VC a concept variable occurring in C, and a mapping that covers all variables of C apart from x. 1. If polc(x; C) = pos and K 6j= (C1 v C2) (x)=B, then K 6j= (C1 v C2) (x)=A. 2. If polc(x; C) = neg and K 6j= (C1 v C2) (x)=A, then K 6j= (C1 v C2) (x)=B. We now extend this optimisation to the case of role variables and we first define the polarity of a role variable in a concept axiom template.
Definition 7. Let x 2 VR be a role variable, C; C1; C2; D concept templates, r a role, and n 2 IN0. We define the polarity of x in D as follows: x occurs positively in 9x:C, 9x :C, > n x:C, > n x :C, = n x:C, and = n x :C; x occurs negatively in 8x:C, 8x :C, 6 n x:C, 6 n x :C, = n x:C, and = n x :C. Furthermore, x occurs positively (negatively) in – :C if x occurs negatively (positively) in C, – C1 u C2 or C1 t C2 if x occurs positively (negatively) in C1 or C2, – 9r:C, 9x:C, 9x :C, > n r:C, > n x:C, > n x :C, 8r:C, 8x:C, or 8x :C if x occurs positively (negatively) in C, – 6 n r:C, 6 n x:C, or 6 n x :C if x occurs negatively (positively) in C, – = n r:C if x occurs in C.
(positively) in C1 or positively (negatively) in C2. We define a partial function polr that maps a role variable x and a concept template C (axiom template of the form C1 v C2) to pos if x occurs only positively in C (C1 v C2) and to neg if x occurs only negatively in C (C1 v C2).
We now show, that the hierarchy optimisation is also applicable to role variables, provided they occur only positively or only negatively.
Theorem 3. Let K be a knowledge base, r; s role names such that K j= r v s, C1; C2 concept templates, C = :C1 t C2, x 2 VR a role variable occurring in C, and a mapping that covers all variables of C apart from x.
Algorithm 2 getPossibleConceptVarMappings(x; ; at; K ) Require: x: a concept variable, : a partial mapping with x 2 dom( ) at: an axiom template in which x occurs, K : a SHIQ knowledge base Ensure: a set of possible answers for x if polc(x; at) == pos then
return f 0 j 0(x) =C; C is direct subconcept of (x) in K ; 0(y) = (y) for y 2 dom( )nfxgg else
return f 0 j 0(x) =C; C is direct superconcept of (x) in K ; 0(y) = (y) for y 2 dom( )nfxgg end if 1. If polr(x; C) = pos and K 6j= (C1 v C2) (x)=s, then K 6j= (C1 v C2) (x)=r. 2. If polr(x; C) = neg and K 6j= (C1 v C2) (x)=r, then K 6j= (C1 v C2) (x)=s.
Algorithm 2 shows how we use the above theorems to create possible concept mappings for a concept variable x that appears only positively or only negatively in an axiom template C1 v C2. We can define a similar algorithm for role variables. Hence, an algorithm for evaluating complex queries can call these algorithms to prune the search space once a solution for such a concept or role variable has been found, e.g., by checking entailment for an instantiated axiom template. 4.1
Complex Axiom Template Evaluation In the absence of suitable standard benchmarks for complex queries or SPARQL queries over OWL ontologies, we created a custom set of queries as shown in Tables 1 and 2 for the GALEN and the FBbt XP ontology, respectively. Systems that fully support the SPARQL Direct Semantics entailment regime are still under development, which makes it hard to compare our results for these kinds of queries with other systems. All experiments were performed on a Mac OS X Lion machine with a 2.53 GHz Intel Core i7 processor and Java 1.6 allowing 1GB of Java heap space. We measure the time for one-o tasks such as classification separately since such tasks are usually performed before the system accepts queries. The ontologies and all code required to perform the experiments are available online.6 For the evaluation we have used the HermiT7 hypertableau reasoner.
GALEN is a biomedical knowledge base. Its expressivity is (Horn-)SH IF and it consists of 2,748 concepts and 413 abstract roles. FBbt XP is an ontology taken from the Open Biological Ontologies (OBO) Foundry.8 Its expressivity is SH I and the knowledge base consists of 7,221 concepts and 21 roles. We only consider the TBox part of FBbt XP since the ABox is not relevant for showing the e ects of the optimisation for concept axiom templates. GALEN took 3.7 s to load and 11.1 s to classify (concepts and roles), while FBbt XP took 1.5 s to load and 7.4 s to classify.
For each query, we tested the execution once with (bold results) and once without the proposed optimisation. The tables also show the number of consistency checks that were performed for the evaluation of each query. 6 http://code.google.com/p/query-ordering/ 7 http://www.hermit-reasoner.com/ 8 http://www.obofoundry.org/
GALEN Queries: As expected, an increase in the number of variables within an axiom template leads to a significant increase in the query execution time because the number of mappings that have to be checked grows exponentially in the number of variables. This can, in particular, be observed from the di erence in execution time between the first two queries, where it is also evident that the use of the hierarchy exploitation optimisation leads to a decrease in execution time of up to two orders of magnitude. In the last query, the hierarchy exploitation optimisation does not improve the execution time since the variables on which the hierarchy optimisation can be applied, are already bound when it comes to the evaluation of the complex templates. Hence, the running times with and without the hierarchy exploitation are similar. The number of consistency checks for this query is significantly lower than the number of answers because the overall results are computed by taking the cartesian products of the results for the two connected components of the query. Although our optimisations can significantly improve the query execution time, the required time can still be quite high. In practice, it is, therefore, advisable to add as many restrictive axiom templates (axiom templates which require only cache lookups) for query variables as possible. For example, the addition of y v Shape to the forth query reduces the runtime from 1.12 s to 0.65 s.
FBbt XP Queries: We observe that in some queries the e ect of the hierarchy exploitation is more profound than in others. More precisely, the smaller the ratio of the result size to the number of consistency checks without the hierarchy optimisation, the more pronounced is the e ect when enabling this optimisation. In other words, when more tested mappings are indeed solutions, one can prune fewer parts of the hierarchy since pruning can only be performed when we find a non-solution. For the second query, we even observe a slight increase in running time when the hierarchy optimisation is used. This is because the optimisation can only prune few candidate mappings, which does not outweigh the overhead caused by maintaining information about which hierarchy parts have already been tested. For the last query, the number of consistency checks with the hierarchy optimisation is less than the result size (32; 490 versus 43; 338) since only the third axiom template of the query requires consistency checks, whereas bindings for y and x1 can be looked up from the cached concept and role hierarchy. 5
In the current paper we presented an approach for using the TBox of a knowledge base to optimise SPARQL queries evaluated using the OWL Direct Semantics entailment regime. For conjunctive instance queries we showed how we can build equivalent queries with additional atoms which can be exploited to reduce the set of possible mappings for query variables. Conditions were defined for this purpose which identify the cases in which such a reduction is achieved. For queries that go beyond conjunctive instance queries we provide a highly e ective and frequently applicable optimisation which prunes the number of candidate solutions that have to be checked by exploiting the concept and role hierarchy. One can, usually, assume that these hierarchies are computed before a system accepts queries. Our empirical evaluation shows that this optimisation can reduce the query evaluation times up to two orders of magnitude. Acknowledgements This work was supported by IKY in collaboration with DAAD in the program IKYDA: Automatic data generation for description logic knowledge bases.
Proof (Proof of Lemma 1). We prove the lemma by induction on the length of the query q given as input to the algorithm intersecQans(K ; q). For q = fatg the two conditions of the definition of approximate query answering algorithms are satisfied. Indeed,
(at) (since inst(K ; at) is an approximate instance retrieval algorithm), which means that K j= (q). 2. for each total function from Var(q) to individual names from K such that 2 ans(K ; q), i.e., 2 ans(K ; at), i.e., K j = (at), it holds 2 K[at] [ P[at] (since inst(K ; at) is an approximate instance retrieval algorithm), i.e., 2 K[q] [ P[q]. algorithm by showing that the two conditions of Definition 3 hold for q0. Let q0 = q [ fatg and let us assume that intersecQans(K ; q) is an approximate query answering algorithm. We prove that inst(K ; q0) is also an approximate query answering 1. If
2 K[q0], this means that jVar(q) 2 K[q] and jVar(at) 2 K[at] (it can easily be seen from the construction K[q0] in intersecQans(K ; q0)). By induction hypothesis jVar(q) 2 ans(K ; q) and, since inst(K ; at) is an approximate instance retrieval algorithm, K j= jVar(at)(at). Since = jVar(q) ./ jVar(at), it holds 2 ans(K ; q0). 2. For each total function from Var(q) to individual names from K such that 2 ans(K ; q0), it holds jVar(q) 2 ans(K ; q) and K j= jVar(at)(at). By the induction hypothesis, jVar(q) 2 K[q] [ P[q] and jVar(at) 2 K[at] [ P[at]. It holds = jVar(q) ./ jVar(at). We distinguish between the following cases: – if jVar(q) 2 K[q] and jVar(at) 2 K[at], then 2 K[q0] – if jVar(q) 2 K[q] and jVar(at) 2 P[at], then – if jVar(q) 2 P[q] and jVar(at) 2 K[at], then – if jVar(q) 2 P[q] and jVar(at) 2 P[at], then We see from the above that in any case 2 P[q0] 2 P[q0] 2 P[q0] 2 K[q0] [ P[q0].
tu inst(K ; at), and at restricts P[q].
Lemma (2). Let K = hT ; Ai be a knowledge base, q and q0 two queries such that q0 = q [ fatg, ans(K ; q) = ans(K ; q0), hK[q]; P[q]i = intersecQans(K ; q), hK[at]; P[at]i = and q as input is an approximate query answering algorithm and
Proof (Proof of Lemma 2). For the first claim, according to Lemma 1, intersecQans(K ; q) is an approximate query answering algorithm. Hence, the first condition on approximate query answering algorithms is satisfied. For the second condition and in contrary to what is to be shown, assume there is some such that < K[q] [ f 2 P[q] j jVar(at) 2 (K[at] [ P[at])g, i.e., jVar(at) < K[at] [ P[at]. By Definition 4 and since at restricts P[q], we have Var(at) Var(q) and all variables from at are in the domain of . Since inst(K ; at) is an approximate instance retrieval algorithm, 2 ans(K ; q), but Then, T j= q
qˆ, i.e., for any ABox A0, ans(hT ; A0i; q) = ans(hT ; A0i; qˆ).
We want to prove that for any ABox A, ans(hT ; Ai; q) = ans(hT ; Ai; qˆ), i.e., ans(hT ; Ai; q) ans(hT ; Ai; qˆ) and ans(hT ; Ai; qˆ) ans(hT ; Ai; q). From Definition 5 it is easily seen that Var(q) = Var(qˆ) and since q has more atoms (is more restricting) than q, it holds ans(hT ; Ai; qˆ) ans(hT ; Ai; q). We will now show that ans(hT ; Ai; q) i.e., hT ; Ai j= 2 ans(hT ; Ai; qˆ).
ans(hT ; Ai; qˆ). Let be a mapping such that 2 ans(hT ; Ai; q), Var(q) to a set of individual names from NI , hT ; Aqf i j= Aˆqf . Hence, hT ; Aqi j= Aˆq (q). From Definition 5 it is obvious that for any total function f from or hT ; (q)i j= (qˆ) which means hT ; A [ (q)i j= erty of description logics, which means that hT ; Ai j= (qˆ) (since hT ; Ai j= (q)), i.e., (qˆ) due to the monotonicity propthis means K 6j
= ans(K ; q) = ans(K ; q0).
jVar(at)(at), but this means that < ans(K ; q0), which contradicts subset of fP[q]g by Definition 4 and since at restricts q.
The second claim follows since f 2 P[q] j jVar(at) 2 (K[at] [ P[at])g is a strict Proof (Proof of Lemma 3). It is obvious that the extended query qˆ does not depend on the function f that is used for its construction since the canonical ABoxes and consequently the extended canonical ABoxes produced w.r.t. di erent functions f are isomorphic to each other, i.e., identical modulo renaming of individuals. and
a mapping that covers all variables of C apart from x.
Theorem (2). Let K be a knowledge base, A; B concept names such that K j= A v B, C1; C2 concept templates, C = :C1 t C2, x 2 VC a concept variable occurring in C, 1. If polc(x; C) = pos and K 6j= (C1 v C2) (x)=B, then K 6j= (C1 v C2) (x)=A. 2. If polc(x; C) = neg and K 6j= (C1 v C2) (x)=A, then K 6j= (C1 v C2) (x)=B. Proof (Proof Sketch of Theorem 2). The claim can be shown by induction on the structure of the concept template C. We only consider the case of polc(x; C) = pos; the case of polc(x; C) = neg is analogous. It su model I = ( I; I) of K and some element ces to show (in contrapositive form) for some 2
I, if 2 (C (x)=A)I, then 2 (C (x)=B)I.
For the base case, C = x, x occurs positively in C. Now, if 2 AI and, hence, 2 BI since K j= A v B by assumption. Hence, 2 (x (x)=A)I, then 2 (x (x)=B)I.
We show the induction step for C = 9r:D. The other cases are analogous. We assume has at least one r-successor, say 0, that is an instance of 2 ((9r:D) (x)=A)I, then D (x)=A. Since K j
= A v B and by induction hypothesis, 0 2 D (x)=B. Hence, the polarity of x in C is always positive and negative and polc(x; C) is undefined. (9r:(D (x)=B))I = ((9r:D) (x)=B)I. Note that the case C = (= n r:D) cannot occur since 2 tu tu tu tu mapping that covers all variables of C apart from x. concept templates, C = :C1 t C2, x 2 VR a role variable occurring in C, and Proof (Proof Sketch of Theorem 3). The claim can be shown by induction on the structure of the concept template C. We only consider the case of polr(x; C) = pos; the case
We have several base cases here, but only present the case for concept templates of of polr(x; C) = neg is analogous. It su model I = ( I; I) of K and some element 2 ces to show (in contrapositive form) for some
C = 6 n x:D with x not occurring in D are similar. Assume, the form C = 9x:D with x not occurring in D. The cases for C = 8x:D, C = > n x:D, 2 (9r: (D))I. Then there is some 0 2
I such that h ; 0i 2 rI and 0 2 (D)I. Since K j= r v s, we also have h ; 0i 2 sI and, therefore, 2 (9s: (D))I = ((9x:D) (x)=s)I.
For the induction step, let C = 9x:D with x occurring in D, we also have polr(x; D) = pos. Now, if
2 ((9x:D) (x)=r)I, then that is an instance of D (x)=s. Hence, of D (x)=r. Since K j= r v s and by induction hypothesis, has at least one r-successor which is an instance 2 ((9x:D) (x)=s)I. The case of C = 9p:D with p has at least one s-successor a role and x occurring in D is analogous and so are the further induction steps.