Introduction

In January 2008 SPARQL was officially approved by a W3C Recommendation [15] -a status which no other RDF query language has achieved. Parallel to this development a respectable number of SPARQL query engines have been developed, e.g. Jena ARQ, the Sesame SPARQL plugin or OWLIM as part of ORDI.

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 [4,11] supporting other subcomponents like query decomposition, query rewriting and join order selection for cost-based decision-making. Our cost model is similar to the ones for System-R suggested in [17,12] in that it estimates physical costs for each individual operation of a query and then totals these costs. Furthermore costs are distinguished by the type of used resources, i.e. number of CPU instructions, number of I/O operations (page/read accesses on persistent memory) and NET delay for retrieval of remote data. From this, a recursive cost function is developed for query execution based on physical cost functions and cardinality functions for basic operations in SPARQL Abstract Queries [15], a declarative representation of SPARQL queries (see section 3.1). Furthermore we presume a SPARQL query plan is given as a SPARQL Query Graph Model [9] which is a graph model for queries abstracting to the semantic of the corresponding SPARQL Abstract Query (see section 3.2). For the choice of complexities of basic SPARQL operations we argue that complexities of best-practice algorithms for related operations in the relational algebra for RDBMS can be used as orientation.

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.

Related Work

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. [13]. In their work they determined the complexity of certain types of SPARQL expression and developed an algebra for SPARQL resp. SPARQL graph pattern expressions which was a significant contribution to the theoretical algebraic model SPARQL Abstract Queries of SPARQL queries in [15]. Furthermore except for minor exceptions the possibility of a straightforward reduction of SPARQL to a SQL-resembling relational algebra has been shown in [3] which is the theoretical core of several SPARQL-to-SQL transforming SPARQL-DBMS like D2RQ or SquirrelRDF. Additional it can be attributed to the similarity between SPARQL and SQL algebras that a System-R-like graph model for SPARQL query plans together with optimization techniques query plans could be introduced [9].

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. [18] suggest for querying distributed RDF-repositories a schema-path-based indexing and storage organization as well as heuristics for join ordering. The techniques are implemented as a prototype extension for Sesame. In [2], RDFPeers, a spanning of RDF-Repositories over a Peer-to-Peer network is introduced. Execution of disjunctive and conjunctive queries over the distributed storages are described though RDFpeers doesn't support SPARQL as query language. In contrast to that Andreas Harth et al. [8] propose YARS2, a toolkit for efficiently querying distributed storages of graph-shaped data, especially RDF data and SPARQL are supported. A distributed indexing mechanism for quadruples (representing RDF triples) and distributed SPARQL query processing with join ordering are fundamental contributions of this work. While lookups for indexes can be dispatched concurrently in the distributed storage environment, other operations embodied in a SPARQL query (i.e. Join, U nion, etc.) are solely executed at one host in the system. An adaptive cost estimation based on System-R-like physical cost and cardinality functions is presented in [16] for conjunctive reasoning for Deductive Ontology Basis (DOB ), a subset of OWL lite. A translation of SPARQL queries into DOBs is promised by the authors for the future, but only partially explained at present.

In contrast to SPARQL the opportunities offered by distributed query processing are vastly explored in the database community. Kossmann describes in [11] a series of query processing optimization concepts in distributed databases in a textbook style. Pirahesh et al. [14] present rule-based rewriting techniques for queries which deliver optimization on a logical level independent from the physical implementation. Query plan cost models which sum up physical costs for single operators are suggested in [17,12]. Such a cost model is also needed as a subcomponent for an optimizer for distributed SPARQL processing as indicator for decision making of other components like query rewriting, decomposition or join and selection ordering. A sophisticated survey of adaptivity for query processing, especially intra-query adaptivity, was assembled by Deshpande et al. [4]. Adaptivity means the query processing is interleaved with adjustments by the query optimizer, which significantly improves the performance of the query evaluation 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.

Preliminaries

