Recently, SPARQL-DL was introduced in [7] as a rich query language for OWL-DL ontologies. It provides an OWL-DL-like semantics for SPARQL basic graph patterns which involves as special cases both conjunctive ABox queries and mixed TBox/RBox/ABox queries over Description Logic (DL) ontologies. This paper describes the implementation of a SPARQL-DL query engine and discusses several optimizations. We investigate the new challenges brought by the additional expressivity of SPARQL-DL by extending a well-known benchmark.
In this section we provide a brief description of SPARQL-DL and refer the reader
to [
Type(a; C ) j PropertyValue(a; p; d ) j SameAs(a1 ; a2 ) j Di erentFrom(a1 ; a2 )
j SubClassOf(C1 ; C2 ) j EquivalentClass(C1 ; C2 ) j DisjointWith(C1 ; C2 )
j ComplementOf(C1 ; C2 ) j SubPropertyOf(p1 ; p2 ) j EquivalentProperty(p1 ; p2 )
j InverseOf(p1 ; p2 ) j ObjectProperty(p) j DataProperty(p) j Annotation(b1 ; r ; b2 )
j Functional(p) j InverseFunctional(p) j Symmetric(p) j Transitive(p)
where a(i) 2 Vuri [ Vvar [ Vbnode, d 2 Vuri [ Vvar [ Vbnode [ Vlit, C(i) 2 Vvar [ Sc,
p(i) 2 Vuri [ Vvar, bi 2 Vuri and r 2 Vuri. The set Sc denotes the set of all
OWL-DL concepts (both atomic and complex) built upon VO (see [
A SPARQL-DL query Q is a set fqigi=1, also denoted as q1; : : : ; qn, interpreted as their conjunction. Each SPARQL-DL query allows for bnodes only in individual/literal position while allowing for distinguished variables at all other positions. In Section 4.1, we will show how we can get rid of bnodes mentioned in SameAs atoms, but in our implementation we assume that no bnodes appear in Di erentFrom atoms.
Having O and Q as above, we de ne SPARQL-DL semantics as follows. A solution to query Q is a mapping : Vvar ! Vcls [ Vop [ Vdp [ Vlit, such that, when applied to all variables in Q we get a semiground query (Q) (i.e. query containing no variables, but possibly containing bnodes), for which O j= (Q). To decide whether O j= (Q) we need to ensure that for each model I = ( I ; I ) of O there exists an evaluation function : Vind [ Vbnode [ Vlit ! I , that coincides with I on literals and individuals, but provides a mapping for a bnode to a domain element, that satis es (I j= (qi)) each semiground atom (qi) 2 Q, see Table 1). The mapping ensures that bnodes behave like proper undistinguished variables, i.e. variables that can be bound not only to asserted individuals but also to inferred ones. 3
In this section, we provide some example queries that show how data and schema
queries can be combined in SPARQL-DL. Our examples are based on the widely
used LUBM dataset [
The LUBM dataset describes the university domain with information about departments, courses, students, and faculty. This dataset comes with 16 pure ABox queries with di erent characteristics (low vs. high selectivity, small vs. large input, etc.). In a similar fashion, we constructed 10 SPARQL-DL queries (all queries are available online4). Our primary goal was to exercise the novel 4 http://svn.versiondude.net/clark-parsia/datasets/lubm/query-owled features of SPARQL-DL and identify the new challenges introduced by the additional expressivity SPARQL-DL provides over traditional ABox queries. The following examples demonstrate some of the features we used in these queries. Example 1 (Variables in property position). Find all the graduate students that are related to a course and nd what kind of relationship (e.g. takesCourse, teachingAssistantOf) it is:
Type(?x ; GraduateStudent); PropertyValue(?x ; ?y; ?z ); Type(?z ; Course) Example 2 (Mixed ABox/TBox query). Find all the students who are also employees and nd what kind of employee (e.g. ResearchAssistant) they are:
Type(?x ; Student); Type(?x ; ?C ); SubClassOf(?C ; Employee) Asked against the LUBM dataset this query returns students who work as ResearchAssistants.
Example 3 (Mixed ABox/RBox query). Find all the members of Dept0 and what kind of membership (e.g. worksFor, headOf) it is: Type(?x ; Person); PropertyValue(?x ; ?y; Dept0); SubPropertyOf(?y; memberOf) 4 4.1
It is possible to simplify a query by removing redundant atoms, i.e. atoms that
are necessarily satis ed due to other atoms in the query. One such simpli
cation is the domain/range simpli cation introduced in [
Algorithm 1 Preprocessing of SameAs atoms with bnodes
The procedure rst removes all trivially satis ed SameAs atoms from the query, skipping those with variables without any other occurence in the query. Next, whenever a query Q in the set S contains a SameAs atoms with bnodes, all occurences of the bnode (or any of the bnodes) are replaced with the other term. For example SameAs(b; ?x ); Type(b; Person) is transformed to Type(?x ; Person). However, this preprocessing cannot be used for SameAs atoms without bnodes, since O might contain individuals explicitly stated to be owl : sameAs in O. For example, in SameAs(?x ; ?y) it is necessary to bind to ?x and ?y to all combinations of individuals in the equivalence set induce by the owl : sameAs relation in O. Correctness follows from the semantics of the SameAs atom (see Table 1) and the following idea: Since it is necessary to construct one evaluation for each interpretation I, we can always choose (b) = ( (a)), if a is a variable, and (b) = (a) otherwise.
The syntactic overhead of SPARQL-DL makes other simpli cations possible. We can remove trivially satis ed atoms: (i) re exive atoms with the same argument from the query that trivially hold, for example SubClassOf(C; C), or SubClassOf(?x ; ?x ) whenever ?x is used at some other atom in the query; (ii) atoms with owl:Thing or owl:Nothing in a particular way, for example as in SubClassOf( ; owl : Thing). On the other hand we can immediately fail queries for irre exive atoms (e.g. DisjointWith; Di erentFrom) with the same argument. These preprocessing steps are not exhaustive but they are all quite cheap and since they decrease the number of atoms in the query, they are valuable especially w.r.t. the cost based reordering presented in Section 5.1.
The next preprocessing step is to split the query into connected components in order to avoid computing cross-products of their results. From now on, w.l.o.g. we will assume that a SPARQL-DL query consists of just one connected component. 1. Qc that contains all Type and PropertyValue atoms from Q, and 2. Qs that contains all other atoms from Q.
Intuitively, Qc represents an ABox (data) query whereas Qs represents the TBox/RBox (schema) query. However, note that, Qc is not a proper ABox query in the traditional sense since there might be variables in class or property positions. Furthermore, there might not be atoms in Qs that mentions such variables. For this reason, we augment Qs with atoms of the form SubClassOf(?x ; ?x ) (resp. SubPropertyOf(?x ; ?x )) for each ?x that occurs in Type( ; ?x ) 2 Qc (resp. PropertyValue( ; ?x ; ) 2 Qc) but does not occur in Qs. Note that, these additional atoms have no e ect to the query results but they ensure that Qs will contain all class and property variables mentioned in the query.
Algorithm 2 is used to answer Qs that consists of just one connected
component (if there are more connected components we can evaluate each of them
separately as in Section 4.1). The algorithm proceeds as follows: First, given an
ordering W of query atoms, an atom q is chosen (next(O; W; B)) for evaluation.
Second, in q we replace variables bound in B with corresponding values.
Resulting query atom q is then evaluated using function evalAtom(O; q; Wr; B; R).
This function (i) checks whether O j= q, if q is ground, (ii) explores possible
bindings for all variables of q in other cases, using the following interface to the
OWL-DL reasoner 5:
allC(O), allP(O), allI(O) return all named classes, resp. properties, resp.
individuals de ned in O.
en(O; q) checks whether O j= q, for a ground SPARQL-DL atom q. As
SPARQLDL atoms correspond to OWL-DL constructs/axioms their reduction to the
basic inference services is straightforward from [
All atoms from Qs are evaluated using the above reasoner interface. As an
example, let's consider a call evalAtom(O; DisjointWith(?x ; ?y ); Wr; ; R). For
each possible binding C 2 allC(O) for ?x we try to get disjoint classes D of
C using subC(O; :C). For each such binding we call eval(O; Wr; B [ f?x 7!
C; ?y 7! Dg; R) to check the rest of the query (See the technical report [
Evaluation of Qs generates a collection R of result bindings. Each B 2 R
is then applied to Qc, possibly binding some class/property variables,
resulting in query Qc . This query is then evaluated using the underlying
conjunctive ABox query engine. One way to avoid unnecessary evaluation of Qs is to
evaluate it as soon as all of its variables get bound in B. Let's take an
example, Type(?z ; ?x ); SubClassOf(?x ; Person); EquivalentClasses(?x ; ?y ). This query
is split into Qc = Type(?z ; ?x ) and Qs = SubClassOf(?x ; Person); EC(?x ; ?y ).
Whenever a binding C for ?x is found during evaluation of SubClassOf we can
5 Although these operations, together with those in Section 4.2, could be reduced
to several consistency checks, this more high-level interface allows for well-known
optimizations of classi cation/instance retrieval operations [
The main advantage of this approach is that it makes use of an existing conjunctive ABox engine, thus providing a support for evaluation of bnodes for free. On the other hand, this approach might not have an optimal performance w.r.t. the reordering optimization introduced in Section 5.1.
Mixed Evaluation For queries without bnodes we can make a simple extension
of (i) the evalAtom( ) method for handling also Type and PropertyValue atoms
and of (ii) the OWL-DL reasoner interface:
ir(O; C) returns all instances of class C in O. Several strategies and optimizations
can be considered here, e.g. linear vs. binary instance retrieval [
This approach performs better w.r.t. the query reordering optimization described below. Unlike separated evaluation where Qs is executed rst and reordered separately from Qc, in mixed evaluation the query is reordered as a whole and schema and the data parts can be evaluated in any order. 5 5.1
A query reordering optimization for ABox queries without bnodes is described
in [
For the purposes of SPARQL-DL, we generalized the reordering strategy mentioned above. The query is reordered and the ordering with minimal cost is chosen according to the Algorithm 3. The cost computation for given atom ordering is shown in Algorithm 4. For each query atom q we need two functions: eC(O; B; q), that estimates the cost needed to evaluate an atom q, and eB(O; B; q), that estimates number of execution branches generated by evaluating q. Both functions take as an argument a collection B of bound variables, binding of which is unknown at given execution point.
1: function next(O; W; B) Require: W 6= ; 2: if B 6= ; then return W 3: W W 4: cost 1 5: for Wp 2 perm(W ) do . perm(W ) returns all permutations of W 6: if cost > staticCost(Wp; ;) then 7: cost staticCost(Wp; ;) 8: W Wp 9: return W 10: end function
function staticCost(W; B) if W = ; then return 1 [qjWr] W return eC(B; q) + eB(B; q) staticCost(Wr; B [ fall variables in qg) 5: end function Knowledge Base Operation Costs For each knowledge base operation described, a typical cost can be estimated. We reduce each of these cost estimates to four atomic costs, which are parameters of the optimizer: noSat, oneSat, classif y and realize for operations requiring respectively no consistency check, one consistency check, ontology classi cation and ontology realization. As an example let's take an atom DisjointWith(?x ; C), evaluation of which is reduced to the subC(:C). Cost estimates are reasoner dependent, for Pellet the call subC( ) would require ontology classi cation, thus eC(;; DisjointWith(?x ; C)) = classif y. Having a non-empty B it is necessary to estimate typical performance of the operations, thus eC(f?xg; DisjointWith(?x ; C)) = oneSat.
Estimating number of candidates While the costs of knowledge base operations are dependent on the form of their arguments and on the KB state (classi ed, realized), the number of candidates for a given query atom can be estimated using a cheap preprocessing of O, making use of two structures : Information cached during consistency checking is used to get estimates for query atoms Type; PropertyValue, SameAs, Di erentFrom, like number of types, or number of same individuals for given individual, etc.
Told axioms are used to get estimates for other atoms, like number of named subclasses for given class, number of functional properties in O, etc.
For example, to compute the number of branches for atom SubClassOf(?x ; C), we would need to estimate how many named subclasses C has in O. If C is a named class, we can simply use the told class taxonomy for this estimate. If C is a complex class then some kind of heuristics can be used, but we did not investigate this possibility in detail and focused on named concepts in queries. 5.2
In addition to the general cost-based reordering of the query, we can also exploit the query structure. For example, consider the query
SubClassOf(?x ; Person); Type(?y ; ?x ) which tries to retrieve all instances ?y of the class Person together with their actual type ?x. When evaluating this query in this order we can exploit information from the class hierarchy and prevent variable ?x to be bound to subclasses of a class C which produced no result when used as a binding for ?x. Thus, we can start exploring the class hierarchy from the top and prune the parts of the class hierarchy if the root of a part does produce no results.
For this purpose we introduce the following notion. At a given execution point, a down-monotonic variable is any variable ?x 2 Vvar that occurs in a Type( ; ?x ), or PropertyValue( ; ?x ; ), later in the query Q. Whenever the engine is about evaluating an atom q that contains a down-monotonic variable ?x, it can safely perform the above described pruning. 6
We have implemented both the separated and the mixed query evaluation strategies in the open-source OWL-DL reasoner Pellet. As mentioned in Section 3, instead of creating a new benchmark from scratch we decided to build our experiments on top of the LUBM dataset and queries. LUBM is a data-oriented benchmark with a smal schema (only several tens of classes and properties) and large number of instances (17000 individuals in the LUBM(1) dataset we used).
We ran the 10 SPARQL-DL queries we created against both the separated and the mixed query engines. In the mixed query engine we ran the experiments both with and without down monotonic variable optimization. Figure 1 shows the query execution times we got for these three instances of query engines.
The results show that the separated query evaluation can match the performance of mixed query engine in some cases but is mostly outperformed. Interestingly, there is a case (Q1 which corresponds to Example 1 from Section 3) where separated engine performs signi cantly better. Investigating the query evaluation for this query revealed that sometimes evaluating TBox/RBox atoms rst and then reordering the ABox query based on those results provide better results. For Q1, the separated engine tries properties in the KB one by one and changes the ordering of the ABox query for di erent properties. These reorderings are much more precise because they use the statistics for the actual property used while evaluating the query atom. Mixed evaluation, on the other hand, computes the reordering once at the beginning based on the overall statistics averaged over all properties and uses the same ordering for every property. This analysis indicates that dynamic reordering strategy in mixed evaluation would be valuable.
The results show that there is only one case (query 7) where the optimization for down-monotonic variables improves the performance. This is not too surprising considering that this optimization exploits the structure of the class/property hierarchies which are both shallow and narrow in the case of LUBM. The query 7 refers to owl : Thing (top of the class hierarchy) in a TBox axiom making the whole class hierarchy relevant for this query and that makes the e ect of down monotonism most visible. It is also important to note that the optimization for down monotonic variable does not introduce any overhead for the other queries. 7
In this paper, we have presented SPARQL-DL evaluation scheme and experience from its implementation in the Pellet reasoner. Two engines were shown: (i) a separated query engine that makes use of an existing ABox query engine as a black box, and (ii) a mixed query engine that answers queries without undistinguished variables. For both engines we have introduced two optimizations; a cost based query reordering and a notion of down-monotonic variables that prunes the search space of the query execution making use of concept/role hierarchies.
Our preliminary experiments show that the separated query evaluation works reasonably well in most cases. There are even some cases where it outperforms the mixed query engine which suggests the mixed query engine can be improved by a dynamic reordering method that we will investigate in the future. Also the cost-based reordering currently implemented is a preliminary prototype and will be revised to be applicable to ontologies with di erent characteristics.
Although not mentioned in the paper, the engine can be augumented in a
simple way with non-monotonic atoms (like DirectSubClassOf), see [
There are several other directions for future work. First, we will likely expand SPARQL-DL and Pellet's implementation of SPARQL-DL to cover more of the SPARQL language, like FILTERs and OPTIONALs. Second, we want to extend the mixed query engine with evaluation of queries with bnodes in the Type and PropertyValue atoms. Handling Di erentFrom atoms with bnodes is an open issue. 8
This work was done during Petr Kremen's internship at Clark & Parsia, LLC during the Semantic Summer 2007 program and was partially funded by the NATO Consultation, Command and Control Agency (NC3A) and by the grant No. MSM 6840770038 \Decision Making and Control for Manufacturing III" of the Ministry of Education, Youth and Sports of the Czech Republic; we thank Dave Clarke, Alex Tucker, Sven Kuehne, and Arno Bijl for their support. The authors would like to thank Bijan Parsia for insightful discussions about SPARQL-DL.