Towards Spatial Ontology-Mediated Query Answering over Mobility Streams

Abstract

The development of (semi)-autonomous vehicles, communication between vehicles and infrastructure (V2X) will aid to improve road safety by identifying dangerous traffic scenes. A key to this is the Local Dynamic Map (LDM), which acts as an integration platform for static, semi-static, and dynamic information about traffic in a geographical context. At present, the LDM approach is purely database-oriented with simple query capabilities, while an elaborate domain model as captured by an ontology and queries over data streams that allow for semantic concepts and spatial relationships are still missing. To fill this gap, we present an approach in the context of ontology-mediated query answering that features conjunctive queries over DL-LiteA ontologies allowing spatial relations and window operators over streams having a pulse. Query evaluation is possible by rewriting to ordinary DL-LiteA that involves transformation of spatial relations and epistemic aggregate queries.

1 Introduction

The development of (semi)-autonomous vehicles needs extensive communication between vehicles and the infrastructure, which is covered by Cooperative Intelligent Transport Systems (ITS). These systems collect temporal data (e.g., traffic light signal phases) and geospatial data (e.g., GPS positions), which is exchanged by vehicle-to-vehicle, vehicle-toinfrastructure, and combined communications (V2X). V2X allows to improve road safety by processing and understanding traffic scenes, e.g., red light violation, thad could lead to accidents. A key technology for this is the Local Dynamic Map (LDM) [ 2 ], which acts as an integration platform for static, semi-static, and dynamic information in a geographical context. Current approaches for an LDM are purely database-oriented with simple query capabilities. An elaborate domain model, captured by a mobility ontology, and extended queries over data streams allowing spatial relations are still missing.

Our aim is to enable spatial-stream conjunctive queries (CQ) over a semantically enriched LDM for safety applications, such as detection of red light violations on complex intersections. To realize spatial query answering (QA) over mobility streams, spatial and streaming data must be lifted to the setting of ontology-mediated QA with the frequently used ontology language DL-LiteA. However, bridging the gap between stream processing and ontology-mediated QA is not straightforward, as the semantics of DL-LiteA must be extended with spatial relations and stream queries using window operators. For this, we build on the work on spatial QA in [ 13 ] and extend ontology-mediated QA with epistemic aggregate queries (EAQ) [ 11 ] to detemporalize the streams. The extension preserves firstorder rewritability, which allows us to evaluate a CQ with spatial atoms over a stream RDBMS. Our contributions are summarized as follows: - We outline the field of V2X integration using LDMs in the mobility context (Sec. 2); - we introduce a data model and query language suited for mobility streams (Sec. 3,4); - we present a spatial-stream QA approach for DL-LiteA defining its semantics and showing the preservation of FO-rewritability. The QA approach is based on CQ over DL-LiteA ontologies, which combines window operators over streams having a pulse and spatial relations over spatial objects (Sec. 5); - we provide a technique for query rewriting taking the above into account. For query evaluation, we extend and apply the known techniques of (a) transformation of spatial objects resp. relations into ordinary DL-LiteA; (b) epistemic aggregate queries, e.g., average, for a “detemporalization” of the streams; and (c) provide a technique for query rewriting with EAQs (Sec. 6).

In Sec. 7 and 8, we describe related work and conclude with future work. 2

V2X Integration using Local Dynamic Maps

The base communication technologies (i.e., the IEEE 802.11p standard) allow wireless access in vehicular environments, which enables messaging between vehicles themselves and the infrastructure, called V2X communication. Different types of messages are broadcast every 100ms by traffic participants and will inform others about their current state such as position, speed, vehicle type; the detailed topology of an intersection, including its lanes and their connections; the projected signal phases (e.g., green) for each lane; and information on specific events like road works in a designated area [ 2 ].

Local Dynamic Maps. As a comprehensive integration effort of V2X messages, the SAFESPOT project [ 2 ] introduced the concept of an LDM as an integration platform to combine static geographic information system (GIS) maps with dynamic environmental objects (e.g., vehicles, pedestrians). The integration was motivated by advanced safety applications as red light violation, which need an “overall” picture of the traffic environment. The LDM consists of the following four layers (see Fig. 1): - Permanent static: the first layer contains static information obtained from GIS maps and includes roads, intersections, and points-of-interest; - Transient static: the second layer extends the static map by detailed local traffic informations such as fixed ITS stations, landmarks, and intersection features like lanes; - Transient dynamic: the third layer contains temporary regional information like weather, road or traffic conditions (e.g., traffic jams), and traffic light signal phases; - Highly dynamic: The fourth layer contains dynamic information of road users detected by V2X messages, in-vehicle sensors like the GPS module.

