In the last years, the query language SPARQL has evolved into the widely accepted standard for querying RDF. Since many Semantic Web applications make use of data whose storage and management is distributed, distributed SPARQL query processing becomes necessary. In the relation and object-oriented database community the efficiency gain by cost-based, adaptive optimizers for distributed querying is proven, though such optimizers are not available for SPARQL. Thus we describe in this paper a cost model which is meant to act as a sub component of a query optimizer for distributed SPARQL query processing to serve as a cost indicator for other subcomponents of the optimizer, e.g. query decomposition, query rewriting and choosing join algorithms and their order. The cost model is tailored for a heterogeneous grid of SPARQL processors and represents query plans as SPARQL Query Graph Models (SQGM). Costs are assigned in an System-R-like fashion relying on recursive cost and cardinality functions. Therefore evaluation complexities of basic operations in SPARQL queries are derived from the complexities of best practice algorithms for the algebraically equivalent basic operations in relational query languages.
In January 2008 SPARQL was officially approved by a W3C Recommendation
[
Since many Semantic Web applications eo ipso manage and store data in
distributed places, distributed SPARQL query processing becomes necessary.
Development of distributed query engines is only in a premature state since
none of the widely accepted query engines, including the ones mentioned above,
are designed for distributed query processing at all. As we will point out in
section 2 cost-based, adaptive optimization techniques are well established for
querying distributed relational or object-oriented databases. Since SPARQL is
based on the relational algebra of Relational Database Management Systems
(RDBMS), we believe it is possible to map these techniques to SPARQL. For
this reason we present here a cost model for the evaluation of SPARQL queries
tailored to act as part of an optimizer for adaptive, distributed query processing
[
In Section 2 we address the scientific background of this paper. In Section 3 we introduce the preliminaries necessary for the definition of the cost and cardinality function in Section 4. There we also deliver the proof for the equality of the complexities for relational algebra operators and their equivalent SPARQL basic operations. In Section 5 we demonstrate the usage of the cost model as part of a query optimizer. We conclude with a discussion of open problems and future work. 2
Some breakthroughs in the analysis of the expressiveness and classification of
SPARQL also with respect to other query languages has been achieved by
Perez et al.[
Research in distributed SPARQL query processing started recently and
predominantly leans on optimization techniques for general database query
languages and RDF query languages. Heiner Stuckenschmidt et al. [
In contrast to SPARQL the opportunities offered by distributed query
processing are vastly explored in the database community. Kossmann describes in
[
A System-R-like cost model and the cost-based, adaptive techniques addressed in the last paragraph are not available yet for a distributed SPARQL processing context. Thus our proposed cost model as part of a still to be developed optimizer for adaptive, distributed SPARQL query processing is a first step to change this circumstance. 3 3.1
3.1.1 SPARQL Abstract Queries For the study of SPARQL semantics,
[
The set of Query Forms, denoted as QF , comprises four functions fSelect ; Ask ; Construct ; Describeg which take a solution mapping multi-set (see Definition 1) as input, Construct additional uses a set of tripe pattern templates. Select returns a set of variable bindings, Ask a boolean, Construct and Describe a RDF graph.
The SPARQL Algebra, whose terms are called SPARQL Algebra Expressions, is an algebra representing graph patterns and solution modifiers in queries. It provides a set of unary or binary functions fJoin; Union; Diff ; LeftJoin; :::g and a set BGP of constants, which are called Basic Graph Patterns (BGP). Both function and constants return a solution mapping multi-set as result while taking solution mapping multi-sets and logical boolean constraints for variable bindings as input. In the following we refer to the set of these functions as SF , and we call SAO = fBGPg[SF the set of SPARQL Algebra Operations (SAO). The elements of the subset SM ½ SF , where SM = fDistinct ; OrderBy ; Limit ; OffSet g, are called Solution Modifiers (SM). Overall we refer to QF [ SAO as the set of SPARQL basic operations.
A SPARQL Abstract Term is either a SPARQL Abstract Query or a SPARQL
Algebra Expressions. Intuitively a SPARQL Abstract Term describes a “sub
term” of a SPARQL Abstract Query.
3.1.2 Solution Mapping Multi-Sets From a technical viewpoint solution
mapping multi-sets are unordered lists of solution mappings which may contain
duplicates. For our following discussion we adopt the mathematical definition
from [
The cardinality of (S; card), denoted as j(S; card)j, is the summation of card(x) for all x 2 S. 3.2
The SPARQL Query Graph Model (SQGM) [
r represents a Query Form), – df lt 2 OP is an operator providing the default RDF graph of the queried
RDF dataset,
– N G ½ OP is the set of graph operators that provide named graphs.
For particular details on SQGMs we refer to [
In the following we will base our cost estimation for SPARQL queries and
query plans on their corresponding SQGMs. While as shown above queries can
be translated directly into SQGMs query plans contain in general additional
physical information for each operator. Thus we consider SQGM as abstraction
of query plans in the sense that all physical information has been masked out.
3.2.1 Constraints for BGPs resp. Graph Pattern Operators Actually
there are two different SPARQL basic operations which can describe joins
between solution mapping multi-sets: The J oin operator and BGPs containing
more than one triple pattern. By limiting joins between solution mapping
multisets to the actual J oin operation of the SPARQL Algebra we unify these to
one form to ease the definition of cost and cardinality functions. Motivated by
this consideration we restrict BGPs (resp. GPOs) to the biggest subset of BGP
(resp. GPO), in which each BGP (resp. GPO) only contains exactly one single
triple pattern. We refer to this subset as BGPT P (resp. GPOT P ). As shown in
the extension to [
In this section we will describe the structure of the cost model for SQGMs and provide a justification to base our cost estimation on the complexities of best-practice-algorithms for relational algebra operations related to the SPARQL basic operations.
Overall the cost model for SQGMs banks on a recursive cost function relying in turn on a recursive cardinality function. Furthermore both cost and cardinality function themselves are based on functions estimating physical cost and solution cardinalities for each SPARQL basic operation.
At first we introduce a method to assign cost and cardinality functions to each SPARQL basic operation also depending on the used implementation algorithms. After that we show how we can recursively compute costs for SQGMs based on our earlier results. Finally we justify that we can reduce almost all SPARQL basic operations to corresponding relational algebra operations in linear time to the input cardinalities. 4.1
For each SPARQL basic operation we assign a cardinality, CPU- and IO-cost function. The cardinality function estimates the cardinality of the operation result, the CPU-function the necessary number of instructions and the IO-cost function the necessary number of hard disk (or page) accesses to process the operation. Each of these functions depends on the cardinalities of the input solution mapping multi-sets, the used algorithm and real number parameters expressing physical characteristics of the machine executing the query. To compute these functions for a triple pattern we use the pattern itself as indication for the cardinality of its solution mapping multi-set. This is motivated by the fact, that either we can retrieve the cardinality directly by sending the triple pattern to the RDF-Repositories or estimate the cardinality by a selectivity method with the triple pattern as input.
In Definition 3 we define a summarization of the function assignments above, denoted as configuration. Hereby T P stands for the set of all RDF Triple Pattern, RDF G for the set of all RDF-Graphs, ALG for the set of all algorithms implementing SPARQL basic operations. Moreover a physical parameter setup is defined as mapping from a set of identifiers to a set of reals. The set of all physical parameter setups is called PPS. The Cartesian product Rkop is the set of all possible tuples consisting of the cardinalities of the input solution mapping multi-sets for an operation op.
Definition 3. A configuration C is a function assigning each SPARQL basic operation op a tuple C(op) = (fCP U;op; fIO;op; fcard;op) where else fÁ;op : (Rk+op £ ALG £ PPS) ! R+ with Á 2 fCP U; IO; cardg. if op = BGPT P then fÁ;op : (T P £ RDF G £ ALG £ PPS) ! R+ with Á 2 fCP U; IO; cardg, We call fIO;op resp. fCP U;op the IO resp. CPU cost function for op and fcard;op the cardinality function for op.
The IO- and CPU-costs of a SPARQL basic operation can be estimated accurately by the usage of an elaborated time and space complexity function for the implementation algorithm, given that the estimation errors for the cardinalities of the input solution mapping multi-sets and the physical parameters are small.
If no additional information is available, a naive way to compute the
cardinalities of the results for a SPARQL basic operation is the usage of the result
cardinalities provided by the operator definitions in [
In this section we recursively determine the execution costs and result cardinalities of a query graph by beginning the recursion at its root moving to the nodes with in-degree 0. Relevant physical cost factors for the processing of an SQGM operator like costs for swapping, hashing, computation, etc. are given in a function, physical parameter assignment, and thus can be respected in the cost estimation. For the delay by transmission through the network we use a very simplistic approach by assigning a real number weight for each operator x which indicates the net distance between the host computing x and the host computing x’s upstream operator. The actual net costs for x is the product <size of transmitted data> ¤ <distance weight>. To determine the overall net costs for a SQGM we add up these products for each operator.
First of all we emphasize in Definition 4 the exchangeability of cost and cardinality functions for SPARQL basic operations and SQGM operator types presuming the restrictions stated in Section 3.2.1 and 3.2.2.
Definition 4. Given a SQGM (OP; DF; r; df lt; N G), a configuration C and a SQGM operator type t which represents a SPARQL basic operation op with C(op) = (fCP U;op; fIO;op; fcard;op). We call fIO;op resp. fCP U;op the IO resp. CPU cost function for t and fcard;op the cardinality function for t. Analogously we use for t the references fIO;t = fIO;op, fCP U;t = fCP U;op and fcard;t = fcard;op.
Before we can present the cardinality (Definition 5) and cost functions (Definition 6) for SQGMs, we need to determine three kinds of functions for a given SQGM G = (OP; DF; r; df lt; N G):
An algorithm assignment is a function which assigns each operator x 2 OP an algorithm. This algorithm is a implementation of x according to the type x belongs to. For instance, if x belongs to the Join Operator type, the algorithm is a join algorithm (NestedLoop-Join, Hash-Join,. . . ).
A physical parameter assignment is a function which assigns each operator x 2 OP a physical parameter setup. This physical parameter setup contains (approximation of) physical values relevant for the estimation of the processing costs (e.g. block size, costs for swapping, hashing or value comparison) for the machine executing x.
A net-distance weight assignment is a function which assigns each operator x 2 OP a positive real number. This number is a weight which expresses the net latency between the machine executing x and the machine executing x’s upstream operator. The weight is multiplied with the result cardinality of x to take the net latency to the machine where the upstream operator is processed into account.
Finally we define the recursive cardinality and cost functions for SQGMs (Definition 5 and 6).
Definition 5. For a SQGM (OP; DF; r; df lt; N G), a configuration C and a node x 2 OP , possessing the providing operators c1; :::; cn, the recursive function card : OP ! R+, called cardinality function, is defined as follows: if x 2 GPOT P then card(x) = fcard;GPOT P (tp; G) where tp is the triple pattern embodied in x and G is the input graph of x, else card(x) = fcard;x:type(card(c1); : : : ; card(cn)) where x:type denotes the operator type of x.
Definition 6. For a SQGM G = (OP; DF; r; df lt; N G), Á 2 fIO; CP U; N ET g, a configuration C, an algorithm assignment A, a physical parameter assignment P, a net-distance weight assignment D and a node x 2 OP the recursive function costsÁ : OP ! R+, called Á-cost function, is defined as follows: For Á 2 fIO; CP U g: if x 2 GPOT P then costsÁ(x) = fÁ;GPOT P (tp; G; A(x); P(x)) where tp is the triple pattern embodied in x and G is the input graph of x, else costsÁ(x) = fÁ;x:type(card(c1); : : : ; card(cn); A(x); P(x)) + + ∑ costsÁ(ci)
i2f1;:::;ng where x:type denotes the operator type, c1; :::; cn the providing operators of x.
For Á = N ET : costNET (x) = ∑
(D(ci) ¢ card(ci) + costsNET (ci)).
i2f1;:::;ng If x is a Select-, Describe-, Construct-, or Ask-Result Operator we refer to costsÁ(x) also as the Á-cost function for G. 4.3
Based on [
Actually this reduction only yields an upper bound for SPARQL basic operations, which might be too pessimistic for certain implementations of operations. To formally neglect this we have to show that there also exists a reduction in the other direction. More precisely, each relational algebra operation must be reducible to a corresponding SPARQL Abstract Term (see Section 3.1), while the most efficient computation of the reduction function for this operation has to be in the smallest complexity class for which the evaluation of the SPARQL Abstract Term is a member of. Alternatively we could empirically prove the usability of the upper bound gained by the reduction introduced here. This proof, by mathematical means or benchmark testing, is a future task.
Before we present the reduction in Theorem 1, we want to clarify that we
base the following discussion on the named version of the relational algebra, as
described by [
The cardinality of (r[U ]; cardRA), denoted as j(r[U ]; cardRA)jRA, is the summation of cardRA(t) for all t 2 r[U ].
Consequently we extend the operations of the relational algebra to be capable of handling relations with duplicates as operands. For instance, the extended version of the relational algebra operation Join, called ondup, additional takes care of the cardRA values of its result tuples such that they resemble the card values of the SPARQL basic operation Join. We also apply this concept for the pairings ([,Union),(¡,Diff ), (¼,Select ) and (¾,Filter ) Definition 8. Let A be the set of all relations with duplicates. The functions ondup, [dup, ¡dup, ¼dup and ¾dup are defined as follows: Function ondub: A £ A ! A is defined as [dub((r1; cardRA;1); (r2; cardRA;2)) = (r; cardRA) with r = r1 on r2 and for each t 2 r, t1 2 r1, t2 2 r2, t = t1 [ t2 holds cardRA(t) = cardRA;1(t1) ¢ cardRA;2(t2).
Function [dub : A £ A ! A is defined as [dub((r1; cardRA;1); (r2; cardRA;2)) = (r; cardRA) with r = r1 [ r2 and for each t 2 r, t1 2 r1, t2 2 r2, t = t1 = t2 holds cardRA(t) = cardRA;1(t1) + cardRA;2(t2).
Function ¡dub : A £ A ! A is defined as [dub((r1; cardRA;1); (r2; cardRA;2)) = (r; cardRA) with r = r1 ¡ r2 and for each t 2 r, t1 2 r1, t2 2 r2, t = t1 = t2 holds cardRA(t) = jcardRA;1(t1) ¡ cardRA;2(t2)j.
Function ¼dub : Attn£A ! A is defined as ¼dub(a; (r1; cardRA;1)) = (r; cardRA) with r = ¼(a; r1). For each t 2 r the cardinality cardRA(t) is the summation of cardRA;1(t1) for all t1 2 r1 with t = t1jt. Here Att is an arbitrary set of attributes and Attn the n-ary Cartesian Product of Att, t1jt is the tuple t1 restricted to the attributes of t.
Function ¾dub : Att £ Dom £ A ! A is defined as [dub(a; d; (r1; cardRA;1)) = (r; cardRA) with r = ¾(a; d; r1) and for each t 2 r, t1 2 r1, t = t1 holds cardRA(t) = cardRA;1(t1). Here Att is an arbitrary set of attributes and domains a set of arbitrary domains for a relational database.
For the reduction in Theorem 1 we define in advance a simple helper algorithm, called trans, to transform a solution mapping multi-set S = (S; card) to an equivalent DB-relation with duplicates R = (r[U ]; cardRA): The union of the variables in the domains of the solutions mappings in S is the set of attributes U for r. Thus the number of attributes in U is the overall number of different variables occurring in the the mappings in S. Furthermore each mapping x 2 S is represented by a tuple tx in r with cardRA(tx) := card(x) where tx has only values for the attributes which coincide with the domain of x (formally: attributes of tx who don’t represent a variable in x have a globally defined null value, which belongs to no domain of the database schema).
In the following we use the denotations: trans(S) = R, trans(x) := tx, trans(S) := r, trans(card) := cardRA, trans((S; card)) := (r; cardRA) and trans-att(S) = U .
For this algorithm we imply (without explicit proof): 1. The number of attributes in U is the overall number of different variables occurring in the solution mappings in S 2. x 2 S iff trans(x) 2 trans(S) 3. The algorithm’s time and space complexity lies in O(j(S; card)j). Theorem 1. Given a function f from SPARQL Abstract Terms to relational algebra terms with
f (Join(S1; S2)) =ondup (trans(S1); trans(S2)); f (Union(S1; S2)) = [dub(trans(S1); trans(S2));
f (Diff (S1; S2)) = ¡dub(trans(S1); trans(S2)); f (LeftJoin(S1; S2)) = [dup(ondup (trans(S1); trans(S2));
¡dup (trans(S1); trans(S2))); where S1 and S2 are two multi-sets of solution mappings. Then f is a reduction of the SPARQL basic operations Join, Union, Diff, LeftJoin to relational algebra terms, i.e., for Á 2 fJoin; Union; Diff ; LeftJoing the following statements hold – x 2 S iff trans(x) 2 r[U ], – card(x) = cardRA(trans(x)) for each x 2 S, – trans-att(S) = U , where Á(S1; S2) = (S; card), f (Á(trans(S1); trans(S2))) = (r[U ]; cardRA) and both S1 and S2 are two multi-sets of solution mappings. Moreover, f is computable linear in time with respect to the sum of cardinalities of S1 and S2, i.e. card(S1) + card(S2).
Proof. We show that for the operations Join,Union, Diff and LeftJoin the concluded statements hold.
A SPARQL Abstract Term Join(S1; S2) = (S; card) with solution
mappings multi-sets S = (S1; f1) and S = (S2; f2) is reduced by f to a
(natural) join with duplicates in the relational algebra ondup (trans(S1); trans(S2)) =
(r[U ]; cardRA). For the generation of r from trans(S1) and trans(S2) operation
ondup (Definition 8) solely relies on on . By the definition of on ([
In an analogous way this can be shown for U nion and Diff. LeftJoin is defined as a SPARQL algebra term which combines Join, Union and Diff. Thus the reduction for Join, Union and Diff yields also a reduction for LeftJoin.
Furthermore, the definition of algorithm trans and reduction f implies that f is computable in linear time with respect to card(S1) + card(S2).
For most of the SPARQL basic operations we can determine the complexity
in the same way as in the proof of Theorem 1. Few are slightly different, e.g.
F ilter allowing regular expression in SPARQL which occasionally can not be
directly translated into the selection operation ¾ as pointed out in [
After the consideration above we are enabled to define a configuration oriented on the complexities for relational algebra operations for the example presented in Section 5. We use the complexity of relational algebra operations for the cost estimation of the related SPARQL algebra operations under the assumption that a SPARQL query processor is approximately as efficient as a RDBMS for the corresponding query (see Table 2). For SPARQL basic operations which are not reducible to relational algebra operations in the way described by Theorem 1, we rely on the complexities of best-practice implementations generally used by the database and Semantic Web community. 5
At this point we showcase the expected benefits of a query optimizer based on our cost model. Therefore we require a system of networked, collaborating
Listing 1.1: SPARQL query q PREFIX ub:< http : //www. l e h i g h . edu / . . . / univbench . owl#> FSPREROLEMEFCI<XTh?rtntdpf :?:<//chetxtpa m:/p/lwe w.wor. w/3U.noirvge/r1s9i9t9y/00.2o/w2l2>¡ rdf¡syntax¡ns#> WHEROE??Pss{TuIrObdNf: An:aLtmyp{ee ??nusb u.b: : GtarkaedsuCaotueSrsteud?enct . . } } hosts, whereas each host contains a RDF repository embodying such a query optimizer. We provide an exemplary SPARQL query q (Listing 1.1, Figure 1) and demonstrate how cost-based query decomposition will established an optimized distributed evaluation of the query in this system.
For this example we make the following presumptions for the host machines:
– The RAM size equals one block of persistent memory
– One I/O access equals reading of one block in persistent memory
– The RDF triples in the RDF repositories are indexed by a B+ tree as
described in [
Now we give a step by step walk-through of the distributed querying process: 1. Initially SPARQL query q (Listing 1.1) is transformed into a SQGM G (Figure 1). 2. Then the decomposition component determines – by calling the cost estimation component – the CPU-costs and IO-costs for each operator and thereby for each sub graph in SQGM. We use the following randomly chosen configuration of physical parameters for each operator in the SQGM G: cgeneric = ccomp = 1, cswap = 10, chash = 2, nrepo = 106, bhost = 10 As implementation for the uppermost J oin operator in G we use the MergeSortJoin algorithm (Note: A SQGM can be interpreted as rooted directed tree, if the Default Graph operator is ignored.). For all other operators in G the choice of the implementation is unambiguous (see Table 2). 3. After the decomposition component gets back the cost estimations (Figure 2) it decides the partitioning of SQGM G with one of the following strategies (These strategies are intuitive choices, their sophisticated research is targeted for the future.): If the query optimizer is regularly noticed about available resources, the partitions can be chosen w.r.t. to their costs and these resources, i.e. a matching between costs and resources is approximated. Alternatively the decomposition component tries to partition SQGM G into chunks with circa the same costs. Here we use the second strategy.
The overall costs for the left and right sub-tree at the upper-most J oin operator are 1012 + 1320 = 2332 and 6 + 310 = 316, if we weight CPU and IO costs with factor 1. Assume two remote hosts A and B are available with access to q’s default graph. A should have net-distance 3 and B net-distance 10 to the host which will process the uppermost J oin operator and the Select operator. The remote processing costs for the left subtree on host A would than be 2332 plus the net latency 3 £ 200 = 600, for the right subtree on host B 316 plus the net latency 10 £ 250 = 2500. Since A and B work parallel the overall cost is 2932 (if we have to wait until A is finished) for the remote processing of the both sub trees compared to a sequential local processing which is 2932 + 2816 = 6748. Thus we split G at the uppermost-most J oin operator. 4. The resulting partitions for the sub trees of the uppermost J oin operator in G lead to the sub queries q1 and q2 (Listings 1.2 and 1.3), which then are forwarded to host A and B for processing. The retrieved sub query answers routed back are combined to an answer for q according to its decomposition. PREFIX ub:< http : //www. l e h i g h . edu / . . . / univbench . owl#> FSPREROLEMEFCI<XTh?rttdspf :?:<//chetxtpa m:/p/lwe w.wor. w/3U.noirvge/r1s9i9t9y/00.2o/w2l2>¡ rdf¡syntax¡ns#> WHERE?s { r d f : type ub : GraduateStudent .
OPTIONAL { ? s ub : takesCourse ? c . } }
Listing 1.3: SPARQL query q2 PREFIX ub:< http : //www. l e h i g h . edu / . . . / univbench . owl#> FSPREROLEMEFCI<XTh?rttdspf :?:<n//hetxtpa m:/p/lwe w.wor. w/3U.noirvge/r1s9i9t9y/00.2o/w2l2>¡ rdf¡syntax¡ns#> WHERE { } ? s ub : name ?n . 6
We have developed a cost model that provides System-R-like cost and cardinality functions for SPARQL queries given as SQGMs and evaluated in an distributed environment. In addition we proved by reduction that for the cost estimation of most SPARQL basic operations complexities of relational algebra operations can be used as upper bounds. Hence, it has yet to be proven – mathematically or empirically – that these upper bounds are not to pessimistic.
For the future we plan an implementation of the cost model as part of query
optimizer for distributed query processing. Since the optimize-then-execute
paradigm is not efficient for complex queries due to exponential growth of the
estimation error [
We will evaluate the cost model in form of representative benchmarks tests for this implementation. In particular the accuracy of the upper bounds for SPARQL basic operations provided by the reduction mentioned above will be verified. 7
This work is partially supported by the TripCom (IST-4-027324-STP) project; http://www.tripcom.org.