The paper presents an approach for optimizing query answering algorithms that are based on approximate instance retrieval. We consider SPARQL instance queries over OWL ontologies and use the OWL 2 Direct Semantics entailment regime of SPARQL for their evaluation. Approximate query answering algorithms are based on the creation of two sets; the set of certain or known query answers and the set of possible query answers, which require checks to determine whether they are real answers. Typically, it is expensive to check the possible answers hence our goal in this paper is to reduce the number of possible answers returned by approximate reasoning algorithms. We present an approach for using schema knowledge from the terminology (TBox) to optimize the evaluation of SPARQL instance queries. We proceed by transforming the query into a set of assertions (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.
Query answering—the computation of answers to users’ queries w.r.t. ontologies and
data—is an important task in the context of the Semantic Web that is provided by many
OWL reasoners. Although much e ort has been spent on optimizing the ‘reasoning’
part of query answering, i.e., the extraction of the individuals that are instances of a
class or property, less attention has been given to optimizing the actual query answering
part when ontologies in expressive languages are used. The SPARQL query language
[
Evaluating queries over OWL 2 DL ontologies using approximate query answering algorithms usually involves performing expensive consistency checks for deciding whether possible answers are real. For example, the description logic SROIQ, which underpins the OWL 2 DL standard has a worst case complexity of 2-NExpTime. In this paper we focus on optimizing such query answering algorithms that are based on approximate instance retrieval. We first define what an approximate query answering algorithm is and give a simple query answering algorithm that is directly based on approximate instance retrieval. We afterwards present an e cient algorithm that is based on a technique called query extension. According to query extension, for a given query q, we compute an equivalent query qˆ that can be evaluated more e ciently. We first replace the variables in q with fresh individual names and we afterwards perform realization, i.e., we materialize entailed class and property 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. We provide a prototypical implementation and evaluation of the proposed optimization, which shows that it can lead to an improvement of up to two orders of magnitude in the query execution times.
The results in this paper have partly been published at the International Description
Logic Workshop 2013 [
In this section we give a brief introduction to the SPARQL instance queries, which we
use throughout the paper. Instead of OWL syntax, for brevity, we use the description
logic (DL) [
The WHERE clause of a SPARQL query consists of graph patterns. Basic graph
patterns (BGPs) can be composed to more complex patterns using operators such as
UNION and OPTIONAL for alternative and optional selection criteria. The evaluation
of (complex) graph patterns is done by evaluating each BGP separately and
combining the results of the evaluation. We only consider the evaluation of BGPs since this
is the only thing that is specific to a SPARQL entailment regime. We further focus on
SPARQL instance queries, i.e., BGPs that retrieve tuples of individuals, which are
instances of the queried class expressions and properties. Such BGPs are first mapped
to OWL class and (object) property assertions that allow for variables in place of
individuals. For further details, we refer interested readers to the W3C specification that
defines the mapping between OWL structural objects and RDF graphs [
Definition 1 (Query). A query signature S is a four-tuple (NC; NR; NI ; V), where the tuple (NC; NR; NI ) is a signature and V is a countable, infinite set of (individual) variables disjoint from NC, NR, and NI . A term is an element from NI [ V. Let C be an OWL 2 DL class expression, t, t0 terms. An atom is an expression of the form C(t) (class atom) or r(t; t0) (property atom). A query q is a formula ~x at1; : : : ; atn, where at1; : : : ; atn are atoms and ~x is the tuple of variables contained in at1; : : : ; atn. We use Var(q) (Var(at) for a query atom at) to denote the set of variables in q (at), respectively. We write jqj to denote the number of axiom templates in q.
replacing each variable x in at (q) with (x). A query mapping is a certain answer for q over an ontology O, written O; j= q, if O j= (at) for each atom at in q. We denote the set of all certain answers for q over O with ans(O; q).
Let X = fx1; : : : ; xng be a set of variables and M a set of query mappings. The projection of X over M is the set MjX = ffx1 7! (x1); : : : ; xn 7! (xn)g j 2 Mg.
For a query q = ~x at1; : : : ; atn, we often write q just as a set of atoms fat1; : : : ; atng, when the order of atoms and the order of the variables in ~x is not important. In the following we use A for a class, C for a class expression, r for an object property, a, b for individuals and x; y for variables. 3
Query Answering via Approximate Instance Retrieval
In this section, we present a technique that uses approximate query answering
algorithms in order to optimize the evaluation of queries. Approximate query answering
algorithms can either be sound and incomplete, i.e., they under-approximate the set
of certain or known answers or they can be complete but unsound, i.e., they
overapproximate the set of certain answers. Typical examples of such algorithms rewrite
a knowledge base into a simpler logic in such a way that computing the results over
the simplified knowledge base yields the desired under- or over-approximation [
2 K[q], 2 ans(O; q), and 2 ans(O; q), 2 K[q] [ P[q].
trieval algorithm if the input query can only consist of a single query atom. For brevity, we write inst(O; at) for the call of such an algorithm.
Without loss of generality, in the rest of the paper we assume that K[ ] \ P[ ] = ; holds for every approximate query answering algorithm.
For ease of presentation, we often write K[C] = fa1; : : : ; ang instead of K[C(x)] = ffx 7! a1g; : : : ; fx 7! angg and similarly for property atoms, queries, and possible answers.
While it is well-known [
Example 1. Let O be an ontology and q the query hx; yi C(x); r(x; y); D(y). Suppose that (possibly as a result of inst(O; C(x)), inst(O; r(x; y)) and inst(O; D(y))) we have K[C] = fag P[C] = fbg
K[r] = fha; cig P[r] = fhb; di; hb; eig
K[D] = fcg P[D] = fdg Even if we do not know O, we can conclude that ha; ci is a certain answer to q, since a 2 K[C], ha; ci 2 K[r] and c 2 K[D]. However, only hb; di is a possible answer for q since b 2 P[C], hb; di 2 P[r] and d 2 P[D]; hb; ei cannot be an answer for q since although hb; ei 2 P[r] and b 2 P[C], e < K[D] [ P[D].
Algorithm intersecQans (see Algorithm 1) formalizes this idea, which we also illustrate in the next example.
Example 2. Let q be as in Example 1. After possibly bringing the query atoms into a beneficial execution order and initializing K[C] and P[C], the sets K[q] and P[q] are initialized to contain partial mappings that only become query mappings once the algorithm is finished. During the following iterations, the mappings in K[q] are 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 the example query, 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.
Proof (sketch). The lemma can straightforwardly be shown by induction on the length of the input query.
The method order in intersecQans is optional and can use query ordering techniques from databases to order the query atoms based on the cardinalities of the sets K[at] and P[at], e.g., one would prefer joins over connected atoms and join a small relation (an atom at with smaller K[at] and P[at] sets) with a bigger one where possible. Algorithm 2 shows how we can evaluate SPARQL instance queries using intersecQans. 4
The question now is: given an ontology O and a query q, how we can find a more e cient way to further reduce the cardinality of P[q] with the aid of inst. Algorithm 1 intersecQans(O; q) Require: O = hT ; Ai: an OWL 2 DL ontology
q: a query over O Ensure: hK[q]; P[q]i: K[q]; P[q] sets of known and possible answers for q over O 1: at1; : : : ; atn := order(q; O) 2: for i = 1; : : : ; n do 3: hK[ati]; P[ati]i := inst(O; ati) 4: if K[q] and P[q] not initialized then 5: hK[q]; P[q]i := hK[ati]; P[ati]i 6: else 7: K[q] := K[q] ./ K[ati] 8: P[q] := (P[q] ./ P[ati]) [ (K[q] ./ P[ati]) [ (P[q] ./ K[ati]) 9: end if 10: end for 11: return hK[q]; P[q]i Algorithm 2 evaluateIntersecQans(O; q) Require: O = hT ; Ai: an OWL 2 DL ontology
q: a query over O Ensure: the certain answers for q over O 1: hK[q]; P[q]i := intersecQans(O; q) 2: return f j 2 K[q]g [ f j 2 P[q]; (O; ) j= qg Example 3. Let O = hT ; Ai be an ontology with O j= 9r:>uC v B, q = fC(x); 9r:D(x)g a query, inst(O; C(x)) = hfbg; fagi and inst(O; B(x)) = hfag; ;i and inst(O; 9r:D(x)) = h;; fa; bgi. From Algorithm 1 we have K[q] = ; and P[q] = fa; bg. In this case, b is no longer a possible answer of q. If b would be a possible mapping for x, it would have an r-successor (since 9r:D(x) 2 q) and it would be an instance of C (since C(x) 2 q) and, hence, b should be in K[B] [ P[B] to satisfy the entailed axiom, which is not the case.
The atom B(x) in the above example is called a restricting atom. We now give a definition of restricting atoms that will help us define an e cient algorithm.
with Var(at) Var(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(O; q) and hK[at]; P[at]i = inst(O; at). Example 4. Going back to Example 3, we find that B(x) is indeed a restricting atom for q according to Definition 3 since we have P[q]jfxg = fa; bg and P[q]jfxg \ (K[B] [ P[B]) = fag, which clearly is a subset of P[q]jfxg.
If we want to preserve the certain answers of q, we should use restricting atoms that do not change the answers of q. Let q and q0 be 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 O = hT ; Ai be an ontology, q and q0 two queries such that q0 = q [ fatg, ans(O; q) = ans(O; q0), hK[q]; P[q]i = intersecQans(O; q), hK[at]; P[at]i = inst(O; at), and at restricts P[q].
and q as input is an approximate query answering algorithm and 2. jf 2 P[q] j jVar(at) 2 (K[at] [ P[at])gj < jP[q]j.
Proof (Sketch). 1. According to Lemma 1, intersecQans(O; q) is an approximate query answering algorithm. Hence, the first condition on approximate query answering algorithms is satisfied. That also the second condition is satisfied can be shown by assuming, to the contrary of what is to be shown, that there is a certain answer 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]. Using the definition of restricting atoms, we can then show a contradiction.
2. Since f 2 P[q] j jVar(at) 2 (K[at] [ P[at])g is a strict subset of fP[q]g by Definition 3 and since at restricts q the claim follows.
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. We first create a small ABox, called query ABox, from the query atoms by mapping their variables to fresh individuals that do not appear in the query or the TBox to avoid interactions. We then materialize this ABox w.r.t. implicit class and property assertions for the individuals that appear in it and the (possible) additional individuals (nominals) added by the TBox creating the extended query ABox. Afterwards, we can go to the extended query by replacing individuals back with variables of the initial query.
The proposed query extension method is similar to the method for deciding
containment between conjunctive queries [
Let Z be a set of axioms or query atoms. In the definition below with NCZ, NRZ and NIZ we denote the set of classes, properties and individuals respectively appearing in Z.
the corresponding query signature Sq, and f a total function from Var(q) to a set of individual names from NI. The query ABox Aqf for q w.r.t. f is defined as follows:
Aqf = f f (at) j at 2 qg The extended query ABox Aˆqf;T for q w.r.t. f and T is defined as:
Aq ˆ f;T = Aqf [ fB(a) j B 2 NCT [Aqf ; a 2 NI T [Aqf and T [ Aqf j= B(a)g
[ fr(a; b) j r 2 NRT [Aqf ; a; b 2 NI T [Aqf and T [ Aqf j= r(a; b)g define the extended query qˆ w.r.t. f and Aˆqf;T as follows: If T [ Aqf is consistent, f is additionally bijective and range( f ) = NI n NI T [q, we can qˆ = f f (at) j at 2 Aq g ˆ f;T same answers as q (w.r.t. any ABox), because O j= 9r:> u C v B.
Example 5. Suppose we have an ontology O = hT ; Ai such that T contains one axiom, if.oer.,q9irs:>AuqfC=vfCB(aanx)d; 9qr=:Df(Ca(x)xg);w9hre:Dre(xf)gmfraopmstEhexavmarpilaeb3le. Ixnttohitshecaisned,ivthideuqaulenryamAeBaoxx. The extended query ABox for q w.r.t. f and T is Aˆqf;T = fC(ax); 9r:D(ax); B(ax)g and the extended query w.r.t Aˆqf;T is qˆ = fC(x); 9r:D(x); B(x)g. Please note that qˆ has the A = fr(a; c); C(c)g.
Note that we want q and qˆ to have the same answers w.r.t. any ABox. For this reason we restrict f to map variables to individuals not appearing in q or T (nominals). If T has nominals and we map a query variable to a nominal in T then Aˆqf may contain consequences that come from the interaction of query mappings and TBox nominals. For example, let T = f9r:fbg v Ag and q = fr(x; y); C(y)g. If we choose f = f a; y 7! bg then Aˆqf = fr(a; b); C(b); A(a)g and qˆ = fr(x; y); C(y); A(x)g. The mapping x 7! fx 7! a; y 7! cg is an answer of q, whereas it is not an answer of qˆ w.r.t. the ABox
Proof (Sketch). The lemma follows since the extended query ABoxes produced w.r.t. di erent functions f are isomorphic to each other, i.e., identical modulo renaming of individuals.
Intuitively (see Example 5), the extended query qˆ adds atoms to q that do not change the set of answers of q, which we formalize by Theorem 1.
Then, T j= q
qˆ, i.e., for any ABox A, ans(hT ; Ai; q) = ans(hT ; Ai; qˆ).
hT ; (q)i j= hT ; Ai j=
(qˆ), which means hT ; A [ (q)i j= (qˆ) since hT ; Ai j= (q), i.e.,
2 ans(hT ; Ai; qˆ).
Proof. From Definition 4 it is easily seen that Var(q) = Var(qˆ) and q qˆ. Hence, ans(hT ; Ai; qˆ) function f from Definition 4 is such that hT ; Aqf i j= Aˆqf . Hence, hT ; Aqi j= Aˆq, i.e., ans(hT ; Ai; q). For the other direction, let 2 ans(hT ; Ai; q). Any (qˆ) due to monotonicity. But then tu Since extending the query with all atoms from Definition 4 and evaluating the extended query is not e cient and may result in the checking of many not entailed mappings, we afterwards describe an optimized algorithm that uses only specific extension atoms to reduce the query answering time. A naive algorithm that uses the extension atoms could be as follows: Given a query q and an ontology O = hT ; Ai, we compute the extended query ABox Aˆqf;T and the extended query qˆ for some suitable bijection f . Note that we do not have to consider the (often large) ABox A from O for computing qˆ. For each atom at 2 qˆ n q we check whether at restricts q according to Definition 3 and create a new query q0 that consists of q and the restricting atoms from qˆ n q. We afterwards evaluate q0.
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 for determining the restricting atoms. Hence, in Algorithm 3 an alternative definition for restricting atoms that just uses the cardinalities of the sets K[ ] and P[ ] is used. The idea is to use the cardinalities of restricting atoms from qˆ to more precisely estimate the cardinalities of atoms in q. This allows for a better ordering of query atoms in cost-based query planning. Moreover, since it is expensive to evaluate restricting atoms if they do not contribute relevant mappings, in Algorithm 3 we show how we can use the query extension technique for query optimization while checking only relevant mappings.
Algorithm 3 (evaluateExtensionQans) takes as input a query q and an ontology O and produces a set of certain answers for q over O. The goal for e ciency is to reduce the sets K[ ] and P[ ] of query atoms from q based on atoms on the extension of q (qˆ) created as in Definition 4. Note that we use the methods instK(O; at) and instP(O; at) to retrieve the sets K[at] and P[at] of at and the methods instjKj(O; at) and instjPj(O; at) to retrieve the cardinalities of the sets K[at] and P[at] of at, respectively. In particular, we first take the extended query qˆ according to Definition 4 (line 4) and for each atom atq of q that can be restricted, we check which of the extension atoms (i.e., atoms in qˆ n q) are restricting for atq and we keep in RA[atq] the restricting atom that leads to the smallest P[atq] set for atq (lines 5-16). The method canbeRestricted takes as input an atom atq of the initial query and returns true if atq is of the form C(x), r(x; a) or r(a; x), otherwise it returns false. An atom atr is considered a restricting atom if it shares variables with atq and additionally it reduces the P[ ] set of atq, i.e., the cardinality of the K[ ] and P[ ] sets of atr is smaller than the cardinality of the P[ ] set of atq (line 11).
After defining restricting atoms for every atom atq 2 q we move to the evaluation of the query. We first order the atoms in q based on the sets of known and the reduced sets of possible mappings for query atoms, which are created using information about the restricting atoms from the structure RA (line 17). Note that in contrast to Algorithm 1, the method order in Algorithm 3 additionally takes RA into account. We initialize the set of certain answers Rans with the identity mapping 0 which does not map any variable to any value (line 18). For each atom atq of q and mapping 2 Rans we proceed as described below (lines 19-33 of Algorithm 3): If atq instantiated by has all its variables bound we check if the appropriate projection of the mapping belongs to the K[ ] set of the atom or if it belongs to the P[ ] set of the restricting atom and the mapping leads to an entailed axiom (lines 23-26). If atq contains unbound variables we extend with mappings for the unbound variables based on the K[ ] set of the atom and the P[ ] set of the restricting atom that lead to entailed axioms (lines 27-30). Note that we check if the mapping belongs to the possible set of the restricting atom but we check entailment using atq of q since we are interested in the evaluation of the atoms of q. Also note that the mappings 0 do not assign values to any of the variables covered by the already computed (partial) solution . This allows for defining the union of and 0 by setting ( [ 0)(v) = (v) if v 2 dom( ), and ( [ 0)(v) = 0(v) otherwise. 5
Although the proposed optimized algorithm can be used, in general, for improving the
performance of most approximate query answering algorithms, here the evaluation is
based on the system described in [
We tested the developed optimizations with the University Ontology Benchmark
(UOBM) [
In order to show the e ect that query extension (Algorithm 3) has, we have created
the following queries, which contain atoms with possible instances:
q1 = fisAdvisedBy(x; y); GraduateStudent(x); Woman(y)g
q2 = fisTaughtBy(x; y); GraduateCourse(x); Woman(y)g
q3 = fteachingAssistantOf(x; y); GraduateCourse(y); Woman(x)g
q4 = f9takesCourse:>(x); 8takesCourse:GraduateCourse(x)g
q5 = fWoman(x); 9worksFor:Organization(x)g
In the above queries, the sets P[GraduateStudent], P[Woman] and P[GraduateCourse]
are non-empty, i.e., the query classes have possible instances. In Table 1 we compare
the number of possible instances that are being checked (i.e., the number of performed
consistency checks), denoted by EntNo in the table, and the running time of three
different algorithms w.r.t. the above queries, i.e., i) Algorithm evaluateExtensionQans,
ii) the algorithm from our previous work when static ordering is used [
From Table 1 we see that Algorithm evaluateExtensionQans considerably reduces the number of performed consistency checks in comparison to Static and hence the query answering times for all queries. As explained in the previous section this is achieved by exploiting the known and possible instances of atoms belonging to the extension of the query. For example, in Query q1 Algorithm Static results in the ordering [isAdvisedBy(x,y), GraduateStudent(x), Woman(y)], while the use of the extension atom Professor(y) significantly reduces the query specific instances of Woman(y) and hence the ordering [isAdvisedBy(x; y); Woman(y); GraduateStudent(x)] is chosen based on the reduced instance sets, which leads to better performance results. Similarly, for Queries q2 and q3 the use of the extension atoms Facutly(y) and TeachingAssistant(x) significantly reduces the mappings for the atoms Woman(y) and Woman(x) respectively. In the same way for Queries q4 and q5, which contain atoms with (complex) class expressions, the use of the extension atoms GraduateStudent(x) and Employee(x) significantly reduces the number of mappings for x that need to be checked. Note that the query extension phase takes around 0.3 seconds for all the above queries. Algorithm evaluateIntersecQans also performs better than Static because only the possible mappings that belong to the known or possible sets of all query atoms are checked.
Regarding the comparison between the algorithms evaluateExtensionQans and evaluateIntersecQans we see that evaluateExtensionQans performs much better than evaluateIntersecQans for queries containing atoms with (complex) class expressions and it performs similarly for queries without atoms with (complex) class expressions. It is worth noting that on Query q5 Static performs worse than evaluateIntersecQans even though Static performs less consistency checks than evaluateIntersecQans. This happens because the two algorithms choose a di erent ordering and, in particular, Static evaluates the atom 9worksFor:Organization(x) first, which requires more expensive consistency checks than the complexity of the consistency checks performed for the atom Woman(x) and the afterwards evaluation of 9worksFor:Organization(x) based on the reduced x-mappings.
In the current paper we presented an approach for using the TBox of an ontology to optimize the evaluation of SPARQL instance queries evaluated under the OWL Direct Semantics entailment regime. For those 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. Through our experimental evaluation we showed that the use of these extension atoms can lead to a significant reduction in query answering time, which can be 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.