3.1 Formalization and Semantics of SPARQL Queries 3.1.1 SPARQL Abstract Queries For the study of SPARQL semantics, [15] provides a declarative formalization for a SPARQL query, called SPARQL Abstract Query. A SPARQL Abstract Query is a triple that consists of a Query Form, a SPARQL Algebra Expression and a RDF Dataset.

The set of Query Forms, denoted as QF, comprises four functions {Select, Ask , Construct, Describe} 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 {Join, Union, Diff , LeftJoin, ...} 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 = {BGP}∪SF the set of SPARQL Algebra Operations (SAO). The elements of the subset SM ⊂ SF , where SM = {Distinct, OrderBy, Limit, OffSet}, 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.

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 [15]: Definition 1. A solution mapping multi-set is a tuple (S, card) where S is a set of solution mappings and card is a function which annotates every x ∈ S with a positive integer.

The cardinality of (S, card), denoted as |(S, card)|, is the summation of card(x) for all x ∈ S.

SPARQL Query Graph Model

The SPARQL Query Graph Model (SQGM) [9] is a graph model for SPARQL queries resp. SPARQL Abstract Queries adopted from the Query Graph Models for SQL [14]. A SQGM is a planar rooted directed graph consisting of operator as nodes and dataflows as edges. Each operator represents an occurrence of an SPARQL algebra operation in the corresponding SPARQL Abstract Query while each data flow connects an operator A to an operator B, iff B uses A's result as input in the corresponding SPARQL Abstract Query. In this constellation A is called providing operator and B consuming operator. Furthermore operators are divided into types each of them having a one-to-one correspondence to a SPARQL basic operation, except for BGPs in combination with Filters and also for Solution Modifiers. For the first constellation SQGMs use an operator type, the set of Graph Pattern Operators (GPO), each corresponding to a BGP with an optional Filter operation. This set is referred to as GPO in the following. For Solution Modifiers SQGMs provide a general operator type, consisting of the Solution Modifier Operators which represent concatenations of arbitrary Solution Modifiers. Additionally we give the formal definition of a SQGM. r represents a Query Form), df lt ∈ 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 [9].

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.

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 Join operator and BGPs containing more than one triple pattern. By limiting joins between solution mapping multisets to the actual Join 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 BGP T P (resp. GPO T P ). As shown in the extension to [13] it is semantically equivalent to simulate BGPs embodying an arbitrary set of triple pattern by defining a BGP for each triple pattern and after that to join these.

Constrains for Solution Modifier Operators

As mentioned above a Solution Modifier Operator can express a application of several Solution Modifiers. In the following we only accept Solution Modifier Operators which represent exactly one Solution Modifier. A sequence of Solution Modifier appliances m 1 , . . . , m n in a SPARQL query can also be represented in a SQGM as a path of Solution Modifiers M 1 → . . . → M n where M i solely represents m i . This limitation is motivated by the need of a one-to-one correspondence for the sake of exchangeability of cost and cardinality functions for corresponding SPARQL basic operations and SQGMs operator types. The exchangeability of functions significantly assists the comprehensibility of the cost computations based on SQGMs.

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.

Cost and Cardinality Functions for SPARQL Basic Operations

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, RDFG 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 R kop 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) = (f CP U,op , f IO,op , f card,op ) where if op = BGP T P then f φ,op : (T P × RDFG × ALG × PPS) → R + with φ ∈ {CP U, IO, card}, else f φ,op : (R kop + × ALG × PPS) → R + with φ ∈ {CP U, IO, card}.

We call f IO,op resp. f CP U,op the IO resp. CPU cost function for op and f card,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 [15]. For instance, we could use the possible maximum of the result size. Hence such a procedure, which solely relies on the input sizes of an operator, causes generally a large estimation error. If available, statistical values for the result sizes of Triple Patterns, BGPs or more complex SPARQL Algebra Expressions are a highly recommended alternative.

