Incremental SPARQL Evaluation for Query Answering on Linked Data

Abstract

SPARQL is the standard query language for RDF data. However, its application to Linked Data is challenging because the assumption that all necessary data is present at the beginning of the evaluation does not apply. Some relevant data sources may only be discovered by processing available data. Existing approaches provide implementations that compute results for basic graph patterns incrementally while retrieving the data. We contribute to this area by a formal analysis of the SPARQL algebra to provide incremental adaptions of the operations. This enables us to evaluate the costs of the incremental evaluation for the design of optimizers that choose the presumably best computation depending on the number of insertions and deletions. In addition, we propose a construction of the SPARQL dataset from Linked Data resources that enables the usage of the Graph-operator in query answering for Linked Data.

-

On the Semantic Web, data publishing according to the Linked Data [ 4 ] principles gained significant importance. The numerous projects mentioned in the Linking Open Data cloud diagram1 and recent ones in librarianship [ 8,17 ] show its broad adaption by private, public, and governmental initiatives. Apart from its appealing simplicity in data publication, its inherent distribution can forward the demanded decentrality of the Web [ 2 ] by allocating data at many sites rather than in centralized stores. However, Linked Data raises new challenges for query answering. In our research, we investigate these problems and contribute novel approaches for SPARQL [ 19 ] evaluation over Linked Data.

By interweaving name and address (cf. [ 5 ]), resources become dereferenceable in Linked Data and return an RDF description [ 14 ] on request. To put it simply, each resource can be perceived as data source. This has three implications: 1. The number of data sources is proportional to the number of resources. 2. Creating and deleting resources changes the number of data sources. 3. Data sources cannot be classified without retrieving their content because resource names are not related to the content. 1 See http://richard.cyganiak.de/2007/10/lod/ Accordingly, query answering on Linked Data is quite different from traditional distributed query answering. On the one hand, in general it is not possible to specify all relevant data sources for a query in advance. Even in the case that all relevant sources have been identified for some query, another query may require different sources, and any new resource in the data may be an additional relevant source. On the other hand, subqueries cannot be delegated to the remote sources because Linked Data does not require the presence of query processors. Thus concepts like the Service-operator from the federation extension2 [ 6 ] of SPARQL 1.1 cannot be used to distribute parts of the query, for instance.

We illustrate our scenario in a small example with the query ‘Select ?x, ?n Where {alice knows ?x. ?x name ?n}’ to find out the names of Alice’s friends. Applying the “follow your nose”-approach from Hartig et al. [ 11 ] to discover relevant data sources, we start by dereferencing alice. We may receive the triples {(alice, knows, bob), (alice, knows, charlie), (bob, name, “Bobby”)}, and compute the result {{?x 7→ bob, ?n 7→ “Bobby”}}. Next, we request data about charlie receiving {(charlie, name, “Charlie”)}, and extend the result with {?x 7→ charlie, ?n 7→ “Charlie”}. Searching for more results, we request also bob and get {(bob, name, “Bob”)}. Having traversed all links3, the final result is {{?x 7→ bob, ?n 7→ “Bobby”}, {?x 7→ charlie, ?n 7→ “Charlie”}, {?x 7→ bob, ?n 7→ “Bob”}}. In the present work, we investigate the suggested incremental computation of the results formally. 1.1

Related Work

Recent work has presented different strategies and implementations to evaluate queries over Linked Data. In terms of Ladwig et al. [ 15 ], Hartig et al. [ 11 ] follow a bottom-up approach, i. e., a query is evaluated without any prior information. Dereferencing the query constants and then following some links in the data, the result is computed incrementally, similar to our above example. However, their implementation with so-called non-blocking iterators may miss some results depending on the evaluation order. Hartig alleviates this problem in [ 10 ] with heuristic adjustments. In contrast, Harth et al. [ 9 ] employ a top-down (cf. [ 15 ]) strategy. Acquired knowledge about sources is organized in a special index before queries are processed. The index is used to select the most promising sources for a given query. For our example their index would recommend alice, bob, and charlie at best letting the result be generated in a single run. Corresponding to our arguments, Harth et al. also mention that the query completeness can increase when data sources which are encountered in the evaluation but are not indexed are considered during the evaluation (e. g., retrieve charlie if only alice and bob are indexed). Ladwig et al. elaborate this idea and propose a mixed resp. explorationbased approach. They propose strategies for query-specific source selection, and use a symmetric hash join for the incremental computation that, unlike the nonblocking iterators, generates all results. In [ 16 ] they refine their join method with 2 Working Draft at