Current research (e.g., [ 17 ], [ 20 ], [ 21 ]) on the LDM architecture identified that it can be built on top of a spatial RDBMS enhanced with streaming capabilities. As recognized by [ 17 ], an LDM should be represented by a world model, world objects, and data sinks on the streamed input. However, an elaborate domain model, captured by an LDM ontology, and extended queries over data streams allowing spatial relations are still missing in current approaches. The ontology represents an integration schema, which we modeled as a DL-LiteA LDM ontology capturing the different layers of an LDM (cf. [ 12 ]). Safety Applications on Intersections. “Road intersection safety” is an important application for improving road safety [ 2 ]. Intersections are the most complex environments and need special attention, where hazardous situations like obstructed view or red-light violation might lead to accidents. We take them as a motivation and running example. Example 1. The following query detects red-light violations on intersections by searching for vehicles y with speed above 30km/h on lanes x whose signals will turn red in 8s: q1(x; y) : LaneIn(x) ^ hasLocation(x; u) ^ intersects(u; v) ^ pos(line; 4s)(y; v) ^ V ehicle(y) ^ speed(avg; 4s)(y; r) ^ (r > 30) ^ isM anaged(x; z) ^ SignalGroup(z) ^ hasState(first; 8s)(z; Stop) Query q1 exhibits the different dimensions which need to be combined: (a) V ehicle(y) and isM anaged(x; z) are ontology atoms, which have to be unfolded in respect to the ITS domain ontology; (b) intersects(u; v) and hasLocation(x; u) are spatial atoms, where the first checks spatial intersection and the second the assignment of a geometry to an object; (c) speed(Avg 2s)(y; v) defines a window operator that aggregates the average speed of the vehicles over the stream and hasState(first; 8s) gives us the next upcoming traffic light state.

3 Streams, Pulses, and Spatial Databases

We now introduce the data model and sources which are used in spatial-stream QA. Streams and Pulses. Our data model is point-based (vs. interval-based) and captures the valid time (vs. transaction time) saying that some data item is valid at that time point. We extend this validity of time, and say that a data item is valid from its time point until the next data item is added to the stream. To capture streaming data, we introduce the timeline T, which is a closed interval of (N; ). A (data) stream is a triple F = (T; v; P ), where T is a timeline, v : T ! hF ; SF i is a function that assigns to each element of T, called timestamp (or time point), data items (called membership assertions) of hF ; SF i, where F (resp. SF ) is a stream (resp. spatial with streams) database, and P is an integer called pulse defining the general interval of consecutive data items on the timeline (cf. [ 6,18 ]). A pulse generates a stream of data items with the frequency derived from the interval length. We always have a main pulse PT with a fixed interval length (usually 1) that defines the lowest granularity of the validity of data items. The pulse also aligns the data items, which arrive asynchronously in the database, to the timeline.

Extending [ 18 ], we allow additional larger pulses that generate streams with a lower frequency allowing larger intervals. Larger pulses also imply that their generated data items are valid longer than items from the main pulse, thus allowing us to resize the window size of a query and perform optimizations such as caching. Furthermore, pull-based queries are executed at any single time point i denoted as Ti. Push-based queries are evaluated asynchronously where the lowest granularity is given by PT.

Example 2. For the timeline T = [0; 100], we have the stream F1 = (T; v; 1) of vehicle positions and speed at the assigned time points v(0) = fspeed(c1; 30); pos(c1; (5; 5)); speed(b1; 10); pos(b1; (1; 1))g, v(1) = fspeed(c1; 29); pos(c1; (6; 5)) speed(b1; 5); pos(b1; (2; 1))g, and v(2) = fspeed(c1; 34); pos(c1; (7; 5))g for the individuals c1 and b1. A second “slower” stream F2 = (T; v; 5) captures the next signal state of a traffic light: v(0) = fhasState(t1; Red)g and v(5) = fhasState(t1; Green)g. As F2 has a pulse of p = 5, we know v(4) = ; but under an alternative semantics with an inertia assumption, we could conclude v0(4) = fhasState(t1; Red)g. Further, the static ABox contains the assertions Car(c1), Bike(b1), and SignalGroup(t1).

Spatial Databases and Topological Relations. We recall the essential idea based on Point-Set Topological Relations (see [ 13 ]). Spatial relations are defined via pure set theoretic operations based on PE R2 of all points in the plane. An admissible geometry g(s) is a sequence p = (p1; : : : ; pn) of points over PF , where PF PE . We define a spatial database over S as a pair S = (PF ; g) of a point set PF and a mapping g : S ! Si 1 PF i, where S is a set of spatial objects. The extent of a geometry p (full point set) is given by the function points(p) as a (possibly infinite) subset of PE . For a spatial object s, we let g(s) be its geometry and points(s) := points(g(s)). For our KB, we consider the following types of admissible geometries p over PF , and let PE = Ss2 S points(s) (see [ 13 ] for more): - points are the sequences p = (p1), where points(p1) = fp1g; - line segments are sequences p = (p1; p2), and points(p) = f p1 + (1 )p2 j 2

R; 0 1g; We use points to evaluate the spatial relations of two spatial objects via their respective geometries and define the relations in terms of pure set operations (see [ 13 ] for more): - Contains(x; y) : points(y) points(x), Intersect (x; y) : points(x) \ points(y)6=;. A spatial relation S(s; s0) with s; s0 2 S holds on a spatial database S, written S j= S(s; s0), if S(g(s); g(s0)) evaluates to true. Relative to points, this is easily captured by a firstorder (FO) formula over (R2; ), and with regard to geo-spatial RDBMS trivially FO expressible and rewritable into FO queries. 4

