The increasing popularity of RDF Stream Processing has led to the developments of several RSP engines. Among these, CQELS has been developed with a native and adaptive approach, which gives it a performance advantage over other engines. However, it currently does not support two important features, namely Complex Event Processing and RDFS reasoning. We propose in this paper an extension of the CQELS query language and semantics towards enriching CQELS with these attractive functionalities.
Following the trend of using RDF as a uni ed data model for integrating diverse web data sources across systems under di erent controls, RDF Stream Processing (RSP) extends RDF to addresses the challenges in querying heterogeneous data streams coming from dynamic data sources of emerging ICT systems such as IoT and Smart Cities. This research eld has being increasingly getting more attention with the developments of several RSP engines such as C-SPARQL [5], CQELS [17], EP-SPARQL [3], SPARQLStream [7], and Sparkwave [13] which mainly aim at providing stream processing functionalities.
Among these engines, CQELS engine was designed to achieve the strict performance requirements of stream processing engines [20] with native physical query operators. The current implementation of CQELS engine provides high throughput physical operators to cover the combination of CQL operators and SPARQL 1.1 with CQELS query language (CQELS-QL). It has been shown to have a performance advantage over other RSP engines [18].
However, CQELS currently does not support two important features, namely Complex Event Processing (CEP) and RDFS reasoning. The former play an important role in handling and analyzing complex relation over high volume of dynamic data [1], while the latter allows reasoning about types and brings additional expressiveness for RSP. Having them in CQELS will enable a new range of `2
Gulda Lane (g)
Haydn Park. (h) Mozart C. (m) `1
Beethoven St. (b)
Center Sq. (c) `3 a1,delay,m d1,delay,h d1,delay,h
a1,delay,m 10 12 14 16 applications that require not only high performance but also high expressiveness, for example, as in the motivating scenario below.
Towards a more powerful CQELS, in this paper, we enrich the current query language of CQELS to support the desired features. Our contributions are: { extending the RDF stream processing model to work on time intervals instead of time points; { proposing an extension of the CQELS-QL to handle navigational paths and complex event processing. For the former, we make use of nSPARQL [16] and SPARQL 1.1 property paths; for the latter, we start the sequence operator SEQ, which is the most popular CEP operator in practice; { giving a semantics of the new language in the SPARQL style, by lifting the join and sequence-related operators to work on sets of mappings with intervals, and introducing evaluation functions that make use of these operators. The proposed new language features and semantics will be illustrated with the following scenario.
Motivating Scenario. Suppose that the tra c center at city of Vienna wants to improve the quality of public transportation by means of smart services. For this purpose, the center has background datasets regarding available vehicles such as subways, trams, buses, and connections between every pair of consecutive stops, including the stop names, types of vehicles and the duration of time needed to travel between them. Moreover, the center receives sensor data reporting the arrival and delay of vehicles with respect to stops. Passengers who register to the smart service also provide their locations as input streams.
On top of these background and streaming data, the center can o er smart services (i) to aid tra c o cers in monitoring and quickly identifying potential problems in the transportation network or (ii) to notify passengers of potential tra c delays and recommend alternative routes.
Example 1 To make sure smooth connections to the city center, a continuous query can be placed to notify about recent repeated delays of subways following by no arrival at stops that according to the network plan can be reached by subways. When such information is instantly available to an o cer, he/she can immediately react by triggering rerouting or providing complementary vehicles to solve the tra c.
Take a simpli ed public transportation map in Figure 1 where `1 and `2 are subway lines, and `3 is a tram line. Assume that delays and arrivals of vehicles wrt. stops are reported along the time lines. At time point 14, a repeated delay for the subway d1 on the way to h is detected, but this is not reported as getting from h to c needs to use the tram line `3. At time point 16, the repeated delay for the subway a1 at m is however reported as one can get from m to c by subways. 2
This section brie y reviews the basic building blocks of this work, namely RDF, SPARQL, RDF stream processing, the navigation language nSPARQL, and CEP. 2.1
RDF and SPARQL RDF is a W3C recommendation for data interchange on the Web [8]. It models data as directed labeled graphs whose nodes are resources and edges represent relations among them. Each node can be a named resource (identi ed by an IRI), an anonymous resource (a blank node), or a literal. We denote by I, B, L the sets of IRIs, blank nodes, and literals, respectively. Let IB = I [ B, IBL = I [ B [ L.
A triple (s; p; o) 2 IB I IBL) is an RDF triple, where s is the subject, p the predicate, and o the object. An RDF graph is a set of RDF triples. Example 2 (cont'd) The background dataset in Example 1 can be represented by the following RDF graph: D= 8 :conn1 :beg :m; :conn1 :end :b; :conn1 :means :subway; :conn1 :dur :3m; 9 > > >>> :conn2 :beg :b; :conn2 :end :c; :conn2 :means :subway; :conn2 :dur :2m; >>> > > >>> :conn3 :beg :h; :conn3 :end :g; :conn3 :means :subway; :conn3 :dur :3m; >>> > > ><> :conn4 :beg :g; :conn4 :end :c; :conn4 :means :tram; :conn4 :dur :5m; >=> .
>>>>>>>>:>>> :a1 rdf:type :subway; :d1..... rdf:type :subway; >>>>>>>>>>;> A triple pattern is a tuple (sp; pp; op) 2 (IB [ V ) (I [ V ) (IBL [ V ), where V is a set of variables. A basic graph pattern is a set of triple patterns.
SPARQL [12], a W3C recommendation for querying RDF graphs, is essentially a graph-matching query language. A SPARQL query is of the form H B, where B, the body of the query, is a complex RDF graph pattern composed of basic graph patterns with di erent algebraic operators such as UNION, OPTIONAL, etc.; and H, the head of the query, is an expression that indicates how to construct the answer to the query [15].
The semantics of SPARQL is de ned via mappings. A mapping is a partial function : V ! IBL. The result of a SELECT SPARQL query is a set of mappings that match the query's body, projected to the variables speci ed in the SELECT clause. However, one-shot queries by themselves are not able to give answers under dynamic input as in the running scenario. For this purpose, we need RDF stream processing. 2.2
RDF Stream Processing RDF Streams and Temporal RDF Graphs. In continuous query processing over dynamic data, the temporal nature of the data is crucial and needs to be captured in the data representation. This applies to both Linked Stream Data and Linked Data, as updates in Linked Data collections are also possible. In [17], RDF streams and instantaneous RDF datasets were de ned by introducing timestamps (time points) to input triples of the former and RDF graphs of the latter. In this paper, we adapt these notions by using time intervals as timestamps. Thereby, 1. An RDF graph at timestamp t, denoted by G(t), is a set of RDF triples valid at time t and called an instantaneous RDF graph. A temporal RDF graph is a sequence G = [G(t)]; t 2 N, ordered by t. 2. An RDF stream S is a sequence of elements hg : [t1; t2]i, where g is an RDF graph and [t1; t2] is a time interval.
Example 3 (cont'd) The sensor data regarding delay and arrival of vehicles as in Figure 1 can be represented as the following RDF stream.3 S = hf(a1; delay; m)g; [10; 10]i; hf(d1; delay; h)g; [12; 12]i; hf(d1; delay; h)g; [14; 14]i; hf(a1; delay; m)g; [16; 16]i; : : : Continuous Queries. Queries in CQELS are inspired by the Continuous Query Language (CQL) [4], where a continuous query is composed from three classes of operators, namely stream-to-relation (S2R), relation-to-relation (R2R), and relation-to-stream (R2S) operators. In CQELS, the former are captured by extending SPARQL 1.1 grammar4 with a \stream graph" pattern, while the latter are taken care of by SPARQL's operators. For more details on the query syntax, we refer the reader to [17].
Example 4 (cont'd) The following continuous query in the CQELS-QL noties stops with delays of subways during the last 10 minutes to users: 1 SELECT ? s 2 FROM ex : t r a n s p o r t a t i o n M a p 3 FROM NAMED WINDOW : W ON ex : p u b l i c T r a n s p o r t [ RANGE 10 m ] 4 WHERE { 5 WINDOW : W { ? v : delayAt ? s } 6 ? v rdf : type : subway . 7 } 3 Note that the noti cation of delay or arrival here is considered atomic event; therefore, the time intervals associated with this data is of the form [t; t]. On the other hand, the output of a CQELS query containing non-atomic events (cf. Example 9) can be fed as input stream to another query. In such situation, input events are associated with time interval [t1; t2] with t1 t2. 4 http://www.w3.org/TR/sparql11-query/#grammar [[self :: a]]G = f(a; a)g [[next :: a]]G = f(x; y) j 9z : (x; z; y) 2 Gg [[axis 1 :: a]]G = f(x; y) j (y; x) 2 [[axis :: a]]Gg, where axis 2 fnext; node; edgeg . .
. For a data model with graph structure like RDF, being able to navigate through the graphs is fundamentally important. In [16], the authors proposed nSPARQL, a language that incorporates navigational capabilities to a fragment of SPARQL using nested regular expressions. nSPARQL allows to pose interesting and natural queries over RDF data, and has an attractive computational property that nested regular expressions can be e ciently evaluated in polynomial time.
The new SPARQL 1.1 query language introduced property paths5 that covers a fragment of nSPARQL without nesting. In this paper, we augment CQELS-QL with the full functionalities of nSPARQL based on the syntax of SPARQL 1.1. We now brie y recall nSPARQL, the following grammar de nes the syntax of nested regular expressions: exp ::= axis j axis :: a(a 2 IBL) j axis :: [exp] j exp=exp j expjexp j exp j exp+; where axis 2 fself; next; next 1; edge; edge 1; node; node 1g. The evaluation of a nested regular expression exp in a graph G is formally de ned as a binary relation [[exp]]G, denoting the pairs of nodes (x; y) such that y is reachable from x in G by following a path that conforms to exp. Table 1 partly shows the formal semantics of nSPARQL on constructs that are used in our running example. For the full semantics, we refer the reader to [16].
Example 5 (cont'd) To nd all stops from which one can reach the city center by subway connections, we can use the following expression:
?s (next 1::beg[next::means/self::subway]/next::end)+ :c: Based on nSPARQL, we de ne an extended triple pattern as either a triple pattern or a triple (sp; exp; op), where sp; op 2 I [ L [ V and exp is a nested regular expression. An extended graph pattern P is a set of extended triple patterns. 2.4
Complex Event Processing Complex Event Processing [14] emerged from publish-subscribe systems [19]. While the latter refer only to single isolated events, CEP aims at timely detecting 5 http://www.w3.org/TR/sparql11-query/#propertypaths high-level events as complex patterns of incoming single atomic events whose order is crucial. The de ned complex events can in turn be used to compose even more complex events and so forth.
To express ordering between events, CEP languages assign time intervals as timestamps for events and make use of operators rooted from Allen's interval algebra [2]. In this paper, we take the rst step to incorporate CEP into CQELS-QL by adopting the sequencing operator SEQ from the SASE system [21] and applies it to time intervals. The version of SEQ with time points in SASE can be brie y described as follows.
Let Ai be an event type. Its semantics represented as Ai(t), is that at a given point t in time, Ai(t) is True if an Ai type event occurs at t, and is False otherwise. The SEQ operator takes a list of n > 1 event types as its parameters, e.g., SEQ(A1; : : : ; An) and speci es a particular order in which the events of interest should occur. Formally speaking:
SEQ(A1; : : : ; An)
9 t1 < t2 < : : : < tn : A1(t1) ^ A2(t2) ^ : : : ^ An(tn): When an event type is negatively speci ed in the sequence, that is:
SEQ(A1; : : : ; Ai 1; !Ai; Ai+1; : : : ; An); this corresponds to the SEQ WITHOUT operator (abbreviated as SEQ WO in this paper), which intuitively detects sequences of events of types A1; : : : ; Ai 1; Ai+1; : : : ; An where no event of type Ai occurs in between two events of types Ai 1 and Ai+1. Formally: SEQ(A1; : : : ; Ai 1; !Ai; Ai+1; : : : ; An) 9t1< : : : <ti 1<ti+1< : : : <tn : A1(t1)^ : : : ^Ai 1(ti 1)^Ai+1(ti+1)^ : : : ^An(tn) ^ (8ti 2 (ti 1; ti+1) : :Ai(ti)): In this paper, we extend the SEQ operator to work with time intervals and RDF triple patterns, as shown next. 3
This section proposes the rst step to extend CQELS with CEP and navigational capabilities by augmenting its syntax and semantics with the sequence operator SEQ and nested regular expressions from nSPARQL. 3.1
Extending CQELS Query Language Let TrTemp be the short-cut for the TriplesTemplate pattern in SPARQL 1.1. The syntax for triple sequence patterns TSP , window speci cations WinSpec, TSP ::= TrTemp
EC ::= WName and event clauses EC is de ned by the following grammar: j SEQ `(' TrTemp (`; ' TrTemp) (`; !' TrTemp) (`; ' TrTemp) `)' j SEQ `(' (`; ' TrTemp) (`; !' TrTemp) (`; ' TrTemp) TrTemp `)' WinSpec ::= `WINDOW ' : WName ON VarOrIRIref `['Window `]' `f' TSP `g' j SEQ `(' WName (`; ' WName) (`; !'WName)? (`; ' WName) `)' j SEQ `(' (WName `; ') (`!'WName `; ')? (WName `; ') WName `)' To add the navigational capabilities as in nSPARQL to the CQELS-QL, we extend the grammar of the SPARQL 1.1 property paths with one more case for nested path, namely elt ::= elt [elt ], where elt is a path element. We call the new query language CQELS-CEP.
Example 6 (cont'd) The following continuous query in CQELS-CEP identify stops (i) from which one can travel to the city center by subways, and (ii) report repeated delays of a subway during the last 10 minutes. 1 SELECT ?s 2 FROM ex : transportationMap 3 FROM NAMED WINDOW :W ON ex : publicTransport [ RANGE 10 m] 4 WHERE { 5 WINDOW :W { 6 SEQ ({? v : delayAt ?s}, {? v : delayAt ?s}, !{? v : arriveAt ?s }) 7 } 8 ?v rdf : type : subway . 9 ?s (^: beg /[: means : subway ]/: end )+ :c. 10 }
Line 6 uses operator SEQ to specify an event pattern in which two delays of the same vehicle ?v wrt. a stop ?s was reported following by no arrival of ?v at ?s. Line 9 is the expression in Example 5 in SPARQL 1.1 syntax extended with nested regular expression described above. 3.2
Modeling This section presents a formal model for the syntax proposed in Section 3.1. Let P1; : : : ; P` be basic graph patterns. A triple sequence pattern TSP is either a graph pattern Pj or a sequence of graph patterns having at most one element negated by `!', i.e., TSP = SEQ(P1; : : :; Pi 1; !Pi; Pi+1; : : :; P`).
A window speci cation is a tuple W = (s; !; TSP ) where s is an IRI identifying an input stream Ss, ! is a window expression, and TSP is a triple sequence pattern. Intuitively, ! speci es how a snapshot of recent input is extracted from the (potentially in nite) stream s. However, unlike traditional stream processing approaches that drop temporal information after the application of windows, this information is kept in our setting. The pattern TSP is then carried out based on the temporal information of valid triples according to the window applications. Given a window speci cation W , its negated version is denoted by !W .
An event clause EC is either a window speci cation W or a sequence of them having at most one element negated by `!', i.e., of the form
EC = SEQ(W1; : : : ; Wi 1; !Wi; Wi+1; : : : ; Wn): In [9], the authors model an RSP query as a tuple Q = (V; P; D; S) where V is a result form, P is a graph pattern, D is a static background dataset, and S is a set of input stream schemas. Under the extension of CQELS queries with triple sequence patterns, window speci cations, and event clauses, we extend this idea and model CQELS queries with CEP and navigation path as tuples of the form Q = (V; P; D; EC), where V is a result form, P is an extended graph pattern (RDF graphs with nested regular expressions, cf. Section 2.3), D is a set of instantaneous RDF datasets, and EC is a set of event clauses. To concentrate on the main contribution of this work on CEP and navigation features, we assume that the size of D is 1 and write D to refer to the single element of D. Example 7 (cont'd) The query in Ex. 6 can be modeled as Q = (V; P; D; EC), where { V = f?sg, { D = ex:transportationMap, { P = f?v rdf:type :subway. ?s (^:beg/[:means :subway]/:end)+ :c.g, { EC = f(ex:publicTransport; [RANGE 10m]; SEQ(P1; P1; !P2))g, where P1 = f?v :delayAt ?sg and P2 = f?v :arriveAt ?sg. 4
We now give a semantics in the SPARQL style [15] for the proposed language. Section 4.1 adapts the notion of window functions to work on input streams whose elements are associated with time intervals. In Section 4.2 we associate time intervals with SPARQL's traditional mappings, thus work on sets of mappings with intervals. We extend the join, union operators in [15] and introduce sequence-related operators to work on this input. Based on these basic operators, Section 4.3 de nes an evaluation function that captures the semantics of the proposed language. 4.1
Window Functions A window function w takes as input an RDF stream S, time point t, a collection of parameters for type , and returns a sub-bag of S. For example, for time-based the window function with sliding size 1, the parameter is a range T of how far the window looks back in time to collect valid input. It can be formally stated as follows.
wRANGE (S; t; T ) = fhg; [t01; t02]i j hg; [t1; t2]i 2 S^
T ) ^ t02 = min(t2; t)g: Each window expression then corresponds to a window function with its parameters fully speci ed. Let ! be a window expression, we denote by wtype(!) the window type and by wparams(!) the parameters of the corresponding window function. For example, with ! = [RANGE 10m], we have that wtype(!) = RANGE and wparams(!) = 10m. 4.2
Operators on Mappings with Intervals
A mapping with interval is a pair h ; [t1; t2]i where is a mapping and [t1; t2]
is a time interval satisfying that t1 t2. Note that two mappings are called
compatible, denoted by 1 = 2 i 8x 2 dom(
Let 1; 2; 3 be sets of mappings with intervals. We de ne the following operators on these sets:
JOIN( 1; 2) = fh 1 [ 2; [max(t1; t3); min(t2; t4)]i j h 1; [t1; t2]i 2
1 ^ h 2; [t3; t4]i 2 2^ 1 = 2 ^ max(t1; t3) min(t2; t4)g OR( 1; 2) = fh ; [t1; t2]i j h ; [t1; t2]i 2 1 _ h ; [t1; t2]i 2 2g SEQ( 1; 2) = fh 1 [ 2; [t1; t4]i j h 1; [t1; t2]i2 1 ^ h 2; [t3; t4]i2 2 ^ 1 = 2 ^ t2 < t3g SEQ WO( 1; 2; 3) = fh 1 [ 2; [t1; t6]i j h 1; [t1; t2]i 2 1 ^ h 3; [t5; t6]i 2 3 ^ 1 = 2 ^ t2 < t5^ (@h 2; [t3; t4]i 2 2 : 2 = 1 [ 3 ^ [t3; t4] [t2; t5])g NO HEAD( 1; 2) = fh 2; [t3; t4]i2 2 j @h 1; [t1; t2]i2 1 : 1 = 2 ^ t2 < t3g NO TAIL( 1; 2; t) = fh 1; [t1; t2]i2 1 j @h 2; [t3; t4]i2 2 : 1 = 2 ^ t2<t3 ^ t4 tg JOIN and OR are natural extensions of the AND and OR operators in the [15] with time intervals. Note that we use the name JOIN instead of AND in order not to be confused with operator AND in ETALIS [3] where it means taking the smallest interval that covers both [t1; t2] and [t3; t4], i.e., [min(t1; t2); max(t3; t4)]. We, on the other hand, take the \intersection" of [t1; t2] and [t3; t4].
Operator SEQ will be use to combine mappings with time intervals in a sequencing order. SEQ WO( 1; 2; 3) combines compatible sequences of mappings in 1 and 3 without a compatible mapping in 2 (the negative element). The last two operators NO HEAD and NO TAIL are two special cases of SEQ WO where the sequence starts or end with a negative element. Example 8 (cont'd) Let
3 = ; and 1 = fhf?v 7! a1; ?s 7! mg; [10; 10]i; hf?v 7! d1; ?s 7! hg; [12; 12]ig 2 = fhf?v 7! a1; ?s 7! mg; [16; 16]i; hf?v 7! d1; ?s 7! hg; [14; 14]ig We have that 4 = NO TAIL(SEQ( 1; 2); 3; 16) = ( hf?v 7! a1; ?s 7! mg; [10; 16]i; ) hf?v 7! d1; ?s 7! hg; [12; 14]i Let Q = (V; P; D; E C) be a query, EC 1; : : : ; EC m be event clauses, W ; W1; : : : ; Wn, be window speci cations, P; P1; : : : ; P` be graph patterns, and t be a time point. The evaluation of Q at t is recursively de ned by the function [[:; :]] as follows.
Case (
[[Q; t]] = [[(V; P; D; EC); t]] = fh jV ; [t1; t2]i j h ; [t1; t2]i 2 JOIN([[EC; t]]; [[P; t]]D)g (
[[SEQ(W1; : : : ; Wi 1!Wi; Wi+1; : : :; Wn); t]] =
[[SEQ WO(SEQ(W1; : : : ; Wi 1); Wi; SEQ(Wi+1; : : :; Wn); t]] (
[[W ; t]] = [[(s; !; TSP ); t]] = [[TSP ; t]]S!s
[[SEQ(P1; P2; : : : ; P`); t]]S! = [[SEQ(P1; SEQ(P2; : : : ; P`)); t]]S!
[[SEQ(P1; P2); t]]S! = SEQ([[P1; t]]S!; [[P2; t]]S!)
(
[[SEQ WO(SEQ(P1; : : : ; Pi 1); Pi; SEQ(Pi+1; : : : ; P`)); t]]S! (
One can see that 4 in Example 8 is the result of [[E C; 16]]. On the other hand, 5 = [[P; t]]D = ff?v 7! a1; ?s 7! mgg. The mapping f?v 7! d1; ?s 7! hg is not concluded in 5 because there is no all-subway path from h to c. Joining 4 and 5 and project the output to V gives us a single answer ?s 7! m. 5
A number of RSP engines have been developed by the RSP community, namely C-SPARQL [5], CQELS [17], EP-SPARQL/ETALIS [3], SPARQLStream [7], and Sparkwave [13]. Among them, C-SPARQL provides a function to extract timestamps of the input triples, and by applying comparison on them, one can mimic the sequence operator without negation. However, it cannot capture complicated event patterns as time points-based semantics cannot cover multiple overlapping time intervals. Sparkwave provides RDFS entailment, which is subsumed by the navigational paths proposed in this work.
Only EP-SPARQL/ETALIS explicitly provides CEP functionalities via operators such as SEQ, PAR, DURING, etc. SEQ with negation is not directly o ered but can be mimicked by existing operators. EP-SPARQL is actually just a fragment of ETALIS to work with RDF streams. ETALIS o ers a Prolog rule-based semantics, and execution of the semantics boils down to backward chaining. On the other hand, we propose here an operational semantics in the SPARQL style. It is interesting to later on have a detail comparison of these two semantics.
Regarding more recent work, [11] proposed a data model for Semantically enabled Complex Event Processing in which RDF is considered as a rst-class citizen. This model can be seen as an adaptation of the SASE approach [21] to work with RDF triples. LARS [6] is a logic-based framework for analyzing stream reasoning. It has a high expressiveness as the consequence of having a semantics based on Answer Set Programming [10] with advanced features such as recursion, non-monotonic reasoning, etc. It also provides di erent ways to refer to time using temporal operators. However, LARS has a similar problem as C-SPARQL in capturing CEP as it bases on time points. Furthermore, LARS has been developed mainly for the purpose of theoretical analysis instead of practical implementation. 6
We propose an extension of the CQELS-QL to CQELS-CEP to handle navigational paths and complex event processing, starting with operator SEQ, which requires to enhance the current RSP query model to work with time intervals. We also give a semantics of the extended language in the SPARQL style. Future work needs to be done on both theoretical and practical sides. For the former, we will extend the semantics to handle Kleene closure of CEP operators, and compare our semantics with that of EP-SPARQL/ETALIS. More e ort will be spent on analyzing the complexity of CQELS-CEP. Regarding practical work, e cient data structures and algorithms will be designed and implemented to realize the proposed semantics.
This work has emanated from research supported in part by research grants from Irish Research Council under Grant No. GOIPD/2013/104, European Commission under Grant No. FP7-ICT-608662 (VITAL), and by the Austrian Science Fund (FWF) project P26471.