http://www.w3.org/TR/2010/WD-sparql11-federated-query-20100601/ 3 We do not consider the predicates here. the intention to consider a local storage beside the remote sources. However, the implementations are not based on an analysis of the SPARQL semantics. They consider only basic graph patterns, a subset of SPARQL and do not deal with decrements potentially induced by optional graph patterns. 1.2

Contribution

We are interested in the incremental SPARQL evaluation over increasing datasets generated by bottom-up Linked Data query answering. In accordance to [ 10 ] and [ 15 ], our assumption is that the solutions should be generated after each addition—we speak of an immediate processing—because an exhaustive link traversal prior to returning the first results seems unfeasible. The contrary, deferred processing, would delay the result computation until all data has been loaded. However, we need to investigate whether an incremental computation, i. e. modifying current results when the data changes, is superior to a direct computation, i. e. deriving all results from scratch in this case. At a first glance, this seems true for monotonically increasing results, and questionable for optional graph patterns that can introduce negation by failure. Therefore we study each SPARQL operator in detail to provide adaptions that enable incremental computation. By an estimation of the processing costs we get evidences for criteria that render one computation method preferable over the other, and make a step towards optimized immediate query processing for Linked Data. Outline. Next, we introduce RDF, SPARQL, Linked Data, and some algebraic equivalences that are necessary for our approach. In Sec. 3 we elaborate on our approach and show the incremental adaptions of the SPARQL operators. We compare our approach to the direct computation in Sec. 4. In Sec. 5, we conclude our work and sketch a possible further development, the application of the HTTP cache mechanism in query answering for Linked Data. 2

Preliminaries

We introduce the RDF data model and the SPARQL query language under special attention to the construction of the dataset by link traversal and to the relation between the Graph-operator and Linked Data resources. 2.1

RDF The RDF data format [ 12 ] describes essentially graphs with directed labeled edges. We consider RDF terms T comprising three pairwise disjoints sets I (IRIs), B (blank nodes), and L (literals). An RDF triple (s, p, o) ∈ I ∪ B × I × T connects node s (subject) through the directed labeled edge p (predicate) with node o (object). A finite set of triples is called RDF graph. The blank nodes in an RDF graph G are denoted by blank(G). We distinguish blank nodes with the prefix ‘_:’ and literals with double quotes (e. g., _:bn01, “Rain”) from IRIs.

A named graph G [ 7 ] is an entity hu, Gi with a name u ∈ I and an RDF graph G. It holds name(G) = u and gr(G) = G. Distinct named graphs do not share any blank nodes.

An RDF dataset D (cf. [ 1 ]) is a set containing a possibly empty default graph dg(D) = G0 and zero or more named graphs, ngs(D) = ? or ngs(D) = {G1, . . . , Gn} with Gi = hui, Gii, where for i 6= j (i) name(Gi) 6= name(Gj), and (ii) blank(Gi) ∩ blank(Gj) = ?. We write names(D) to denote {name(Gi) | Gi ∈ ngs(D)}, and gr(u)D = gr(Gi) if name(Gi) = u and Gi ∈ ngs(D), otherwise it is the empty RDF graph.

We use the operator ‘t’ to merge two RDF graphs and define the operator ‘+’ as follows. For a dataset D and a named graph G, D + G = D ∪ G with G0 = dg(D) t gr(G) if name(G) ∈/ names(D), else D + G = D. 2.2

SPARQL

SPARQL is a W3C-recommended [ 19 ] query language for RDF data. We follow the compositional semantics in [ 18,20 ] and include the Graph-operator as in [ 1 ]. Like there, our syntax differs from the W3C syntax in the previous example. Syntax. Let V be a set of variables, V ∩ T = ?. We indicate variables with a leading question mark (e. g., ?x). A triple pattern (s, p, o) ∈ IV × IV × ILV is a SPARQL expression.4 The variables of a triple pattern t are denoted by vars(t). If P1 and P2 are SPARQL expressions, so are P1 Filter R, P1 Union P2, P1 And P2, P1 Opt P2, u Graph P1 (u ∈ I), and ?x Graph P1. R means a filter condition: ?x =?y, ?x = c (c ∈ L ∪ I), and bnd(?x) are filter conditions; if R1 and R2 are filter conditions then ¬R1, R1 ∧ R2, and R1 ∨ R2 are, too. Finally, a query has the form SelectS,F1,F2 (P ) where S is a finite subset of V , P is a SPARQL expression, and the dataset specifications F1 and F2 are possibly empty finite subsets of I (cf. From and From Named in Sec. 8 of [ 19 ]). Semantics. A mapping μ is a partial function μ : V → T ; the domain of μ is denoted by dom(μ). There is an empty mapping μ0 with dom(μ0) = ?. Two mappings μ1, μ2 are compatible if for all ?x ∈ dom(μ1)∩dom(μ2) holds μ1(?x) = μ2(?x), written as μ1 ∼ μ2. A mapping μ1 is subsumed by a mapping μ2, denoted μ1 v μ2, if μ1 ∼ μ2 and dom(μ1) ⊆ dom(μ2). Mappings can be applied to triple patterns, written as μ(t), and replace all ?x ∈ dom(μ) ∩ vars(t) in t by μ(?x).

