Social semantic data are becoming a reality, but apparently their streaming nature has been ignored so far. Streams, being unbounded sequences of time-varying data elements, should not be treated as persistent data to be stored \forever" and queried on demand, but rather as transient data to be consumed on the y by queries which are registered once and for all and keep analyzing such streams, producing answers triggered by the streaming data and not by explicit invocation. In this paper, we propose an approach to continuous queries and realtime analysis of social semantic data with C-SPARQL, an extension of SPARQL for querying RDF streams.
\Which are the hottest topics under discussion on Twitter?" \Who is discussing about Italian food right now?" \What have my close friends been discussing in the last hour?" \Who is now discussing about Tuscany red wines in my social network?" \How many people have been twittering about northern Italy white wines in the last three hours?"
The information required to answer those queries is increasingly becoming
available on the Web. On the one side, we observe a trend in Web 2.0 as blogs,
feeds and microblogs are adopted to disseminate and publish information in
real-time streams trough social networking Web sites. This trend is often
referred to as the Twitter phenomenon or, in more broader terms, as the so-called
blogosphere. On the other side, a trend can be also observed towards the
interlinking of Social Web with semantics [
2 http://xmlns.com/foaf/spec/ 3 www.w3.org/2004/02/skos/
As concrete examples, we can refer to three pioneers in this eld
{ SMOB [
Several attempts to provide answers to those questions exist both by employing Information Retrieval (IR) methods (e.g., technorati.com, icerocket.com, blogsearchengine.com, blogsearch.google.com) and Semantic Web methods (e.g., the SIOC API of sindice.com, SMOB aggregator and Smesher). Our claim is that answering such questions in the space of one-time semantics of current IR and Semantic Web tools is di cult because the underlying data are streams.
Data streams are unbounded sequences of time-varying data elements. They
have been recognized in a variety of modern applications, such as network
monitoring, tra c engineering, sensor networks, RFID tag applications, telecom call
records and nancial applications. Processing of data streams has been largely
investigated in the last decade [
DSMS represent a paradigm change in the database world as they move from persistent relations and user-invoked queries to transient streams and continuous queries. The innovative assumption is that streams can be consumed on the y rather than being stored forever and that queries which are persistently monitoring streams are able to produce their answers even in the absence of invocation. DSMS can support parallel query answering over data originating in real-time and can cope with bursts of data by adapting their behavior to gracefully degrade answer accuracy by introducing higher levels of approximation. However, even if such DSMS systems proved to be an optimal solution for on the y analysis of data streams, they cannot perform complex reasoning tasks, such as the ones required for computing the answers to the above questions.
At the same time, while Semantic Web reasoners are year after year scaling up in the classical, time invariant domain of RDF triples and ontological knowledge, reasoning upon rapidly changing information has been neglected or forgotten so far. Reasoning systems assume static knowledge, and do not manage \changing worlds"|at most, one can update the ontological knowledge and then repeat the reasoning tasks.
In [
integrate data streams and reasoning systems, thus giving answer to the above and other questions from di erent domains.
The rest of the paper is organized as follows. In Section 2, we provide the background needed to understand the proposed extensions to RDF and SPARQL introduced in Sections 3.1 and 3.3, respectively. In Section 4, we describe an architecture and implementation of a C-SPARQL engine. Section 5 is dedicated to the comparison of C-SPARQL to SPARQL using the real-world social data streams described in Section 3.2. We close the paper by discussing related work in Section 6 and draw conclusions in Section 7. 2
2.1
Data Streams This section illustrates previous work on data streams and the SPARQL language.
DSMS are based on the observation that not only is it impossible to control the
order in which data items arrive in a stream, but, even more importantly, it is
not feasible to locally store a stream in its entirety [
The Chronicle data model [
The rst query language tailored to data streams, CQL [
More recently, Law et al. [
SPARQL
SPARQL has been developed under the patronage of the W3C as the standard
query language for RDF. Therefore, the most authoritative source on its syntax
and semantics is the W3C recommendation [
With the goal of proposing a syntactic and semantic extension to SPARQL, we found the following works particularly useful.
{ Gutierrez et al. [
Data models and query languages for DSMS are not su cient for continuously querying and analyzing in real-time streams of RDF. Indeed, we deem that there is a potential interest for giving up one-time semantics in RDF repositories as well, so as to explore the bene ts provided by continuous semantics. Therefore, we introduce RDF streams as the natural extension of the RDF data model to the new continuous scenario and Continuous SPARQL (or simply C-SPARQL) as the extension of SPARQL for querying RDF streams. 3.1
RDF Streams An RDF stream is de ned as an ordered sequence of pairs, where each pair is constituted by an RDF triple and its timestamp .
. . .
(hsubji; predi; objii , i) (hsubji+1; predi+1; obji+1i , i+1)
. . .
Timestamps can be considered the context of RDF triples. They are monotonically non-decreasing in the stream ( i i+1). They are not strictly increasing because timestamps are not required to be unique. Any (unbounded, though nite) number of consecutive triples can have the same timestamp, meaning that they occur at the same time, although sequenced in the stream according to some positional order. Our de nition of RDF streams extends RDF in the same way as the stream type in CQL extends the relation type.
Named graphs [
A Real Source of Social Semantic Data Streams
Given that RDF streams of social semantic data are not readily available yet, we
decided to use the data provided by Social Network Glue5. Glue enables users to
connect with their friends on the Web based on the pages the users visit online.
Using semantic recognition technologies to automatically identify books, music,
movies, wines, stocks, movie stars and many other similar topics, it generates a
continuous stream of the identi ed objects which is accessible in real time
using a REST API6. The REST request \http://api.getglue.com/v1/glue/recent"
returns the 250 most recent public interactions. We adopted the GRDDL
approach [
Subject Predicate Object Timestamp glueinter:i1 rdf:type sioc:Post \2009-07-20T22:48:52Z" glueinter:i1 sioc:content \The Proposal on imdb.com" \2009-07-20T22:48:52Z" glueinter:i1 sioc:has container http://www.getglue.com \2009-07-20T22:48:52Z" glueinter:i1 dc:title \The Proposal" \2009-07-20T22:48:52Z" glueuser:id1 rdf:type sioc:User \2009-07-20T22:48:52Z" glueinter:i1 sioc:has creator glueuser:id1 \2009-07-20T22:48:52Z" glueinter:i1 sioc:topic gluecat:movies \2009-07-20T22:48:52Z" glueinter:i2 rdf:type sioc:Post \2009-07-20T22:48:54Z" glueinter:i2 sioc:content \Mario Kart Wii on gamefaqs.com" \2009-07-20T22:48:55Z" glueinter:i2 sioc:has container http://www.getglue.com \2009-07-20T22:48:55Z" glueinter:i2 dc:title \Mario Kart Wii" \2009-07-20T22:48:55Z" glueuser:id2 rdf:type sioc:User \2009-07-20T22:48:55Z" glueinter:i2 sioc:has creator glueuser:id2 \2009-07-20T22:48:55Z" glueinter:i2 sioc:topic glueint:video games \2009-07-20T22:48:55Z" Similarly to SemanticTweet, we are also able to translate the social relationships obtained using the REST service \/user/friends" into FOAF. 3.3
Continuous SPARQL
C-SPARQL is an extension of SPARQL for querying both RDF graphs and
RDF streams. The complete de nition of the language in terms of syntax and
semantics is given in [
Continuous Queries The distinguishing feature of C-SPARQL is the support for continuous queries, i.e. queries that are registered and then executed continuously over windows opened on RDF streams and standard RDF graphs. Continuous queries, which make usage of aggregates, are particularly relevant.
A C-SPARQL query is registered using the grammar extension provided by the rst of the following two production rules.
6 http://getglue.com/api Registration ! `REGISTER QUERY' QueryName `AS' Query Registration ! `REGISTER STREAM' QueryName `AS' Query
As output C-SPARQL queries produce the same types as SPARQL queries: boolean answers, selections of variable bindings, RDF descriptions of the involved resources or constructions of new RDF triples. These outputs are continuously renewed in each query execution. In addition, C-SPARQL queries can be registered to produce new RDF streams using the grammar extension provided by the second production rule given above. In this second case, only CONSTRUCT and DESCRIBE queries can be registered, as they produce RDF triples that, once associated with a timestamp, yield RDF streams that can be managed in CSPARQL.
Windows Given that RDF streams are intrinsically in nite, we introduce the
notion of windows upon RDF streams, whose types and characteristics are
inspired by those of the windows in continuous query languages such as CQL [
FromStrClause ! `FROM' [`NAMED'] `STREAM' StreamIRI `[ RANGE' Window `]'
From the RDF stream identi ed by StreamIRI, a window extracts the last triples, which are considered by the query. The extraction can be physical (a given number of triples) or logical (a variable number of triples which occur during a given time interval).
The part of C-SPARQL that we introduced so far is su cient to address the question \What have my closest friends been visiting in the last hour?" Below, we show how to formulate this query in C-SPARQL over the Glue interaction stream and the graph of FOAF relationships described in Section 3.2.
REGISTER QUERY WhatHaveMyCloseFriendsBeenVisitingInTheLastHour AS PREFIX sioc: <http://rdfs.org/sioc/ns#> PREFIX foaf: <http://xmlns.com/foaf/0.1/> PREFIX glue: <http://c-sparql.cefriel.it/sdow-demo/> SELECT DISTINCT ?friend ?topic FROM <http://c-sparql.cefriel.it/sdow-demo/glueusers.rdf> FROM STREAM <http://c-sparql.cefriel.it/sdow-demo/interactions.trdf> [ RANGE 60m STEP 5m ] WHERE { glue:id1 foaf:knows ?friend .
?post sioc:has_creator ?friend . ?post rdf:type sioc:Post .
?post sioc:topic ?topic . }
The rst triple pattern matches triples in the FOAF graph, whereas the other three triple patterns match triples in a sliding window of 60 minutes opened on the RDF stream, which advances progressively in steps of 5 minutes. Aggregation Another question that we could answer using a C-SPARQL is \Which are the top topics in Glue?" To do so, we also need to introduce the aggregation capabilities that we added to C-SPARQL. We allow multiple independent aggregations within the same C-SPARQL query, thus pushing the aggregation capabilities beyond those of SQL and other proposals for aggregation in SPARQL7. Aggregation clauses have the following syntax. AggregateClause ! ( `AGGREGATE { (' var `,' Fun `,' Group `)' [Filter] `}' )* Fun ! `COUNT' j `SUM' j `AVG' j `MIN' j `MAX' Group ! var j `{' var ( `,' var )* `}'
An aggregation clause starts with a new variable not occurring in the WHERE clause, followed by an aggregation function and closed by a set of one or more variables, occurring in the WHERE clause, which express the grouping criteria. For instance, the query above can be expressed in C-SPARQL as follows.
REGISTER QUERY TopTopicsGlueUsersAreInterestedIn AS PREFIX sioc: <http://rdfs.org/sioc/ns#> SELECT DISTINCT ?topic ?number FROM STREAM <http://c-sparql.cefriel.it/sdow-demo/glueinteractions.trdf> [ RANGE 30m STEP 10m ] WHERE { ?post sioc:topic ?topic . }
AGGREGATE {(?number , COUNT , {?topic })} 4
The C-SPARQL engine was designed based on a separation of concerns between stream management and query evaluation. This separation is the foundation for a simple architecture for C-SPARQL, built upon known database and reasoning technolgies. Figure 1 shows the three main components of our C-SPARQL execution framework.
The module named C-SPARQL Query Parser gets a C-SPARQL query as input and produces the information needed by the Data Stream Manager Layer and the SPARQL EndPoint Layer to execute the query. The data stream manager registers the data streams speci ed in the query and applies logical or physical windows. When the resulting graph has been produced, the SPARQL part of the C-SPARQL query is executed by the SPARQL endpoint. This process is executed as frequently as speci ed in the REGISTER clause of the C-SPARQL query. Finally, the result computed is timestamped and passed on. Both the data stream manager and the SPARQL endpoint are considered plugins, in order to be independent from the actual DSMS/SPARQL engine implementations that will be used. We have implemented a prototype based on this architecture using ESPER as a DSMS and Jena as a SPARQL endpoint.
ESPER8 is a component for stream processing applications, which require high throughput to process large volumes of data elements (between 1,000 to 100k messages per second) and low latency to react in real-time (from a few
C-SPARQL
Query Parser Continuous part
REGISTER FROM STREAM Data Stream Manager Layer
Standard SPARQL Query
SPARQL
EndPoint Layer milliseconds to a few seconds). In particular, it supports the various forms of windows we de ned in C-SPARQL (i.e., sliding and tumbling windows both in terms of time and length) and several forms of aggregation we plan to exploit for optimizations based on query rewriting.
Jena9 is a Java framework for building Semantic Web applications. We choose it, because it includes a custom RDF storage engine for high performance applications and a SPARQL query engine. The SPARQL engine supports standard SPARQL and aggregation, GROUP BY and assignment as SPARQL extensions.
The adoption of o -the-shelf stream management systems and reasoning tools both provide a solid framework and a fast way of prototyping. 5
In order to evaluate, our approach we compared the time required to compute a C-SPARQL query with our engine, to the time needed to execute an equivalent SPARQL query in Jena using its SPARQL engine over its custom RDF storage engine. The tests have been run on a Pentium Core 2 Quad 2.0GHz with 2GB of main memory.
As representative C-SPARQL query we chose the following one, in which we count how many Glue users are interested in the various topics recognized by Glue in the last 3 minutes.
REGISTER QUERY CountHowManyGlueUsersAreInterestedInEachTopic AS PREFIX sioc: <http://rdfs.org/sioc/ns#> SELECT DISTINCT ?topic ?number FROM STREAM <http://c-sparql.cefriel.it/sdow-demo/interactions.trdf> [ RANGE 3m STEP 10s ] WHERE { ?post sioc:topic ?topic . } AGGREGATE {(?number , COUNT , {?topic })}
This simple query showcases all characteristics of C-SPARQL, namely, registration, selection of triples based on a window over a RDF stream and an aggregate function.
We registered this C-SPARQL query in our engine and continuously executed it every second. We run two experiments feeding new triples from the RDF stream into the C-SPARQL engine at two di erent rates: 5 triples per second (5 t/s) and 200 t/s. In both experiments, we measured the time required to compute the answer with the triples in the window.
It is possible to write a SPARQL query, which computes the same results as the C-SPARQL query above, by adding (a) a triple pattern that matches the creation date of the post, (b) a FILTER clause that selects the same time interval of the C-SPARQL query, and (c) an aggregate function that counts the number of topics using Jena SPARQL extensions for aggregates.
PREFIX sioc: <http://rdfs.org/sioc/ns#> PREFIX dcterms: <http://purl.org/dc/terms/> PREFIX xsd: <http://www.w3.org/2001/XMLSchema#> SELECT ?topic count(?topic) WHERE { ?post sioc:topic ?topic .
?post dcterms:created ?date .
FILTER (?date > ‘‘2009-07-20T22:47:00Z’’ˆˆxsd:dateTime
&& ?date < ‘‘2009-07-20T22:50:00Z’’ˆˆxsd:dateTime ) } GROUP BY ?topic
Using Jena, we executed the above SPARQL query six times against repositories containing the rst 100, 500, 1000, 1500, 2000 and 2500 triples, respectively. In these experiments, we again measured the time required to compute each answer.
The results are shown in Figure 2 and are named SPARQL. Comparing the linear regressions of the three experiments, named Linear(SPARQL), Linear(CSPARQL 5 t/s) and Linear(C-SPARQL 200 t/s), we see that the C-SPARQL window based selection always performs signi cantly better than the FILTER based selection of SPARQL in Jena. Notably, this result holds both for a low triple per second rate of 5 t/s and a reasonably high rate of 200 t/s. 6
A previous e ort to combine SPARQL and data streams is presented in Bolles
et al. [
Our approach is di erent from their in several key aspects. First, Bolles et al. omit essential ingredients such as aggregate functions, thus the resulting expressive power is not su cient to express interesting practical queries such as \Which are the top topics under discussion?". Second, the authors do not follow the approach, established by DSMS, to only use windows to transform streaming data into non-streaming data in order to apply standard algebraic operations. Bolles et al. choose to also change the standard SPARQL operators by making them timestamp-aware and, thereby, e ectively introduce a new language semantics. Finally, their approach allows window clauses to appear within SPARQL
Response Time C-SPARQL vs. SPARQL 40 30 s m20 10 0 0
500 1000 1500 2000 number of triples in the window (C-SPARQL) or in the repository (SPARQL) 2500 SPARQL Linear (SPARQL)
C-SPARQL 5 t/2 Linear (C-SPARQL 5 t/2)
C-SPARQL 200 t/s Linear (C-SPARQL 200 t/s) group graph pattern expressions. This makes the query syntax more intricate and it complicates query evaluation. Moreover, it violates the separation of concerns between stream management and query evaluation that is the basis of our simple architecture for C-SPARQL engines. 7
We began this paper with a list of questions related to social data on the Web that stress the streaming nature of blogs and microblogs. Our initial claim was that social data should not be treated as persistent data to be stored forever and queried on demand, but rather as transient data to be consumed on the y by registered queries. In order to prove this claim, we have made the following arguments in this paper.
{ RDF streams can be de ned by extending RDF data type with a notion of timestamp; { RDF streams can be serialized as N-Quads; { sources of RDF streams are available and can be obtained from blogs and microblogs with the same approach used to obtain the RDF representations used for social semantic data; { SPARQL can be extended with the notion of continuous query registered once and for all that keep monitoring such RDF streams, producing answers triggered by the streaming data and not by explicit invocation; { C-SPARQL queries can be evaluated using a simple architecture based on the decision to keep stream management and query evaluation separated; and { in terms of response time, even in a naive implementation of this architecture the window based selection of C-SPARQL outperforms the FILTER based selection needed to formulate the equivalent query in SPARQL.
Moreover, we do not exploit several optimization opportunities. On the one hand, we can adopt smarter query rewriting techniques that push part of a C-SPARQL query evaluation from the SPARQL engine to the DSMS. On the other hand, we are not considering the parallel nature of streams and thus the opportunity for parallel continuous query processing.
Finally, we have been limiting ourselves to treat RDF as relational data
without considering it part of the Semantic Web stack. We are currently investigating
techniques [
Acknowledgements The work described in this paper has been partially supported by the European project LarKC (FP7-215535). Michael Grossniklaus's work is carried out under SNF grant number PBEZ2-121230.