In recent years, the ever-increasing number of available linkeddata endpoints has allowed the creation of complex data pipelines leveraging these massive amounts of information. One crucial challenge for federated pipeline designers is to know when to query the various sources they use in order to obtain fresher nal results. In other words, they want to know when a data update on a speci c source impacts their own nal results. Unfortunately, the SPARQL standard does not provide them with a method to be aware of such updates; and therefore pipelines are regularly relaunched from scratch, often uselessly. To help them decide when to get fresher results, we propose a constructive method. Practically, it relies on digitally signing result sets from federated endpoints in order to create a speci c query able to warn when, and explain why, the pipeline result set is outdated. In addition, as our solution is exclusively based on SPARQL 1.1 built-in functions, it is fully-compliant with all the endpoints.
During the past decades, the number of linked open datasets has rapidly
increased1. These datasets are structured following the W3C standard Resource
Description Framework (RDF) [
Bene ting from these two decades of developments made by the community, it is now possible to deploy Semantic Web pipelines and to adapt them to a wide range of needs and use-cases. Recent developments have been, for example, focused on distributed systems or on connecting Semantic Web data management systems together with non-RDF centric systems, paving the road to querying heterogeneous data. As a consequence of this increasing complexity of the usecases, the pipelines themselves are getting more complicated, and often rely on several distinct data sources using SPARQL federation techniques, in order to compute their nal results.
Hence, as data available may change, these pipelines (or parts of them) are frequently re-run in order to get fresher results. However, lots of times they are re-run unnecessarily as datasets have not been updated in the meantime in ways that impact the result sets of the pipeline. All these operations are leading to a waste of computation power and loads on the network.
In this article, mainly dedicated to SPARQL practitioners and data pipeline
designers, we present some possibilities provided by SPARQL 1.1 [
In this Section, we review several use-cases where the use of SPARQL hashing features becomes relevant. In particular, we focus on various methods to obtain a \signature" of a SPARQL result set. 2.1
The SPARQL standard provides a large set of built-in functions, from ones dedicated to strings to speci c ones about dates. These can be used by query designers to re ne their result set. In particular, the standard o ers a set of ve hash functions2: MD5, SHA1, SHA256, SHA384 & SHA512.
simple literal hash_function (simple literal arg) H = md5("ab") = md5("ab"^^xsd:string) simple literal hash_function (xsd:string arg) H = "187ef4436122d1cc2f40dc2b92f0eba0"
These functions accept either RDF literals or strings as argument and return the hash as a literal. In addition, a xsd:string or its corresponding literal should return the same result. In the `MD5' example above, the hash value represents the result of a simple SPARQL query3. 2.2
Technically, the standard hash functions provide the query designer with useful tools to, for instance, check/sign a speci c value within a filter eld. Nevertheless, they could also be used for more complex tasks that simply checking a 2 https://www.w3.org/TR/sparql11-query/#func-hash 3 select * wheref values ?x f"ab" "ab"^^xsd:stringg bind (md5(?x) as ?H)g value. For example, in a more extreme case, they could be used over a complete RDF graph through a SPARQL endpoint: one can extract all the triples available with select * where f?s ?p ?og, and then hash all of them, aggregated with a group concat function. This could look like so: SELECT (SHA1(GROUP_CONCAT(?tripleStr ; separator= \n ))) AS ?nTriples WHERE { ?s ?p ?o
BIND(CONCAT(STR(?s), " ", STR(?p), " ", STR(?o)) AS ?tripleStr) } In the previous query, the triples ?s ?p ?o are cast by element to a string (STR), and then concatenated to form a \triple". The recomposed list of triples is then grouped into one single string (GROUP CCONCAT) and nally hashed.
Obviously, this \naive" approach has drawbacks. First, the result depends on
the order of the triples returned by the triplestore: a workaround can be achieved
adding e.g. ORDER BY ?s ?p ?o datatype(?o) lcase(lang(?o)). Second, this
method has a scalability issue, as all the graph is loaded in-memory before the
hash call. We therefore recommend this approach to sign small RDF graphs,
e.g. ontologies or small result sets. Finally, this method does not address the
complex case of blank node identi cation as e.g. f :a p og and f :b p og do
not have the same hashes (see e.g. [
More pragmatically however, these hash functions can be used in order to sign
SPARQL query result sets [
Using this method, a SPARQL pipeline designer can easily obtain a hash corresponding to a result set, and store it for computing a comparison later. She would therefore know if RDF data updates have been impacting, in the meanwhile, her results. On advantage of such a method lays in the place where the computations happens: the SPARQL endpoint which could thereby be in charge of having otpimisation techniques (such as result caching or sub-view updating) to retrieve the result sets faster. 2.4
SPARQL pipelines often rely on several data sources that are queried on-the- y and whose sub-results are aggregated to form the nal result set. Practically, the SPARQL standard provides the designers with a built-in function to call an external endpoint with speci c conditions: the SERVICE keyword. This keyword is supposed to take as arguments a SPARQL endpoint URI5 and a set of conditions similarly to the where clause.
Consequently, by the mean of SPARQL sub-queries it is possible to re ne the previous method when the designer sets up federated queries. Indeed, each SERVICE call can be extracted and encapsulated following the steps presented previously. For example, considering SELECT ?s WHERE f ?s ?p ?o . SERVICE <URI> f ?s ?t ?u . gg, we can obtain a ner precision computing the following two hashing SPARQL queries: SELECT (MD5(GROUP_CONCAT(CONCAT(
STR(?s),STR(?t),STR(?u)); separator= \n )) as ?ServiceHash) WHERE{ SELECT ?s ?t ?u WHERE { SERVICE <URI> { ?s ?t ?u. } } ORDER BY ?s ?t ?u SELECT (MD5(GROUP_CONCAT(CONCAT(
STR(?s)); separator= \n )) as ?ResultSetHash ) WHERE{ SELECT * WHERE { SELECT ?s WHERE { ?s ?p ?o. SERVICE <URI> } { ?s ?t ?u. } } } ORDER BY ?s } The rst query (left-hand side) focuses on computing a hash of the results set 5 According to the SPARQL 1.1 standard, this SPARQL endpoint URI may also be a variable, e.g. \SERVICE ?url f ... g", requiring the endpoint to rst retrieve the possible entities for this variable and then call the external endpoints applying the set of conditions. However, this case is currently out of our scope. obtained from the external source; and the second one hashes the complete result set obtained once the local and the external results are joined.
More generally, one needs to generate one dedicated hashing query per SERVICE call plus a general hashing query for the main/top-level SPARQL query. By using this strategy, the query designer is then able to create her merkle tree6 of her di erent sources' sub-results. Moreover, this method is fully compliant with the SPARQL standard as it uses exclusively built-in functions. Finally, this \incremental" approach allows the users to know which source has been updated in a way that might impact the general query. 3
Automation for complex federated SPARQL queries The aforedescribed steps to generate the queries that obtain the hashes, splitting the query into pieces based on SERVICE, are easy to automate and allow users to know when to relaunch their pipelines. In order to help pipeline designers in practice, we serve our method at: https://dgraux.github.io/SPARQL-hash/ where our query converters can be used directly by developers to generate queries computing the hash of their result sets both for \regular" SPARQL queries and federated ones.
In the case of source federation, as the generation of several hashing queries (as presented in the previous section) is tedious and prone to committing errors, we also provide a generator dedicated to federated queries. Practically, our generator takes the SPARQL query Q and returns a new one Q hash which take care of computing all the necessary hashing sub-queries once run on the designers' SPARQL endpoint7. Speci cally, Q hash's result is another SPARQL query Q check which is in charge of running8 the various hashing sub-queries in order to compare the hashes with the previous ones obtained by Q hash. By construction, Q hash is supposed to be run only once and Q check should be the one -once obtained- used regularly to check if Q needs to be relaunched in order to update the designer's nal result set. Furthermore, Q check is built in a way which allows the query designers to know why she should update her nal result set; it actually explains which speci c source is updated.
As Q check and more Q hash tend to be long, we refer the reader to the extensive set of examples on our website for details. Notwithstanding, for the sake of clarity, let's consider the following simpli ed query (Q): select * where f ... service uri f...gg. Let's now name Qserv and Qgene the sub-queries generating "123" and "abc": the hashes (following the methods proposed in Sections 2.3 & 2.4) for the service part and for Q respectively. Therefore, Q check would have the following sketch: select ?res where { { Q_serv } # To compute a fresh hash for the service 6 Following recursively the SERVICE calls. 7 i.e. the same endpoint as the one where Q is supposed to be run. 8 Like Q hash, Q check should be run on the endpoint where Q is supposed to be run. { Q_gene } # To compute a fresh hash for Q if (Q_serv="123"){ if (Q_gene="abc") {?res="No update"} else {?res="Local data has changed"} } else {
?res="External source has changed" } } As presented above, Q check inspects the possible updates of hash results using a set of nested conditions. In particular, this set of conditions follows the exploration of a merkle tree starting from the bottom layer. Therefore, by structuring the query like so, an optimised SPARQL endpoint might be able to properly order its query plan in order to evaluate sequentially the various sub-queries and stop as soon as possible, saving computational resources. 4
This article describes how to improve existing Semantic Web data pipelines with a SPARQL-based method that helps in identifying when query results have changed. In particular, it sheds lights on a possible strategy when dealing with complex federated queries. It allows to re-run pipelines only when interesting parts of the original datasets have been updated. By using SPARQL to compute the signature of the query results, it avoids large result sets to be sent over the network. Finally, it also helps the designers identify what are the external sources that have been updated. We hope this will inspire developers to use the hash functions provided by the standard.