Syntax and Semantics of DL-LiteA (S,F)

We start from previous work in [ 13 ], which introduced spatial CQ answering for DL-LiteA, and lift the semantics from the spatial DL-LiteA KB to the spatial-stream KB. Syntax and Semantics of DL-LiteA . We consider a vocabulary of individual names

I , domain values V (e.g., N), and spatial object S . Given atomic concepts A, atomic roles P , and atomic attributes E, we define (a) basic concepts B, and basic roles Q, and (b) complex concepts C and complex role expressions R, complex attributes V , basic value-domains E (range of attributes), and value-domain expressions D: B ::= A j 9Q j (UC ) E ::= (UC ) Q ::= P j P

C ::= >C j B j :B j 9Q:C0 D ::= >D j D1 j : : : j Dn

R ::= Q j :Q V ::= U j :U where (c) P is the inverse of P , >D is the universal value-domain and >C is the universal concept; and UC is a given attribute with (UC ) (resp. (UC )) as its domain (resp. range). A DL-LiteA knowledge base (KB) is a pair K = (T ; A) where the TBox T (resp. ABox A) consists of a finite set axioms such as (see [ 10 ] for a complete list): - inclusion assertions of the form B v C, Q v R, E v D, and U v V ; - membership assertions of the form A(a), D(c), P (a; b), and U (a; c), where a resp. b are individual names in I and c is a value in V .