A mapping μ satisfies the filter condition R, denoted μ R, iff one of the following six conditions holds: (i) R is bnd(?x) and ?x ∈ dom(μ), or (ii) R is ?x =?y and bnd(?x) ∧ bnd(?y) ∧ μ(?x) = μ(?y), or (iii) R is ?x = c and bnd(?x) ∧ μ(?x) = c, or (iv) R is ¬R1 and ¬(μ R1), or (v) R is R1 ∧ R2, μ R1, and μ R2, or (vi) R is R1 ∨ R2, and μ R1 or μ R2.5 4 Blank nodes are not considered because they act as anonymous variables and can be replaced w. l. o. g. by unselected variables in a query. 5 The distinction between false and error in case of μ 6 R can be safely ignored in our context.

The solution of a SPARQL expression or query is a set of mappings. Let R be a filter condition and S a finite set of variables. For mapping sets Ω1, Ω2, the SPARQL set algebra defines the operations join (./ ), union (∪), minus (\), left join (¯on), selection (σ), and projection (π): ¯ Ω1 ./ Ω 2 := {μ1 ∪ μ2 | μ1 ∈ Ω1, μ2 ∈ Ω2 : μ1 ∼ μ2} Ω1 ∪ Ω2 := {μ | μ ∈ Ω1 ∨ μ ∈ Ω2} Ω1 \ Ω2 := {μ1 ∈ Ω1 | ∀μ2 ∈ Ω2 : μ1 6∼ μ2} Ω1 ¯¯no Ω2 := (Ω1 ./ Ω 2) ∪ (Ω1 \ Ω2) σR(Ω1) := {μ ∈ Ω1 | μ R} πS(Ω1) := {μ | dom(μ) ⊆ S ∧ ∃μ0 : dom(μ0) ∩ S = ? ∧ μ ∪ μ0 ∈ Ω1}

The evaluation semantics is defined by the help of a function [[.]] that transfers a query Q into set algebra, written as [[Q]]. For expressions P , the same function is used with two additional arguments to indicate the dataset D and an active graph G for the evaluation, written [[P ]]GD. Let t be a triple pattern, P1, P2 SPARQL expressions, u ∈ I, and R, S as before.

[[t]]GD := {μ | dom(μ) = vars(t) ∧ μ(t) ∈ G} [[P1 Filter R]]GD := σR([[P1]]GD) [[P1 Union P2]]GD := [[P1]]GD ∪ [[P2]]GD

[[P1 And P2]]GD := [[P1]]GD ./ [[P2]]GD [[u Graph P1]]GD := [[P1]]gDr(u)D

