Existing solutions to query dynamic Linked Data sources extend the sparql language, and require continuous server processing for each query. Traditional sparql endpoints accept highly expressive queries, contributing to high server cost. Extending these endpoints for time-sensitive queries increases the server cost even further. To make continuous querying over real-time Linked Data more affordable, we extend the low-cost Triple Pattern Fragments (tpf) interface with support for time-sensitive queries. In this paper, we discuss a framework on top of tpf that allows clients to execute sparql queries with continuously updating results. Our experiments indicate that this extension significantly lowers the server complexity. The trade-off is an increase in the execution time per query. We prove that by moving the complexity of continuously evaluating real-time queries over Linked Data to the clients and thus increasing the bandwidth usage, the cost of server-side interfaces is significantly reduced. Our results show that this solution makes real-time querying more scalable in terms of cpu usage for a large amount of concurrent clients when compared to the alternatives.
As the Web of Data is a dynamic dataspace, different results may be returned depending
on when a question was asked. The end-user might be interested in seeing the query results
update over time, and thus may have to re-execute the entire query over and over again
(i.e., polling). This is, however, not very practical, especially if it is unknown beforehand
when data will change. An additional problem is that many public (even static) sparql
query endpoints suffer from a low availability [
In this work, we therefore devise a solution that enables clients to continuously evaluate non-high frequency queries by polling specific fragments of the data. The resulting framework performs this without the server needing to remember any client state. Its mechanism requires the server to annotate its data so that the client can efficiently determine when to retrieve fresh data. The generic approach in this paper is applied to the use case of public transit route planning. It can be used in various other domains with continuously updating data, such as smart city dashboards, business intelligence, or sensor networks.
In the next section, we discuss related research on which our solution will be based. In Section 3, we present a motivating use case. Section 4 discusses different techniques to represent dynamic data, after which Section 5 gives an explanation of our proposed query solution. Next, Section 6 shows an overview of our experimental setup and its results. Finally, Section 7 discusses the conclusions of this work with further research opportunities. 2
In this section, we first explain techniques to perform rdf annotation, which will be used to determine freshness. Then, we zoom in on possible representations of temporal data in rdf. We finish by discussing existing sparql streaming extensions and a low-cost (static) Linked Data publication technique. 2.1
rdf Annotations Annotations allow us to attach metadata to triples. We might for example want to say that a triple is only valid between a certain time interval, or that a triple is only valid in a certain geographical area.
rdf 1.0 [
Singleton Properties [
With rdf 1.1 [
Regular rdf triples cannot express the time and space in which the fact they describe
is true. In domains where data needs to be represented for certain times or time ranges,
these traditional representations should thus be extended. Time labeling [
The authors introduced a temporal vocabulary [
Next to these properties, we will also introduce our own predicate tmp:expiration with range xsd:dateTime which indicates that the subject is only valid up until the given time.
Several sparql extensions exist that enable querying over data streams. These data
streams are traditionaly represented as a monotonically non-decreasing stream of triples
that are annotated with their timestamp. These require continuous processing [
c-sparql [
cqels [
Experiments have shown that more than half of public sparql endpoints have an
availability of less than 95% [
A guiding use case, based on public transport, will be referred to in the remainder of this paper. When public transport route planning applications return dynamic data, they can account for factors such as train delays as part of a continuously updating route plan. In this use case, different clients need to obtain all train departure information for a certain station. A static sparql query can be used to retrieve all information using this basic data model, which can be found in Listing 1.1, the first two triple patterns refer to triples that contain dynamic data.
SELECT ?delay ?platform ?headSign ?routeLabel ?departureTime WHERE { _:id t:delay ?delay. _:id t:platform ?platform. _:id t:departureTime ?departureTime. _:id t:headSign ?headSign. _:id t:routeLabel ?routeLabel.
FILTER (?departureTime > "2015-12-08T10:20:00"^^xsd:dateTime).
FILTER (?departureTime < "2015-12-08T11:20:00"^^xsd:dateTime). } Listing 1.1: The basic sparql query for retrieving all upcoming train departure information in a certain station. The two first triple patterns are dynamic, the last three are static. 4
Our solution consists of a partial redistribution of query evaluation workload from the server to the client, which requires the client to be able to access the server data. There needs to be a distinction between regular static data and continuously updating dynamic data in the server’s dataset. For this, we chose to define a certain temporal range in which these dynamic facts are valid, as a consequence the client will know when the data becomes invalid and has to fetch new data to remain up-to-date. To capture the temporal scope of data triples, we annotate this data with time. In this section, we discuss two different types of time labeling, and different methods to annotate this data.
We use interval-based labeling to indicate the start and endpoint of the period during which triples are valid. Point-based labeling is used to indicate the expiration time.
With expiration times, we only save the latest version of a given fact in a dataset, assuming that the old version can be removed when a newer one arrives. These expiration times provide enough information to determine when a certain fact becomes invalid in time. We use time intervals for storing multiple versions of the same fact, i.e., for maintaining a history of facts. These time intervals must indicate a start- and endtime for making it possible to distinguish between different versions of a certain fact. These intervals cannot overlap in time for the same facts. 4.2
The two time labeling types introduced in the last section can be annotated on triples in different ways. In Section 2.1 we discussed several methods for rdf annotation. We will apply time labels to triples using the singleton properties, graphs and implicit graphs annotation techniques.
Singleton Properties Singleton properties annotation is done by creating a singleton property for the predicate of each dynamic triple. Each of these singleton properties can then be annotated with its time annotation, being either a time interval or expiration times. Graphs To time-annotate triples using graphs, we can encapsulate triples inside contexts, and annotate each context graph with a time annotation.
Implicit Graphs A tpf interface gives a unique uri to each fragment corresponding
to a triple pattern, including patterns without variables, i.e., actual triples. Since Triple
Pattern Fragments [
We will execute our use case for each of these annotation methods. In practice, an annotation method must be chosen depending on the requirements and available technologies. Each has their own set of advantages and disadvantages, like for example required triple count. 5
Query Engine tpf query evaluation involves server and client software, because the client actively takes part in the query evaluation, as opposed to traditional sparql endpoints where the server does all of the work. Our solution allows users to send a normal sparql query to the local query engine which autonomously detects the dynamic parts of the query and continuously sends back results from that query to the user.
Our solution must be able to handle regular sparql 1.1 queries, detect the dynamic parts, and produce continuously updating results for non-high frequency queries. To achieve this, we built an extra software layer on top of the existing tpf client that supports each discussed labeling type and annotation method and is capable of doing dynamic query transformation and result streaming. We will refer to this layer as the query streamer. A simplified overview of this architecture can be seen in Figure 1. The rewriter module internally splits the query up in a static and dynamic query. This splitting is done by exchanging metadata with the endpoint using small queries. The dynamic query is formed in such a way that time annotations can be retrieved from its dynamic triples based on the selected annotation mechanism. The streamer module does the result streaming by determining the earliest expiration time of the dynamic triples for each resultset and re-executing the dynamic query based on that time. Once the dynamic query results are collected, these results are filled into the static query after which it can be executed. These dynamic and static results are then combined and sent back to the user. A client-side caching mechanism is applied in the streamer module to cache the static query results where possible. At the tpf server, dynamic data must be annotated with time depending on the used combination of labeling type and method. The server expects dynamic data to be pushed to the platform by an external process with varying data. For the case of graph-based annotation, we extended the tpf server implementation with quad support.
Server Client
TPF Interface
external
Query Streamer SPARQL query
User query results
Web split queries metadata
Basic Graph Iterator
queries Rewriter
Streamer We set up an experiment to measure the impact of our proposed redistribution of workload between the client and server by simultaneously executing a set of queries against a server using our proposed solution. We repeat this experiment for two state-of-the-art solutions: c-sparql and cqels.
To test the client and server performance, our experiment consisted of one server and ten physical clients. Each of these clients can execute from one to twenty unique concurrent queries based on the use case from Section 3. The data for this experiment was derived from real-world Belgian railway data using the iRail API1. This results in a series of 10 to 200 concurrent query executions. This setup was used to test the client and server performance of different sparql streaming approaches.
For comparing the efficiency of different time annotation methods and for measuring the effectiveness of our client-side cache, we measured the execution times of the query for our use case from Section 3. This measurement was done for different annotation methods, once with the cache and once without the cache. For discovering the evolution of the query evaluation efficiency through time, the measurements were done over each query stream iteration of the query.
The discussed architecture was implemented2 in JavaScript using Node.js to allow for easy communication with the existing tpf client.
The tests3 were executed on the Virtual Wall (generation 2) environment from
iMinds [
Server Cost The server performance results from our main experiment can be seen in Figure 2a. This plot shows a quickly increasing cpu usage for c-sparql and cqels for higher numbers of concurrent query executions. On the other hand, our solution never reaches more than one percent of server cpu usage.
Client Cost The results for the average cpu usage across the duration of the query evaluation of all clients that sent queries to the server in our main experiment can be seen in Figure 2b. The clients that were sending c-sparql and cqels queries to the server had a client cpu usage of nearly zero percent for the whole duration of the query evaluation. The clients using the client-side query streamer solution that was presented in this work had an initial cpu peak reaching about 80%, which dropped to about 5% after 4 seconds. Annotation Methods The execution times for the different annotation methods can be seen in Figure 3. The execution times for expiration time annotation used are approximately constant, while the execution times for time intervals significantly increase over time, for graph-based annotation this increase is not as fast as for the other two approaches. 1 https://hello.irail.be/api/1-0/ 2 The source code for this implementation is available at https://github.com/rubensworks/
TPFStreamingQueryExecutor 3 The code used to run these experiments with the relevant queries can be found at https: //github.com/rubensworks/TPFStreamingQueryExecutor-experiments/
In this paper, we researched a solution for querying over dynamic data with a low server cost, by continuously polling the data based on volatility information. In this section, we draw conclusions from our evaluation results with regard to server cost, client cost, performance, and annotation methods.
Server cost Not only is the server cost for our solution more than ten times lower on
average when compared to the alternatives, this cost also increases much slower for a
growing number of simultaneous clients. This makes our proposed solution more scalable
for the server for our tested use case.
Client cost The results for the client load measurements from Section 6 show that our
solution requires more client processing power than c-sparql and cqels The required
client processing power using our solution is clearly much higher than for c-sparql and
cqels. This is because we redistributed the required processing power from the server to
the client. In our solution, it is the client that has to do most of the work for evaluating
queries, which puts less load on the server. The load on the client still remains around 5%
for the largest part of the query evaluation as shown in Figure 2b. Only during the first few
seconds, the query engines cpu usage peaks, which is because of the processor-intensive
rewriting step that needs to be done once at the start of each dynamic query evaluation.
Performance Our solution significantly reduces the required server processing per client,
this complexity is mostly moved to the client. This comparison shows that our technique
allows data providers to offer dynamic data which can be used to continuously evaluate
dynamic queries with a low server cost. Our low-cost publication technique for dynamic
data is useful when the number of potential simultaneous clients is large. When this data
is only required for a small number of clients in a closed off environment and query
evaluation must happen fast, traditional approaches like cqels or c-sparql are advised.
These are only two possible points on the Linked Data Fragments axis [
In this work, the frequency at which our queries are updated is purely data-driven using time intervals or expiration times. In the future it might be interesting, to provide a control to the user to change this frequency, if for example this user only desires query updates at a much lower frequency than the data actually changes.
In future work, it is important to test this approach with a larger variety of use cases.
The time annotation mechanisms we use are generic enough to transform all static facts
to dynamic data for any number of triples. The CityBench [
The described research activities were funded by iMinds and Ghent University, the Institute for the Promotion of Innovation by Science and Technology in Flanders (IWT), the Fund for Scientific Research Flanders (FWO Flanders), and the European Union. Ruben Verborgh is a Postdoctoral Fellow of the Research Foundation Flanders.