We denote by pred(T ) the set of all concept and role names. The semantics of DL-LiteA is given in terms of FO interpretations I = ( I ; I ), where I is a nonempty domain, the disjoint union of II of IV , and I is an interpretation function as usual (see [ 10 ]). Satisfaction of axioms and logical implication are denoted by j=. We assume the unique name assumption (UNA) holds for different individuals resp. values and adopt the constant domain assumption, saying that all models share the same domain. Checking satisfiability of DL-LiteA ontologies is FO rewritable [ 10 ], i.e., for every T , there is a Boolean FO query qT (constructible from T ) s.t. for every A, T [ A is satisfiable iff DB(A) 6j= qT , where DB(A) is the least Herbrand model of A.

Syntax DL-LiteA (S,F). Let T be a timeline and let S , I , and V be pairwise disjoint sets as defined above. A spatial-stream knowledge base is defined as a tuple KSF = hT ; A; SA; hF ; SF i ; Bi, where T (resp. A) is a DL-LiteA TBox (resp. ABox), SA is a spatial database, and hF ; SF i is a stream database with support for spatial data. Furthermore, B I S is a partial function called the spatial binding from A to SA and F to SF . In case we restrict to a spatial KB resp. stream KB, we have KS = hT ; A; SA; Bi resp. as KF = hT ; A; F i.

We introduce for DL-LiteA the ability to specify the localization of pred(T ). For this, we extend the syntax similar to [ 13 ] and include concept and role localization: C ::= >C j B j :B j 9Q:C0 j (loc A) j (locs A)

R ::= Q j :Q j (loc Q) j (locs Q); where s 2 S and the concept and roles are as before. Intuitively, (loc A) is the set of individuals in A that can have a spatial extension, and (locs A) is the subset which have a single extension s. The extension with streaming is captured by the following axioms: (streamF C); (streamF R); where F is a particular stream over either complex concepts C or roles R in hF ; SF i. Example 3. For Ex. 2 , a simple TBox contains (streamF1 speed), (streamF1 (loc pos)), (streamF1 V ehicle), and (streamF2 hasState). Further, we have the axioms Car v Vehicle, Bike v Vehicle, and Ambulance v 9hasRole:Emergency .

Semantics DL-LiteA (S,F). We give a semantics to the localization (loc Q) and (locs Q) for individuals of Q with some spatial extension resp. located at s, such that a KB KS = hT ; A; S; Bi can be readily transformed into an ordinary DL-LiteA KB KO = hT 0; A0i, using the fresh spatial top concept CST and spatial concepts Cs. An interpretation of KS is a structure IS = I ; I ; bI , where h I ; I i is an interpretation of hT ; Ai and bI I S is a partial function that assigns some individuals a location, such that for every a 2 I , (a; s) 2 BA implies bI (aI ) = s. We extend the semantics with (loc Q) and (locs Q), where Q is an atomic role in T by ((loc A) and (locs A) are accordingly): (loc Q)IS f(a1; a2) j (a1; a2) 2 QI ^ 9s 2 S : (a2; s) 2 bI g; (locs Q)IS = f(a1; a2) j (a1; a2) 2 QI ^ (a2; s) 2 bI g: The transformation of KS to an ordinary DL-LiteA KB KO adds the spatial concepts CS and Cs for every s 2 S to T 0. Then, each loc Q (resp. (locs Q)) is replaced in T 0 by the axioms 9Q:CS (resp. 9Q:Cs) and Cs is connected to the top concepts by Cs v CS . Finally, the binding is compiled into T 0 by adding Cs(a) for every (a; s) 2 B. Following the approach in [ 13 ], it can be shown that the models of KS and KO correspond wrt. the same domain and pred(T ). As a consequence, satisfiability checking for DL-LiteA ontologies is in LOGSPACE (in fact FO-rewritability), the same holds for DL-LiteA(S) .

The idea of an initial streaming semantics is by interpreting the stream over the full timeline, which can be captured by FA as a finite sequence of temporal ABoxes, such that FA = (Fi)Tmin i Tmax , which is obtained via the evaluation function v on F and T (cf. [ 7 ], [ 14 ]). Then, we define the interpretation of the point-based model over T as a sequence IF =(Ii)Tmin i Tmax of interpretations Ii= I ; Ii . IF is a model of KF , such that IF j= KF iff Ii j= Fi and Ii j= T ; for all i 2 T:

The semantics of the (streamF C) and (streamF R) axioms is along the same line. A stream axiom is satisfied, if a complex concept C (resp. role R) holds over all the time points of stream F = (T; v; P ); thus we restrict our models such that: (streamF C)I = S I j e 2 CIi g); (streamF R)I = Si2tp(T;P )(fe 2

i2tp(T;P )(f(a1; a2) j (a1; a2) 2 RIi g); where tp(T; P ) is a set of time points determined by the segmentation of T by P . This allows us to check for the satisfiability of a KB and gives us a global consistency, which is of theoretical nature, since we would need to know the full timeline. 5

Spatial-Stream Query Language over DL-LiteA (S,F)

We next define spatial-stream conjunctive queries (STCQ) over KSF . Such queries may contain ontology, spatial, and stream predicates. An STCQ q(x) is a formula: l n m ^ QOi (x; y) ^ ^ QSj (x; y) ^ ^ QFk (x; y) (1) i=1 j=1 k=1 where x are the distinguished (answer) variables and y are either non-distinguished (existentially quantified) variables, individuals from I , or values from V . Each QOi (x; y) has the form A(z) or P (z; z0), with A resp. P from pred(T ) and z; z0 from x [ y. Each atom QSj (x; y) is from the vocabulary of spatial relations (see Sec. 3) and of the form S(z; z0), with z; z0 from x [ y; QFj (x; y) is similar to QOi (x; y) but adds the vocabulary for stream operators, which are taken from [ 6 ] and relate to CQL operators [ 4 ]. Moreover, we have a window over a stream that is derived from L (in Z+ for past or in Z for future time units) resp. Ti, and an aggregate function agr 2 fcount; min; max; sum; avg; f irst; lastg (see Sec. 6) that is applied to the data items in the window:3 - QFj TL agr represents the aggregate of last/next L time units of (stream Fj ); - QFj T represents the current tuples of Fj with L = 0; - QFj TO agr: represents the aggregate of all previous L time units of Fj ; Example 4. We modify q1(x; y) of Ex. 1 and use the stream operators instead: q1(x; y) : LaneIn(x) ^ hasLocation(x; u) ^ intersects(u; v) ^ position 4T line(y; v) ^ V ehicle(y) ^ speed 4T avg(y; r) ^ (r > 30) ^ isM anaged(x; z) ^ SignalGroup(z) ^ hasState T 8first(z; Stop) Certain Answer Semantics. In the streamless setting, due to the OWA, queries are evaluated over all (possibly infinitely many) models. Certain answers retain the tuples that are answers in all possible models. More formally, a match for q(x) in an interpretation I= I ; I of K is a function : x [ y ! I such that (c) = cI , for each constant c in x [ y, and for each i = 1; : : : n: – (i) (z) 2 AI , for QOi (x; y) = A(z); and – (ii) ( (z); (z0)) 2 P I , for QOi (x; y) = P (z; z0). 3 This would be represented in CQL as R[Range L], R[Now], R[Range L Slide D], etc. Then, a tuple c = c1; : : : ; ck over I is a certain answer for q(x) in I, x = x1; : : : ; xk, if q(x) has some match in I such that (xi) = ci, i = 1; : : : ; k; and c is a certain answer for q(x) over K, if it is a certain answer in every model I of K. The result of q(x) over K, denoted Cert(q(x); K), is the set of all its (certain) answers. If we drop T , we have a DB setting and denote with Eval(q(x); I) the set of matches of q(x) over a single model (a database instance) I of A that coincides with DB(A).

Spatial Queries. For spatial CQ we have additionally spatial atoms and extend a match for q(x) and j = 1; : : : ; m as follows: – (iii) 9s; s0 2 S : ( (z); s) 2 bI ^ ( (z0); s0) 2 bI ^ S j= S(s; s0), for QSj (x; y) :=

S(z; z0).

For spatial atoms individuals must have (unique) spatial extensions and the relationship between them must hold. As shown in [ 13 ], the semantic correspondence between KO and KS guarantees that we can transform q(x) into an equivalent query over KS 0 = hT 0; A0; SAi by replacing each spatial atom S(z; z0) in q(x) with qSj (z; z0):

Ws;s02 S (Cs(z) ^ Cs0 (z0) ^ S(s; s0)); it is easily transformed to a union of CQs (UCQ): uq(x) = qS0 (x) ^ ^ qSn (x) ^ qrest(x); where qrest(x) is the rewriting of the non-spatial part of q(x). A tuple c is then an answer in uq(x) over KS 0 iff it is an answer in every model I0 of KS 0. Using the above rewriting and the semantic correspondence of KO and KS , spatial atoms can be rewritten into a “standard” DL-LiteA UCQ, and conclude that Cert(q(x); KS ) = Cert(uq(x); KS 0). Thus, answering spatial CQs is still FO-rewritable (details in [ 13 ]). QA over Streams. The standard certain answers semantics for ontology-mediated QA can be extended to streams in different ways. A possible approach is described in [ 8 ], [ 7 ], and [ 14 ], where a boolean CQ is evaluated over KF with A by rewriting T such that for every time point i 2 T: T ; A; T j= q iff DB(Ai) j= qT ; for all i 2 T; where qT is the FO rewriting of q in T and DB(Ai) is the least Herbrand model of A at time point Ti. This approach is extended by either evaluation over the entire history of A using temporal operators (e.g., always) from Linear Temporal Logic (LTL) [ 7 ], or by using time intervals and a temporal query language with less/greater operators [ 14 ]. Our approach aims at answering queries at a single time point Ti with stream atoms that define aggregate functions on different windows sizes relative to Ti; thus we ignore LTL operators and time intervals. We consider a semantics based on epistemic aggregate queries (EAQ) over ontologies [ 11 ] by dropping the order of time points for the membership assertions and handle the (streamed) assertions as bags, which is similar to “normal” stream processing approaches. As described in [ 11 ], aggregate queries are defined over bags of numeric and symbolic values, called groups and denoted as fj jg. Aggregates cannot be directly transferred to DL-Lite, thus [ 11 ] extended the database semantics for aggregates with an epistemic operator K and a two-layer evaluation using the completion w.r.t T . More formally, an EAQ is defined as qa(x; agr(y)) : K x; y; z: ; 4 where x are the grouping variables, agr(y) is the aggregate function and variable, and is a CQ called main conditions; z are the disjoint existential variables of . We call w := x [ y [ z the K-variables of . The definition of a group was extended in [ 11 ] by a multiset Hd of groups d, called K-group, as:

Hd := fj (y) j 2 KSatI;K(z; ) and (x) = d jg; 4 We simplified EAQs of [ 11 ] by omitting and consider only aggregates with a single variable. where KSat are the satisfying K-matches of for the model I of K and given by:

KSatI;K(w; ) := f 2 Eval( ; I) j (w) 2 Cert(auxqa ; K)g; where auxqa (w) is the auxiliary atom used to map w only to known solutions. The set of K-answers for an EAQ query q over I and K can now be derived as: qaI := f(d; agr(Hd)) j d = (x); for some 2 KSatI;K(w; )g: The epistemic certain answers ECert(qa; K) for a query qa over K is the set of K-answers that are answers in every model I of K. To compute ECert(qa; K), [ 11 ] gave a “general algorithm” GA that (1) computes the certain answers, (2) projects on the K-variables, and (3) aggregates the resulting tuples. Importantly, evaluating EAQs reduces to standard CQ evaluation over DL-LiteA with LOGSPACE data complexity.

6 Query Rewriting by Stream Aggregation

As discussed above, we drop the temporal order by evaluating the EAQ queries over the bag of temporal ABox assertions. Thus, we evaluate the EAQ over several filtered and merged temporal ABoxes that are created according to the window operator and Ti. The filtering and merging, relative to the window size and Ti, creates a windowed ABox A that is the union of a static ABox A and the filtered stream ABoxes from F . The EAQ aggregates can be applied on normal objects by counting, on concrete values by aggregate functions like sum, and on spatial objects by applying geometrical functions that create geometries like line. More formally, a stream atom TL agr is evaluated as an EAQ over ontologies defined as follows: q (x; agr(y)) : K x; y; z: TL; where x is the grouping variables and y the aggregate variable, z are the disjoint existential variables, and is a subquery of q with atoms in the same scope of the window operator

TL and aggregate function agr.

Example 5. For query q1(x; y) of Ex. 4, we have three EAQs represented as: qpos(y; line(v)) : K y; v: V ehicle(y) ^ position(y; v); qspeed(y; avg(r)) : K y; r: V ehicle(y) ^ speed(y; r); qstate(z; f irst(m)) : K z; m: hasState(z; m)

We extend the evaluation of EAQs for the stream setting, such that an EAQ is evaluated over the window relative to Ti, the window operator TL, and the pulse P . KSat is now the set of K-matches of for a model I of K , where the windowed ABox A is defined as A = A [ SfAi j ws i weg. We have four cases for the window size L and a pulse P , where P enlarges L according to its interval length: - a current window with L = 0 that is ws = we = Ti ; - a past window with L > 0 leading to ws = (Ti L) and we = Ti; - a future window with L < 0 that is ws = Ti and we = (Ti + L); - the entire history with O resulting in ws = 0 and we = Ti.

We obtain KB K = hT ; A i as above; the epistemic certain answers ECert (q ; K ) for q over K are the K-answers that are answers in every model I of K as: qI := f(d; agr(Hd)) j d = (x); for some 2 KSatI ;K (w; )g: In ECert , we have not addressed yet the validity of a membership assertion, say in A 1 , to the next assertion in A 3 . There are two suggestive semantics: in the first, we ignore intermediate time points, and thus A 2 will be unknown. The second semantics fills the missing gaps with the previous assertion, i.e. copies the assertion from A 1 to A 2 . For specific aggregation functions, e.g., max, min, or last, the two semantics coincide, but for sum, avg, and count, this leads to different results. Example 6. We pose the query q1(x; y) at T1 and replace the stream atoms with auxiliary atoms related to the EAQ of Ex. 5: q1(x; y) : LaneIn(x) ^ hasLocation(x; u) ^ intersects(u; v) ^ qpos(y; v) ^ qspeed(y; r) ^(r > 30) ^ isM anaged(x; z) ^ qstate(z; Stop) The queries are computed using the ABoxes A [0;1] = A [ A0 [ A1 and A [1;4] = A S1 i 4 Ai. This leads under ECert for qspeed to the groups Gc1 =fj30; 29; 34jg and Gb1 =fj10; 5jg, which results in qspeed=f(c1; 31); (b1; 7:5)g. The results for the other EAQ are qstate=f(t1; Red)g and qpos=f(c1; ((5; 5); (6; 5); (7; 5))); (b1; ((1; 1); (2; 1)))g.

ECert gives the certain answers for a single EAQ including the streamless atoms in the same scope as the stream atoms. Answering the full CQ, denoted ECertAll(q; KF ; Ti), can be done by answering each EAQ q j by ECert (q j ; K w( j;Ti) ) separately and combining the answers as follows, where w( j ; Ti) is the computed window size:

KF ; Ti j= q 1 ^ q 2 iff KF ; Ti j= q 1 and KF ; Ti j= q 2 Details on deriving each q j from q via hypertree decomposition is left for future work.

We now introduce the algorithm NSQ (see Alg. 1), where z are the non-distinguished variables in and PerfectRef (resp. Answer) is the “standard” query rewriting (resp. evaluation) as in [ 10 ]. NSQ extends the GA of [ 11 ] to compute the answers for stream CQs as follow: (1) calculate the epistemic answer for each stream atom over the different windowed ABoxes and store the result in an auxiliary ABox using new atoms. Further, replace each stream atom with a new auxiliary atom; (2) calculate the certain answers over A and the auxiliary ABox, using the “standard” DL-LiteA query evaluation. Theorem 1. Correctness of NSQ. For every stream CQ q, KB KF , and time point Ti, it holds that ECertAll(q; KF ; Ti) = NSQ(q; KF ; Ti).

Our proof sketch considers that q has to be restricted by T and standard aggregates have to fullfill aggregate conditions (see below). Correctness is based on the idea, that we exploit the computational property of decoupling answering each EAQ (Step 1) from answering the full CQ as follows (similar to [ 9 ]): 1. we let qF OL(x) be the FOL query obtained from q(x) by replacing each EAQ q i by a new predicate R i with the same arity; 2. we define Iq;KF as the FOL interpretation over I0 for R i such that (i) I = I0 (same domain) and (ii) the extension of R i is RIqi;KF = ECert (q i ; K ). For Step 2, we let Eval(qF OL; Iq;KF ) be the result of evaluating qF OL over Iq;KF . The semantic correspondence between Eval(qF OL; Iq;KF ) and ECertAll(q; KF ; Ti) is guaranteed under the following conditions: 1. The evaluation of qF OL should not be over a possibly infinite domain I , thus allowing FOL queries that are domain independent; 2. the extension of R i in Iq;KF needs to be finite, or else the evaluation is infeasible. Domain independence is ensured by using special interpretation based on the active domain, denoted as IAdom. The active domain is a subset of I built from all constants in KF , T, and q. Furthermore, FOL queries under active domain semantics are equivalent to range-restricted relational calculus (RRC) queries, with allows the translation from FOL into RRQ queries as shown in [ 1 ].

Standard Aggregates. Different aggregation functions for use in ECert(q; K) were already provided in [ 11 ]. For this, K, q and Hd have to fulfill aggregate conditions to avoid Algorithm 1: NSQ - Answer Naive Stream Query

Input: A stream conjunctive query q, time point Ti, and a KB KF Output: Set of tuples O /* Step 1: Detemporalize foreach QFi of q do

A i A Sws j we Aj according to TL and Ti ; K i hT ; A i i ; build auxi(x; y; z) from TL agr of QFi ; build qi;1(x; y; z ) from PerfectRef(auxi; T )(x; y; z) ; build qi;2(x; agr(y)) from qi;1(x; y; z ) and TL agr ; Ri;1 := evaluate Answer(auxi; K i ) (Certain answers) ; Ri;2 := evaluate qi;1 over Ri;1 (K projection) ; Ri := evaluate qi;2 over Ri;2 (Aggregation) ;

Add Ri to Aaux and replace QFi in q with Ri(x; y) ; /* Step 2: Standard evaluation O := evaluate Answer(q; hT ; A [ Aauxi) ; */ */ “wrong” aggregation and ensure correctness: (1) q has to be non-trivial and coherent, such that q is satisfiable regarding T ; (2) the variables in q must be restricted, which introduces functional dependency on epistemic variables; (3) q has uniform grouping; (4) dropping zero groups, i.e., groups having only zero values (see [ 11 ] for details). For concrete values, the following aggregation functions were introduced based on ECert(q; K) for every A: (i) count; min; max: (1) has to hold for q and K; (ii) sum: (1), (2), and (4) have to hold for q and K; (iii) avg: (1), (2), and (3) have to hold for q and K.

For last and f irst, we extend the definition of Hd, as the sequence of time points is lost. However, by iteratively checking if we have a match in some ABox A i , ws i we, at a single time point, we can determine where we have the first resp. last match. We extend Hd for f irst as follows (last is similar):

Hd0 := fj (y) j ( 2 (x) = d and ( 2 KSatI0;K(z; ) or ( 2 KSatI1;K(z; ) and 62 KSatI[0;0];K(z; )) or ::: or ( 2 KSatIn;K(z; ) and 62 KSatI[0;n 1];K(z; )) ) jg; where KSatIi;K, resp. KSatI[i;j];K, is the set of satisfying K-matches for a model Ii of hT ; A [ Aii, resp. I[i;j] of hT ; A [ Ai [ [ Aj i.

Spatial Aggregates. For spatial objects, we define aggregation functions applied on the multiset of Hd. As the order of assertions (i.e., points) is lost, we must rearrange them to an admissible geometry that is a point sequence p = (p1; : : : ; pn) as defined in Sec. 3. We thus extend agr with the new functions agrpoint and agrline on Hd to create new admissible geometries g(sd): - agrpoint: we evaluate the function last (as shown before) to get the last available position p1 and assign it to g as g(sd) = (p1); - agrline: we create the sequence (p1; : : : ; pn), where p1 6= pn and determine a total order on the bag of points in each K-group. The total order is defined such that we have a starting point using last and search backwards using last subsequently. Further functions such as computing a polygon could be defined. We must consider the binding B for spatial aggregates, hence we add 9s 2 S : ( (y); s) 2 bI to KSat. In contrast to numerical aggregates, spatial aggregates introduce for each Kgroup (d; agr(Hd)) a new spatial object sd of S and an admissible geometry g(sd) with agr(Hd) = (p1; : : : ; pn). This is achieved by adding a binding (d; sd) to B and creating a new mapping g : sd ! (p1; : : : ; pn) in Saux.

Combining KF and KS . We combine the spatial and temporal elements of a query q and KB K as follows: (1) detemporalize the stream atoms using EAQs; (2) transform the spatial query and the KB to an ordinary UCQ and KB as shown in Sec. 4. We keep LOGSPACE data complexity, as evaluating an EAQ is in LOGSPACE and the number of EAQ computations is limited by the number of aggregate atoms. Spatial binding and relations do not increase the data complexity.

7 Related Work

Data stream management systems (DSMSs) such as STREAM [ 4 ], were built supporting streaming applications by extending RDMBS. More recently, RDF stream processing engines, such as C-SPARQL [ 5 ], SPARQLstream [ 8 ], and CQELS [ 16 ], have been proposed to enable the processing of RDF streams integrated with other Linked Data sources. Besides C-SPARQL, most of them follow the DSMSs paradigm and do not support stream reasoning. EP-SPARQL [ 3 ] resp. LARS [ 6 ] proposes a language that extends SPARQL resp. CQ with stream reasoning, but translated their KB into expressive (less efficient) logic programs. For spatio-temporal RDF stream processing, a few SPARQL extensions have been proposed, such as st-SPARQL [ 15 ]. Besides [ 7 ] and [ 14 ] (see Sec. 5), closest to our work are: (i) [ 19 ] is a framework for efficient spatio-temporal queries that support spatial operators and aggregation over temporal features; (ii) [ 8 ] allows evaluating ontology-mediated QA queries over a range of data streaming systems, and (iii) [ 18 ] extends SPARQL using state sequences and aggregates, which are evaluated over streamed ABoxes. Our work differs regarding: (a) the evaluation approach based on EAQ with aggregations and (b) the main focus on querying streams of spatial data. We use results on EAQ in [ 11 ], but introduce streams over spatial data and give an initial implementation.

8 Conclusion and Future Work

Our work is sparked by the LDM for V2X communications, which serves as an integration effort for streaming data (e.g., vehicle movements) in a spatial context (e.g., intersections) over a complex domain (e.g., a mobility ontology). We introduced a suitable approach using ontology-mediated QA for realizing the LDM. For spatial-streaming queries, bridging the gap between stream processing and ontology-mediated QA is not straightforward. Thus, we provide an extension using epistemic aggregate queries to detemporalize the stream sources and extend previous work in [ 13 ]. The detemporalization preserves FO-rewritability, which allows us to evaluate conjunctive queries with spatial atoms over existing stream RDBMS. Currently, we are working on a technique for suitable query execution plans using hypergraph decomposition. We have been implementing an experimental prototype to check the feasibility of our approach on initial experiments with mobility data (details on www.kr.tuwien.ac.at/research/projects/loctrafflog/sr2016/).

Future research aims at the theoretical and practical side of our approach. On the former, complexity results for our algorithm under different aggregate functions are of interest, as well as dealing with consistent QA. Our bag semantics could introduce inconsistencies in larger windows, we thus may consider different repairs as in belief revision. On the later, the implementation could be extended to pull-based QA and constraints such as guaranteed latency. This requires optimizations, such as caching, window size adaptation, and efficient query rewriting techniques. Also more complex spatial aggregation, i.e., polygons or trajectories, are of interest. Finally, evaluation and testing using e.g., the SUMO traffic simulation (http://sumo.dlr.de/) under real conditions is desired.

References

1. Abiteboul , S. , Hull , R. , Vianu , V. (eds.): Foundations of Databases: The Logical Level . AddisonWesley Longman Publishing Co., Inc . ( 1995 )

2. Andreone , L. , Brignolo , R. , Damiani , S. , Sommariva , F. , Vivo , G. , Marco , S. : Safespot final report . Tech. Rep. D8.1 . 1 ( 2010 ), available online.

3. Anicic , D. , Fodor , P. , Rudolph , S. , Stojanovic , N.: Ep-sparql: a unified language for event processing and stream reasoning . In: Proc. of WWW 2011 . pp. 635 - 644 ( 2011 )

4. Arasu , A. , Babu , S. , Widom , J.: The CQL continuous query language: semantic foundations and query execution . VLDB J . 15 ( 2 ), 121 - 142 ( 2006 )

5. Barbieri , D.F. , Braga , D. , Ceri , S. , Valle , E.D. , Grossniklaus , M.: C-sparql: a continuous query language for rdf data streams . Int. J. Semantic Computing 4 ( 1 ), 3 - 25 ( 2010 )

6. Beck , H. , Dao-Tran , M. , Eiter , T. , Fink , M.: LARS: A logic-based framework for analyzing reasoning over streams . In: Proc. of AAAI 2015 . pp. 1431 - 1438 ( 2015 )

7. Borgwardt , S. , Lippmann, M. , Thost , V. : Temporalizing rewritable query languages over knowledge bases . J. Web Sem . 33 , 50 - 70 ( 2015 )

8. Calbimonte , J. , Mora , J. , Corcho , O ´. : Query rewriting in RDF stream processing . In: Proc. of ESWC 2016 . pp. 486 - 502 ( 2016 )

9. Calvanese , D. , De Giacomo , G. , Lembo , D. , Lenzerini , M. , Rosati , R.: Eql-lite: Effective first-order query processing in description logics . In: Proc. of IJCAI 2007 . pp. 274 - 279 ( 2007 )

10. Calvanese , D. , Giacomo , G.D. , Lembo , D. , Lenzerini , M. , Rosati , R. : Tractable reasoning and efficient query answering in description logics: The dl-lite family . J. Autom. Reasoning 39 ( 3 ), 385 - 429 ( 2007 )

11. Calvanese , D. , Kharlamov , E. , Nutt , W. , Thorne , C. : Aggregate queries over ontologies . In: Proc. of ONISW 2008 . pp. 97 - 104 ( 2008 )

12. Eiter , T. , Fu¨reder, H., Kasslatter , F. , Parreira , J.X. , Schneider , P. : Towards a semantically enriched local dynamic map . In: Proc. of ITS World Congress 2016 . To appear.

13. Eiter , T. , Krennwallner , T. , Schneider , P. : Lightweight spatial conjunctive query answering using keywords . In: Proc. of ESWC 2013 . pp. 243 - 258 ( 2013 )

14. Klarman , S., Meyer, T.: Querying temporal databases via OWL 2 QL . In : Proc. of RR 2014 . pp. 92 - 107 ( 2014 )

15. Koubarakis , M. , Kyzirakos , K. : Modeling and querying metadata in the semantic sensor web: The model strdf and the query language stsparql . In: Proc. of ESWC 2010 . pp. 425 - 439 ( 2010 )

16. Le-Phuoc , D. , Dao-Tran , M. , Parreira , J.X. , Hauswirth , M.: A native and adaptive approach for unified processing of linked streams and linked data . In: ISWC 2011 . pp. 370 - 388 ( 2011 )

17. Netten , B. , Kester , L. , Wedemeijer , H. , Passchier , I. , Driessen , B. : Dynamap: A dynamic map for road side its stations . In: Proc. of ITS World Congress 2013 ( 2013 )

18. O¨ zc¸ep, O¨ .L. , Mo¨ller, R., Neuenstadt , C. : Stream-query compilation with ontologies . In: Proc. of AI 2015 . pp. 457 - 463 ( 2015 )

19. Quoc , H.N.M. , Le Phuoc , D.: An elastic and scalable spatiotemporal query processing for linked sensor data . In: Proc. of SEMANTICS 2015 . pp. 17 - 24 . ACM ( 2015 )

20. Shimada , H. , Yamaguchi , A. , Takada , H. , Sato , K. : Implementation and evaluation of local dynamic map in safety driving systems . J. Transportation Technologies 5 ( 2 ), 102 - 112 ( 2015 )

21. Ulbrich , S. , Nothdurft , T. , Maurer , M. , Hecker , P. : Graph-based context representation, environment modeling and information aggregation for automated driving . In: Proc. IEEE Intelligent Vehicles Symposium 2014 . pp. 541 - 547 ( 2014 )