[[P1 Opt P2]]GD := [[P1]]GD ¯¯no [[P2]]GD [[?x Graph P1]]GD := [ [[SelectS,F1,F2 (P1)]] := ui∈names(D) πS([[P1]]GD0∗ ) πS([[P1]]GD00 ) if F1 = F2 = ? else [[ui Graph P1]]GD ./ {{?x 7→ ui}} According to [ 19 ], queries without dataset specification are evaluated over a default dataset D∗ available to the query processor. Otherwise the dataset is constructed as D0 := Fui∈F1 deref(ui) ∪ Svi∈F2 {hvi, deref(vi)i} . The function deref maps an IRI to its corresponding graph. 2.3

Linked Data

The term Linked Data [ 3 ] refers to several conventions that integrate data publication into the Web’s HTTP stack as well as to the published data itself. We focus on a key aspect, the identification of non-information (e. g., a person, cf. [ 13 ]) resources with URLs though their essence is not a transmittable message. A request for such a resource u ∈ I is thus redirected to an information resource f(u) which serves a description (e. g., RDF graph or HTML page) for u. So the references to other resources in descriptions are traversable and carry over the “follow your nose”-principle from the Web of Documents to the Web of Data. Graphs. Among others, the SPARQL Graph-operator is useful for restricting mappings to authoritative information (the information provided by the URI owner of a resource, cf. Sec. 2.2.2.1 in [ 13 ] and Sec. 5.1 in [ 3 ]). Unfortunately, the rather intuitive adaption of our introductory example, Select{?x,?n},?,? ((alice, knows, ?x) And (?x Graph (?x, name, ?n))), is inconsistent because non-information resources (friends of Alice here) are not RDF graphs. Therefore, – we define the dataset D0 := Fui∈F1 deref(ui) ∪ Svi∈F2 {hf(vi), deref(vi)i} to beware the equation of non-information resources with named graphs. Consequently, however, graph names in D0 are unpredictable before evaluating a query, so – we add (u, f, f(u)) to G0 for each dereferenced resource u to make the relation between u and its description f(u) explicitly available.

Of course, triples t with t.p = f got from external sources are not inserted into D0 to prevent tampering. Hence the previous query can be expressed as Select{?x,?n},?,?(((alice, knows, ?x) And (?x, f, ?y)) And (?y Graph (?x, name, ?n))) and does not return Alice’s nickname for Bob, Bobby. Query Answering. We follow the bottom-up approach from [ 11 ] to illustrate our approach. First, for all dereferenceable constants c ∈ I in a query we add f(c) to F1 and F2 and compute the mapping sets for this dataset. Second, we consider each dereferenceable c occurring in a mapping as a relevant source and insert f(c) into F1 and F2. The results over the extended dataset are computed incrementally based on the present mapping sets. We repeat the second step until F1 and F2 remain unchanged. 2.4

Algebraic Equivalences

Our approach is based on transformations of SPARQL algebra expressions. We define difference (−) and intersection (∩) for mapping sets as usual (cf. union above) and introduce two new equivalence rules additional to those from the synoptical table in [ 20 ] shown in Tab. 1. With ‘P1 ≡ P2’ we denote the equivalence between the algebra expressions P1 and P2. Note that minus is indeed distinct from difference: Consider Ω1 = {{?x 7→ a, ?y 7→ b}, {?x 7→ a}} and Ω2 = {{?x 7→ a, ?y 7→ b}}, then Ω1 \ Ω2 = ? as against Ω1 − Ω2 = {{?x 7→ a}}. Lemma 1 (FDPush). Let Ω1, Ω2 be mapping sets and R a filter condition, then σR(Ω1 − Ω2) ≡ σR(Ω1) − σR(Ω2).

Proof. We fix a mapping μ and show that it is contained in left hand side iff it is contained in the right hand side. “⇒”: Suppose μ ∈ σR(Ω1 − Ω2). It holds that μ ∈ Ω1, thus μ ∈ Ω1 − Ω2 because selection does not add mappings and μ ∈/ Ω2. It follows immediately that μ ∈ σR(Ω1) but μ ∈/ σR(Ω2). “⇐”: Suppose μ ∈ σR(Ω1) − σR(Ω2). Then it holds that μ ∈ Ω1 and μ R. We distinguish two cases. Case (1): We assume μ ∈/ Ω2 and are done. Case (2): We assume μ ∈ Ω2. Then μ ∈ σR(Ω2) because μ R and so μ ∈/ σR(Ω1) − σR(Ω2). This contradicts the first presumption.

Lemma 2 (MDReord). Let Ω1, Ω2, Ω3 be mapping sets, then (Ω1−Ω2)\Ω3 ≡ (Ω1 \ Ω3) − Ω2.

Proof. We proceed like above. “⇒”: Suppose μ ∈ (Ω1 − Ω2) \ Ω3. Then for all μ0 ∈ Ω3 holds μ 6∼ μ0, and μ ∈/ Ω2 but μ ∈ Ω1. It follows that μ ∈ Ω1 \ Ω3, and thus also μ ∈ (Ω1 \Ω3)−Ω2. “⇐”: Suppose μ ∈ (Ω1 \Ω3)−Ω2. Then μ ∈/ Ω2, and for all μ0 ∈ Ω3 holds μ 6∼ μ0. So μ ∈ Ω1 − Ω2 and finally μ ∈ (Ω1 − Ω2) \ Ω3. tu

3 Incremental SPARQL Evaluation

We want to evaluate SPARQL over an increasing dataset while we are interested in the result of a query after each addition to the data as outlined in the introduction. This can certainly be achieved by a complete evaluation over the whole data. However, we think that an approach that takes previously computed results into account might perform better. Therefore we provide an incremental adaption for each algebra operation to compute the result based on the changes of the operands between the dataset D and the increased dataset D + ΔD. We consider also the mechanism to select the active graph (Graph) and the evaluation of triple patterns.

Definition 1 (Insertions and Deletions). For a SPARQL expression P , an

RDF dataset D, and a named graph ΔD, let A = [[P ]]GD and A0 = [[P ]]GD+ΔD . We define insertions ΔA+ := A0 − A and deletions ΔA− := A − A0. It follows that (i) ΔA+ ∩ΔA− = ?, (ii) ΔA+ ∩A = ?, (iii) ΔA− ∩A0 = ?, (iv) ΔA− ⊆ A, and (v) A0 = (A − ΔA−) ∪ ΔA+. This must hold in the following transformations. 3.1

Algebra operations

For the transformations of union, join, and minus assume that A = [[P1]]GD, B = [[P2]]GD, A0 = [[P1]]GD+ΔD , and B0 = [[P2]]GD+ΔD have already been computed. Projection. Given Cπ = [[SelectS,F1,F2 (P )]], A = [[P ]]GD0 , A0 = [[P ]]GD0+ΔD , and ΔD = hf(u), Gi, we are interested in Cπ0 = [[SelectS,F1∪{u},F2∪{u}(P )]]. Δπ−, Δπ+ can be used when projections are pushed down in query optimizations. [[SelectS,F1∪{u},F2∪{u}(P )]] = πS([[P ]]GD0+ΔD ) = πS(A0) = {μ | dom(μ) ⊆ S ∧ ∃μ0: dom(μ0) ∩ S = ? ∧ μ ∪ μ0 ∈ A0} = {μ | dom(μ) ⊆ S ∧ ∃μ0: dom(μ0) ∩ S = ? ∧ μ ∪ μ0 ∈ (A − ΔA−)} ∪ {μ | dom(μ) ⊆ S ∧ ∃μ0: dom(μ0) ∩ S = ? ∧ μ ∪ μ0 ∈ ΔA+} = (πS(A) − {μ ∈ πS(ΔA−) | ¬∃μ0 ∈ A0: μ v μ0}) ∪ πS(ΔA+) Δπ− = {μ ∈ πS(ΔA−) | ¬∃μ0 ∈ A0: μ v μ0} Δπ+ = {μ ∈ πS(ΔA+) | μ ∈/ πS(A)} Selection. Given Cσ = [[P Filter R]]GD, we are interested in Cσ0 = [[P Filter R]]GD+ΔD. Assume A = [[P]]GD and A0 = [[P]]GD+ΔD have been computed yet. [[P Filter R]]GD+ΔD = σR((A − ΔA−) ∪ ΔA+) = σR(A − ΔA−) ∪ σR(ΔA+) (FUPush) = (σR(A) − σR(ΔA−)) ∪ σR(ΔA+) (FDPush) Δσ− = σR(ΔA−) Δσ+ = σR(ΔA+) Union. Given C∪ = [[P1 Union P2]]GD, find C∪0 = [[P1 Union P2]]GD+ΔD. [[P1 Union P2]]GD+ΔD = A0 ∪ B0 = ((A − ΔA−) ∪ ΔA+) ∪ ((B − ΔB−) ∪ ΔB+) = ((A − ΔA−) ∪ (B − ΔB−)) ∪ (ΔA+ ∪ ΔB+) (UAss, UComm) = {μ ∈ A ∪ B | (μ ∈ A ∧ μ ∈/ ΔA−) ∨ (μ ∈ B ∧ μ ∈/ ΔB−)} ∪ (ΔA+ ∪ ΔB+) Δ∪− = {μ ∈ A ∪ B | (μ ∈/ A ∪ ΔA+ ∨ μ ∈ ΔA−) ∧ (μ ∈/ B ∪ ΔB+ ∨ μ ∈ ΔB−)} Δ∪+ = {μ ∈ ΔA+ ∪ ΔB+ | μ ∈/ A ∪ B} Join. Given C./ = [[P1 And P2]]GD, find C.0/ = [[P1 And P2]]GD+ΔD. [[P1 And P2]]GD+ΔD = A0 ./ B 0 = ((A − ΔA−) ∪ ΔA+) ./ ((B − ΔB−) ∪ ΔB+) = ((A − ΔA−) ./ (B − ΔB−))

∪ ((A − ΔA−) ./ Δ B+) ∪ (ΔA+ ./ B 0) (JUDistR, JUDistL) = {μ ∈ A ./ B | ∃μ1 ∈ A, μ2 ∈ B: μ = μ1 ∪ μ2 ∧ μ1 ∈/ ΔA− ∧ μ2 ∈/ ΔB−} ∪ ((A − ΔA−) ./ Δ B+) ∪ (ΔA+ ./ B 0) Δ.−/ = {μ ∈ A ./ B | ∀μ1 ∈ A ∪ ΔA+, ∀μ2 ∈ B ∪ ΔB+ :

(μ1 ∪ μ2 = μ) → (μ1 ∈ ΔA− ∨ μ2 ∈ ΔB−)} Δ.+/ = {μ ∈ ((A − ΔA−) ./ Δ B+) ∪ (ΔA+ ./ B 0) | μ ∈/ A ./ B } Minus. Given Cr = A \ B, we are interested in Cr0 = A0 \ B0.

Cr0 = ((A − ΔA−) ∪ ΔA+) \ B0 = ((A − ΔA−) \ ((B − ΔB−) ∪ ΔB+)) ∪ (ΔA+ \ B0) (MUDistR) = ((A − ΔA−) \ ((B ∪ ΔB+) − ΔB−)) ∪ (ΔA+ \ B0) (ΔB− ∩ ΔB+ = ?) = ((A − ΔA−) \ (B ∪ ΔB+)) = (((A \ B) − ΔA−) \ ΔB+) ∪ {μ ∈ A − ΔA− | ∀μ0 ∈ (B ∪ ΔB+): μ ∼ μ0 → μ0 ∈ ΔB−} ∪ (ΔA+ \ B0) (MMUCorr, MDReord) ∪ {μ ∈ A − ΔA− | ∀μ0 ∈ (B ∪ ΔB+): μ ∼ μ0 → μ0 ∈ ΔB−} ∪ (ΔA+ \ B0) Δ−r = {μ ∈ A \ B | μ ∈ ΔA− ∨ ∃μ0 ∈ ΔB+ : μ ∼ μ0} Δ+r = {μ ∈ A − ΔA− | ∀μ0 ∈ (B ∪ ΔB+): μ ∼ μ0 → μ0 ∈ ΔB−} ∪ (ΔA+ \ B0) Left Join. C¯0no = [[P1 Opt P2]]GD+ΔD = A0 ¯¯on B0 can be expressed by join and ¯ minus, thus C¯0no = C.0/ ∪ Cr0, Δ¯−no = Δ.−/ ∪ Δ−r, and Δ¯+no = Δ.+/ ∪ Δ+r.

¯ ¯ ¯

3.2 Active Graph Selection and Triple Patterns

The selection of the active graph propagates to the subexpressions and finally takes effect in the evaluation of triple patterns. The active graph can also be changed inside the scope of a Graph-operator, yet it is not possible to reactivate the default graph. For example, [[u1 Graph (P1 And (u2 Graph P2)]]GD is equivalent to [[P1]]gDr(u1)D ./ [[P2]]gDr(u2)D, ui ∈ I.

Default Graph. Let t be a triple pattern and ΔD = hu, Gi. Given CDG = [[t]]dDg(D), we are interested in CD0G = [[t]]dDg+(DΔ+DΔD).

[[t]]dDg+(DΔ+DΔD) = [[t]]dDg+(Dhu+,Ghui,Gi) = [[t]]dDg+(Dhu),tGGi = {μ | dom(μ) = vars(t) ∧ t ∈ dg(D) t G} = {μ | dom(μ) = vars(t) ∧ t ∈ dg(D)}

∪ {μ | dom(μ) = vars(t) ∧ t ∈ G} = [[t]]dDg(D) ∪ [[t]]hGu,Gi ΔD+G = {μ ∈ [[t]]hGu,Gi | μ ∈/ [[t]]dDg(D)} Fixed Graph. The expression u Graph P with fixed graph name u is evaluated as [[P]]gDr(u)D. Let t be a triple pattern and CFG = [[t]]gDr(u)D. We are interested in CF0G = [[t]]gDr+(uΔ)DD+ΔD with ΔD = hu0, Gi. The expression is rewritten like above.

([[t]]gDr(u)D if u ∈ names(D) [[t]]gDr+(uΔ)DD+ΔD = [[t]]{hu0,Gi} if u = u0

gr(u)ΔD ΔF+G = ( [[t]]{hu0,Gi} if u = u0

gr(u)ΔD ? else Variable Graph. With variable graph name, ?x Graph P is evaluated as Sui∈names(D) [[ui Graph P ]]GD ./ {{x 7→ ui}} . Unlike before, it cannot be completely pushed down to the subexpressions. Let be ΔD = hu, Gi as above. Given CVG = [[P ]]gDr(u1)D ./ {{x 7→ u1}} ∪ . . . ∪ [[P ]]gDr(un)D ./ {{x 7→ un}} and Ai = [[P ]]gDr(ui)D , A0i = [[P ]]gDr+(uΔi)DD for ui ∈ names(D) we are interested in CV0G = Sui∈names(D+ΔD) [[ui Graph P ]]GD+ΔD ./ {{x 7→ ui}} . [ ui∈names(D+ΔD) [[P ]]gDr+(uΔi)DD+ΔD ./ {{x 7→ ui}}

={Bzi0 = [

ui∈names(D) |A0i ./ {{x 7→ ui}}} ∪ [[P ]]GD+ΔD ./ {{x 7→ u}} ΔV−G = [i ΔB−i ΔV+G = [i ΔB+i ∪ [[P ]]GD+ΔD ./ {{x 7→ u}} ? because μ1(?x) 6= μ2(?x) for μ1 ∈ ΔB+i , μ2 ∈ ΔB−j where i 6= j. ΔB−i and ΔB+i are composed as in Sec. 3.1 and thus disjoint. It holds ΔV+G∩ΔV−G = 4

Comparing Incremental and Direct Computation

We evaluate our approach by comparing the incremental computation to the direct computation. We exemplify these considerations for projection and leave out the other operations due to space limitations. Union behaves similarly, join and minus are slightly more complicated, and selection is easier.

Definition 2 (Projection of mappings). Let μ be a mapping and S a fi

nite set of variables. The mapping μ[S] is the projection of μ onto S where (i) dom(μ[S]) := dom(μ) ∩ S and (ii) μ[S](?x) := μ(?x).

Costs of Projection. Let sets with the operations insert, delete, and fsub to check for a subsuming mapping be given. We do not assume a specific order for the sets. The costs of evaluating an operation op are denoted by kopk.

The direct computation of the projection simply performs ‘for μ ∈ A0 do μ0 ←− μ[S]; Cπ0 insert μ0 end’, so its costs can be estimated at |A0| · (kμ[S]k + kCπ0 insert μ0k). An achievable proceeding for the incremental case is shown in Alg. 1. Its approximated costs are given in the following sum where α is the number of successful subsumption checks and β the number of changes to Cπ. |ΔA−| · kμ[S]k + kA0 fsub μ0k + (|ΔA−| − α) kCπ0 delete μ0k + kΔπ− insert μ0k + |ΔA| · kμ[S]k + kCπ0 insert μ0k + β kΔπ+ insert μ0k

+ Overestimating the insertions into Δπ+ we can conclude that the incremental adaption has fewer costs if ΔA− = ? and |A0| > 2 · |ΔA+|. Otherwise it depends on the size of ΔA− and opens the way for optimizations.

Algorithm 1: Compute Cπ0 = πS(A0) incrementally

Data: Mapping sets Cπ = πS(A), A0, ΔA−, ΔA+, variable set S Result: Cπ0 = πS(A0) begin Δπ− ←− ?; Δπ+ ←− ? for μ in ΔA− do

μ0 ←− μ[S]; if not A0 fsub μ0 then Cπ delete μ0; Δπ− insert μ0 for μ in ΔA+ do

μ0 ←− μ[S]; if Cπ insert μ0 changes Cπ then Δπ+ insert μ0 Towards an optimizer. A useful cost estimation is subject to the data and especially to the chosen implementation. If the direct evaluation is presumably cheaper, an optimizer may choose to compute Cπ0 only from A0. However, to support the incremental computation for operations that use Cπ0 as input, the costs to compute Δπ− := Cπ − Cπ0 and Δπ+ := Cπ0 − Cπ must be considered, too.

A different improvement can be achieved by using mapping multi-sets (cf.[ 20 ]) that combine a mapping μ with a multiplicity m(μ). In the computation of Δπ−, it must be checked for each mapping μ ∈ ΔA− whether there are still justifications for μ[S] in A0. By contrast, the multiplicities in a mapping multi-set are evidences for the number of justifications. By defining −A as A with each multiplicity multiplied by −1, we can compute Cπ0 = {μ ∈ πS(A) ∪ (−πS(ΔA−) ∪ πS(ΔA+)) | m(μ) > 0} (assuming that the operations cover multiplicities). Δπ− and Δπ+ can be assigned during the computation of the leftmost union for deletions (μ with m(μ) < 0) and insertions (μ with m(μ) > 0). 5

Conclusion and Future Work

We have presented a novel analysis of incremental SPARQL evaluation. Our results show means to design an optimizer that is able to choose the presumably best computation in the described Linked Data query answering scenario where the immediate processing of new data is desired. We have also proposed an integration of Linked Data resources and the Graph-operator based on specific construction of the SPARQL dataset. We think that our findings provide a sound formal basis for further research in this area.

Future Work. Next, we want to transfer the presented analysis to the SPARQL bag semantics and implement our approach with the described possibilities for optimization, and generalize ΔD in order to let it contain more than one named graph. Our approach may also be useful in combination with local caches. As Linked Data is built on top of HTTP, the cache-control mechanism6 could be used to detect and update outdated data on the fly in order to integrate the latest information during the query processing. 6 RFC #2616 Draft Standard at http://tools.ietf.org/html/rfc2616

References

1. Angles , R. , Gutierrez , C. : The Expressive Power of SPARQL . In: Proceedings of the 7th Int'l Semantic Web Conference (ISWC) . Karlsruhe, Germany ( 2008 )

2. Berners-Lee , T. : Long Live the Web: A Call for Continued Open Standards and Neutrality . Scientific American Magazine 12 ( 2010 )

3. Bizer , C. , Cyganiak , R. , Heath , T. : How to Publish Linked Data on the Web . Tech. Rep ., Freie Universität Berlin, The Open University ( 2007 ), http://www4.wiwiss. fu-berlin.de/bizer/pub/LinkedDataTutorial/, Accessed Aug 15 , 2011

4. Bizer , C. , Heath , T. , Berner-Lee , T. : Linked Data - The Story So Far . International Journal on Semantic Web and Information Systems (IJSWIS) 5 ( 3 ) ( 2009 )

5. Booth , D. : Four uses of a url: Name, Concept, Web Location and Document Instance (Jan 2003 ), http://www.w3.org/ 2002 /11/dbooth-names/dbooth-names_ clean.htm, Accessed Aug 15 , 2011

6. Buil-Aranda , C. , Arenas , M. , Corcho , O. : Semantics and Optimization of the SPARQL 1.1 Federation Extension . In: Proceedings of the 8th Extended Semantic Web Conference (ESWC) . Heraklion, Greece ( 2011 )

7. Carroll , J.J. , Bizer , C. , Hayes , P. , Stickler , P. : Named Graphs. Web Semantics: Science, Services and Agents on the World Wide Web 3 ( 4 ) ( 2005 )

8. Hannemann , J. , Kett , J.: Linked Data for Libraries . In: World Library and Information Congress: 76th IFLA Gen. Conf. and Assy . Gothenburg, Sweden ( 2010 )

9. Harth , A. , Hose , K. , Karnstedt , M. , Polleres , A. , Sattler , K.U. , Umbrich , J. : Data Summaries for On-Demand Queries over Linked Data . In: Proceedings of the 19th Int'l Conference on World Wide Web (WWW) . Raleigh, NC , USA ( 2010 )

10. Hartig , O. : Zero-Knowledge Query Planning for an Iterator Implementation of Link Traversal Based Query Execution . In: Proceedings of the 8th Extended Semantic Web Conference (ESWC) . Heraklion, Greece ( 2011 )

11. Hartig , O. , Bizer , C. , Freytag , J.C. : Executing SPARQL Queries over the Web of Linked Data . In: Proc. of the 8th Int'l Sem. Web Conf. Chantilly , VA , USA ( 2009 )

12. Hayes , P. , McBride , B.: RDF Semantics. W3C Recommendation ( Feb 2004 ), http: //www.w3.org/TR/2004/REC-rdf-mt- 20040210 /, Accessed Aug 15, 2011

13. Jacobs , I. , Walsh , N.: Architecture of the World Wide Web. W3C Rec. (Dec 2004 ), http://www.w3.org/TR/2004/REC-webarch- 20041215 /, Accessed Aug 15, 2011

14. Klyne , G. , Caroll , J.J. , McBride , B. : Resource Description Framework (RDF): Concepts and Abstract Syntax . W3C Recommendation (Feb 2004 ), http://www. w3.org/TR/2004/REC-rdf-concepts- 20040210 /, Accessed Aug 15, 2011

15. Ladwig , G. , Tran , T. : Linked Data Query Processing Strategies . In: Proceedings of the 9th Int'l Semantic Web Conference (ISWC) . Shanghai, China ( 2010 )

16. Ladwig , G. , Tran , T.: SIHJoin: Querying Remote and Local Linked Data . In: Proc. of the 8th Extended Semantic Web Conference (ESWC) . Heraklion, Greece ( 2011 )

17. Nandzik , J. , Heß , A. , Hannemann , J. , Flores-Herr , N. , Bossert , K. : Contentus - Towards Semantic Multi-Media Libraries . In: World Library and Information Congress: 76th IFLA General Conf. and Assembly . Gothenburg, Sweden ( 2010 )

18. Pérez , J. , Arenas , M. , Gutierrez , C. : Semantics and Complexity of SPARQL . ACM Transactions on Database Systems (TODS) 34(3) ( 2009 )

19. Prud'hommeaux , E., Seaborne , A. : SPARQL Query Language for RDF . W3C Recommendation (Jan 2008 ), http://www.w3.org/TR/2008/REC-rdf - sparql-query20080115/, Accessed Aug 15 , 2011

20. Schmidt , M. , Meier , M. , Lausen , G.: Foundations of SPARQL Query Optimization . In: Proceedings of the 13th International Conference on Database Theory (ICDT) . Lausanne, Switzerland ( 2010 )