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 diagram 1 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.
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 extension 2 [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 → bob, ?n → "Bobby"}}. Next, we request data about charlie receiving {(charlie, name, "Charlie")}, and extend the result with {?x → charlie, ?n → "Charlie"}. Searching for more results, we request also bob and get {(bob, name, "Bob")}. Having traversed all links 3 , the final result is {{?x → bob, ?n → "Bobby"}, {?x → charlie, ?n → "Charlie"}, {?x → bob, ?n → "Bob"}}. In the present work, we investigate the suggested incremental computation of the results formally.
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 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.
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.
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.
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 u, G 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) = G 0 and zero or more named graphs, ngs
We use the operator ' ' to merge two RDF graphs and define the operator '+' as follows. For a dataset D and a named graph
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 P 1 and P 2 are SPARQL expressions, so are P 1 Filter R, P 1 Union P 2 , P 1 And P 2 , P 1 Opt P 2 , u Graph P 1 (u ∈ I), and ?x Graph P 1 . R means a filter condition: ?x =?y, ?x = c (c ∈ L ∪ I), and bnd(?x) are filter conditions; if R 1 and R 2 are filter conditions then ¬R 1 , R 1 ∧ R 2 , and R 1 ∨ R 2 are, too. Finally, a query has the form Select S,F1,F2 (P ) where S is a finite subset of V , P is a SPARQL expression, and the dataset specifications F 1 and F 2 are possibly empty finite subsets of I (cf. From and From Named in Sec. 8 of [19]).
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
. 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(?
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 ( ¯ ), selection (σ), and projection (π):
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 ]] D G . Let t be a triple pattern, P 1 , P 2 SPARQL expressions, u ∈ I, and R, S as before.
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
The function deref maps an IRI to its corresponding graph.
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 D := ui∈F1 deref(u i ) ∪ vi∈F2 { f(v i ), deref(v i ) } to beware the equation of non-information resources with named graphs. Consequently, however, graph names in D are unpredictable before evaluating a query, so add (u, f, f(u)) to G 0 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 D 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 F 1 and F 2 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 F 1 and F 2 . The results over the extended dataset are computed incrementally based on the present mapping sets. We repeat the second step until F 1 and F 2 remain unchanged.
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 'P 1 ≡ P 2 ' we denote the equivalence between the algebra expressions P 1 and P 2 . Note that minus is indeed distinct from difference: Consider Ω 1 = {{?x → a, ?y → b}, {?x → a}} and Ω 2 = {{?x → a, ?y → b}}, then Ω 1 \ Ω 2 = ∅ as against Ω 1 − Ω 2 = {{?x → a}}.
Let Ω 1 , Ω 2 be mapping sets and R a filter condition,
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
. Then it holds that µ ∈ Ω 1 and µ R. We distinguish two cases. Case (1): We assume µ /
∈ Ω 2 and are done. Case (2): We assume µ
. This contradicts the first presumption.
Let Ω 1 , Ω 2 , Ω 3 be mapping sets, then
Proof. We proceed like above. "⇒": Suppose
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.
This must hold in the following transformations.
For the transformations of union, join, and minus assume that
have already been computed.
π can be used when projections are pushed down in query optimizations.
[
= A ¯ B can be expressed by join and minus, thus
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. . with ∆ D = u , G . The expression is rewritten like above.
Variable Graph. With variable graph name, ?x Graph P is evaluated as
Bi and ∆ + Bi are composed as in Sec. 3.1 and thus disjoint. It holds
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. 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 op . The direct computation of the projection simply performs 'for µ ∈ A do µ ←− µ[S]; C π insert µ end', so its costs can be estimated at |A | • ( µ[S] + C π insert µ ). 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 π .
Overestimating the insertions into ∆ + π we can conclude that the incremental adaption has fewer costs if
Otherwise it depends on the size of ∆ − A and opens the way for optimizations.
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 π only from A . However, to support the incremental computation for operations that use C π as input, the costs to compute ∆ − π := C π − C π and ∆ + π := C π − 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 A . 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 π = {µ ∈ π 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).
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.