Cost and Cardinality Functions for SQGM

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) = (f CP U,op , f IO,op , f card,op ). We call f IO,op resp. f CP U,op the IO resp. CPU cost function for t and f card,op the cardinality function for t. Analogously we use for t the references f IO,t = f IO,op , f CP U,t = f CP U,op and f card,t = f card,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 ∈ 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 ∈ 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 ∈ 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).

(D(c i ) • card(c i ) + costs N ET (c i )).

If x is a Select-, Describe-, Construct-, or Ask-Result Operator we refer to costs φ (x) also as the φ-cost function for G.

Cost Estimation Oriented on RDBMS Complexities

Based on [3] we will now prove that the choice of cost functions for SPARQL basic operations oriented on the complexities of best-practice-algorithms for relational algebra operations is sound. This is motivated by the fact that there are strong similarities between SPARQL basic operations and the operations of the relational algebra for RDBMS. To support this claim we will prove that almost each SPARQL basic operation is reducible to a single operation or a more complex term of the relation algebra for RDBMS in linear time while the cardinalities of the input values are preserved. 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 [1] in chapter 5.1, which contains the operations {σ, π, , δ, ∪, −}. In addition, we define a database relation with duplicates as follows. The cardinality of (r[U ], card RA ), denoted as

|(r[U ], card RA )| RA , is the sum- mation of card RA (t) for all t ∈ 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 dup , additional takes care of the card RA 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 dup , ∪ dup , − dup , π dup and σ dup are defined as follows: 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 ], card RA ): 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 ∈ S is represented by a tuple t x in r with card RA (t x ) := card(x) where t x has only values for the attributes which coincide with the domain of x (formally: attributes of t x who don't represent a variable in x have a globally defined null value, which belongs to no domain of the database schema).

Function dub : A × A → A is defined as ∪ dub ((r 1 , card RA,1 ), (r 2 , card RA,2 )) = (r, card RA ) with r = r 1 r 2 and for each t ∈ r, t 1 ∈ r 1 , t 2 ∈ r 2 , t = t 1 ∪ t 2 holds card RA (t) = card RA,1 (t 1 ) • card RA,2 (t 2 ). Function ∪ dub : A × A → A is defined as ∪ dub ((r 1 , card RA,1 ), (r 2 , card RA,2 )) = (r, card RA ) with r = r 1 ∪ r 2 and for each t ∈ r, t 1 ∈ r 1 , t 2 ∈ r 2 , t = t 1 = t 2 holds card RA (t) = card RA,1 (t 1 ) + card RA,2 (t 2 ). Function − dub : A × A → A is defined as ∪ dub ((r 1 , card RA,1 ), (r 2 , card RA,2 )) = (r, card RA ) with r = r 1 − r 2 and for each t ∈ r, t 1 ∈ r 1 , t 2 ∈ r 2 , t = t 1 = t 2 holds card RA (t) = |card RA,1 (t 1 ) − card RA,2 (t 2 )|. Function π dub : Att n ×A → A is defined as π dub (a, (r 1 , card RA,1 )) = (r, card RA ) with r = π(a,

In the following we use the denotations: trans(S) = R, trans(x) := t x , trans(S) := r, trans(card) := card RA , trans((S, card)) := (r, card RA ) 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 ∈ S iff trans(x) ∈ trans(S)

The algorithm's time and space complexity lies in O(|(S, card)|).

Theorem 1. Given a function f from SPARQL Abstract Terms to relational algebra terms with f (Join(S 1 , S 2 )) = dup (trans(S 1 ), trans(S 2 )),

f (Union(S 1 , S 2 )) = ∪ dub (trans(S 1 ), trans(S 2 )), f (Diff (S 1 , S 2 )) = − dub (trans(S 1 ), trans(S 2 )), f (LeftJoin(S 1 , S 2 )) = ∪ dup ( dup (trans(S 1 ), trans(S 2 )), − dup (trans(S 1 ), trans(S 2 ))),

where S 1 and S 2 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 φ ∈ {Join, Union, Diff , LeftJoin} the following statements hold

-x ∈ S iff trans(x) ∈ r[U ], -card(x) = card RA (trans(x)) for each x ∈ S, -trans-att(S) = U ,

where φ(S 1 , S 2 ) = (S, card), f (φ(trans(S 1 ), trans(S 2 ))) = (r[U ], card RA ) and both S 1 and S 2 are two multi-sets of solution mappings. Moreover, f is computable linear in time with respect to the sum of cardinalities of S 1 and S 2 , i.e. card(S 1 ) + card(S 2 ).

Proof. We show that for the operations Join,Union, Diff and LeftJoin the concluded statements hold.

A SPARQL Abstract Term Join(S 1 , S 2 ) = (S, card) with solution mappings multi-sets S = (S 1 , f 1 ) and S = (S 2 , f 2 ) is reduced by f to a (natural) join with duplicates in the relational algebra dup (trans(S 1 ), trans(S 2 )) = (r[U ], card RA ). For the generation of r from trans(S 1 ) and trans(S 2 ) operation dup (Definition 8) solely relies on . By the definition of ([1] p.58, top) and transformation algorithm trans it follows that trans-att(S) = U and the fact, that a solution mapping x is element of S iff there exists a tuple t x in r[U ] , which has the same values for its attributes as x for its respectively variables. Moreover, algorithm trans uses for the cardinality card RA (r) of a tuple t x ∈ r[U ] the same value as its corresponding solution mapping x (i.e. trans(x) = t x ). In addition, dup (Definition 8) relies on the same computation formula for cardinalities of tuples as the SPARQL basic operation Join for solution mappings. Thus card(x) = card RA (trans(x)) holds for each x ∈ S.

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(S 1 ) + card(S 2 ).

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 [3]. For these exceptions we will estimate their complexity based on known efficient implementations, also with orientation on similar operations in the relational algebra, if possible.

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.

Example

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 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 [7] -Statistics about cardinalities of solution mapping multi-sets for SPARQL Algebra Expressions are available for each RDF repository (e.g. for BGPs a schema-path-based index of the result cardinalities for n-way triple pattern joins would be possible, analogous to the source index hierarchy proposed by [18])

In Table 2 we provide a list of IO and CPU cost functions necessary for this example, i.e. for each occurring operator type. These functions were derived from [6,5]. Table 1 explains the used symbols.

f CP U = n 1 • c generic f IO = b 1 • c generic Join Operator NestedLoop-Join f CP U = n 1 • n 2 • ccompare f IO = b 1 • b 2 • cswap Hash-Join f CP U = min(n 1 , n 2 ) • ccomp+ + max(n 1 , n 2 ) • c hash f IO = (b 1 + b 2 ) • cswap + bres • c generic MergeSort-Join f CP U = (n 1 • logn 1 + n 2 • logn 2 + + n 1 + n 2 ) • ccompare f IO = (b 1 • logb 1 + b 2 • logb 2 + + b 1 + b 2 ) • cswap

LeftJoin Operator Union(HashJoin,Diff)

f CP U = f CP U,HashJoin (n 1 , n 2 )+ + (n 1 + n 2 ) • ccompare+ + n 1 • c hash f IO = f IO,HashJoin (b 1 , b 2 )+ + (b 1 + b 2 ) • cswap+ + b 1 • c generic

Graph Pattern Operator consisting only of a single triple pattern B+-Tree lookup

f CP U = ccomp • log b host nrepo f IO = cswap • (log b host nrepo + bres)

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:

c generic = c comp = 1, c swap = 10, c hash = 2, n repo = 10 6 , b host = 10

As implementation for the uppermost Join operator in G we use the MergeSort-Join 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 Join 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 Join 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 Join operator. 4. The resulting partitions for the sub trees of the uppermost Join operator in G lead to the sub queries q 1 and q 2 (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.

Conclusion and Future Work

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 [10] we additionally expect that the query processor and its optimizer operates in an intra-query adaptive fashion [4], i.e. the optimizer interleave query processing for dynamic adjustments and cost estimations to provide better response time or more efficient usage of resources.

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.