Data changes worldwide in size and over time and when new data arrives rapidly from different sources, an easy access to dynamic data becomes a keyfactor. Therefore, temporalizing and streamifying ontology-based data access (OBDA) is a very important topic today, where the industry still relies on algebraic queries. We contribute to the practical efforts in this field by showing how a specific ontology-based stream querying language can be transformed with respect to mappings into standard SQL queries. For that purpose we choose the stream and temporal reasoning query language STARQL. STARQL is motivated by industrial usecases and evaluated in the European research project Optique. It offers access to temporal and streaming data as well for reactive diagnosis or continous monitoring.
The following work contributes to research in the field of OBDA1 on
temporal data [
Sensor data is playing an important role in the IP7 EU project Optique.
Siemens, one of the industrial stakeholders, provides huge amounts of sensor
data to the project [
The idea of an ABox sequencing strategy makes the required steps, rewriting and unfolding for Ontology Based Data Access a challenging task. In the next section, we analyze the rules for STARQL transformations into algebraic queries like SQL and show that the rewriting and unfolding steps are indeed possible. 2
Transformation Rules for Streaming Data with STARQL As mentioned in the last section, rewriting and unfolding of the ABox sequencing strategy is the most challenging task. STARQL uses a clause especially designed for temporal data access called Having Clause. We will concentrate explicitly on transforming the STARQL Having-Clause into an algebraic query language in this paper. An example for the use of a Having Clause can be seen in Listing 1. Here we see the definition of a stream Sout (Line 1), its output is defined as sensors of the type MonInc, which stands for monotonically increasing (Line 2). In line three the input stream with sensor values and the sliding window operator is defined, which is of size three seconds and slides with exactly one second for each window evaluation. In the next part the sequence of ABoxes for each window is defined. StdSeq stands for a sequence where each data set, which is represented by another timestamp, is placed in different ABoxes by an increasing order. The important part to evaluate the content of each window is shown in lines 5 to 7. For STARQL a new so called Having Clause has been explored. Its syntax is defined in first order logic using quantors for binding variables, conjunctions, disjunctions or negations of atoms, which can be graph triples or logical and arithmetic expressions. In our specific example a filter for monotonically increasing sensor data is used. It can be read as follows: for all timepoints i smaller than j it is true that if in i a sensor has a value x and in j the same sensor has a value y, then x must be smaller than or equal i.
An expression of the Having Clause from Listing 1 in first order logic is shown
in formula 1. For an analysis of the STARQL syntax and semantics we refer to
[
8i; j; x; y((R(i; s; x) ^ S(j; s; y) ^ i < j) ! (x y)) (1)
We will take this query as a running example in the further paper. 1 CREATE STREAM S_out AS 2 CONSTRUCT GRAPH NOW { ?s rdf : type MonInc } 3 FROM STREAM S_Msmt [NOW -2s , NOW ] - >"1S "^^ xsd : duration 4 SEQUENCE BY StdSeq AS seq 5 HAVING FORALL ?i ,? j IN seq ,?x ,? y: 6 IF ( GRAPH ?i { ?s : val ?x } AND GRAPH ?j { ?s : val ?y } AND ?i < ?j) 7 THEN ?x <= ?y
Listing 1: Example query in STARQL
Classical OBDA without querying time or time sequences has been researched
for many years. In the non-temporal case the query language SPARQL is
commonly used. Query languages like SPARQL (or in our temporal case STARQL)
that are transformed to relational algebra must be domain independent, which
can be achieved by a syntactical criterion requiring that all variables have to be
range restricted (see [
For our transformation of the STARQL Having Clause, we make two more assumptions. First, our database offers a view that represents time tagged data with a time sequence representation of the sliding window in two additional columns, where the schema consists of WindowID, ABoxID, Timestamp and [Datacolumns] for every temporal table. An example view for a sliding window with measured data is shown in Table 1. It includes measurements for a single sensor and describes two windows with WindowID 1 and 2, where the window width is of three minutes. Every single ABox in the sequence can be accessed by the ABoxID in the second column.
For the second assumption we assume additionally that the unfolding for a single graph triple “GRAPH i { subject predicate value}”, where i respresents the index variable of ABoxes, is trivial and can be unfolded with mappings to aid!i wid;aid;x1;:::;xn (R), where wid represents the evaluated window, aid the ABox, x1; :::; xn the specific data columns and R the described data view in sliding window format. A projection of the WindowID is necessary for temporal queries, where we explore several time windows in parallel. For streaming queries, where we evaluate the data of a single window per timepoint only, an index variable for comparing the ABoxes in a sequence would be enough.
Making these assumptions, the Having Clause of STARQL can be
transformed by following the algorithm below for transforming from Safe Range
Normal Form into Relational Algebra Normal Form (for detailed informations and
proofs, see [
First, we normalize the Safe Range Form of the Having Clause by five steps: 1. Variable substitution: All variable names are substituted until every variable is bound only once and no variable occurs free and bound. 2. Remove universal quantifier: We replace all 8x by :9x: 3. Remove implications: We replace all ! by : _ 4. Push negations: We push every negation down into the formula until every child of a negation is either an atom or an exists quantifier 5. Flattening: Flatten every and, which is the child of an and, do the same for or and exists quantifiers
Second, we normalize again for the relational algebraic normal form by three additional steps: 1. Push into or: We push every or upwards until there is no or as a child of an and. 2. Push into quantifier: if is of the form 1 ^ ::: ^ n ^ 9x and not all free variables of are range restricted, push a subset of 1 ^ ::: ^ n as conjunct into until all free variables of are range restricted. 3. Push into negated quantifier: if is of the form 1 ^ ::: ^ n ^ :9x and not all free variables of are range restricted, copy a subset of 1 ^ ::: ^ n as conjunct into until all free variables of are range restricted. :9i; j; x; y(R(i; s; x) ^ S(j; s; y) ^ i < j ^ x > y) (2)
After both normalization steps the Having Clause example from Listing 1 can now be written in RANF as shown in Formula 2.
For transforming a formula from Relational Algebraic Normal Form (RANF)
into an algebraic query E , we adopt the modified algorithm 1 with added
window and ABox information from [
Unfolding of the RANF formula yields to the algebraic query in Formula 3. fhig – wid;aid;s( x>y( i<j ( wid;aid;s;x(R) 1 wid;aid;s;y(S)))) (3)
In the next step, we replace the left part of the subtraction with the projection of the right side without making use of any specific selection.
wid;aid;s( wid;aid;s;x(R) 1 – wid;aid;s( x>y( i<j ( wid;aid;s;x(R) 1
wid;aid;s;y(S)) wid;aid;s;y(S)))) (4) Algorithm 1 (Translation from RANF to Algebra) Input: a formula in modified RANF Output: an algebra query E equivalent to x = a R(e) !
! fhx : aig ^ ! if is x = x, then E
f ( wid;aid;x1;:::;xn ( F (R))) if is x = y, (with x, y distinct) then x=y(E ), if fx; yg
f ree( ) x=y(E x=y(E 1 x!yE ), if x 2 f ree( ) and y 2= f ree( ) 1 y!xE ), if y 2 f ree( ) and x 2= f ree( ) = : 0, then if is x 6= y, then x6=y(E ) if
E – (E
1 E 0 ), if f ree( 0) E – E 0 , if f ree( 0) = f ree( )
f ree( ) otherwise, E
1 E does not have “and” as parent) : 1 _ ::: _ n 9x1,...,xn (x1,...,xn, y1,...,ym) ! fhig – E (if : ! E [ ::: [ E !
wid;aid;y1 ;:::;yn (E )
Finally, we arrive at an algebraic query transformed from the STARQL Having Clause in formula 4, which can now directly be written in SQL.
This algorithm has been implemented in the stream query answering prototype of the EU Optique project. A detailed description and evaluation of several examples will be presented in future work. 3
In this paper we have shown how we transform the Having Clause of the stream and temporal query language STARQL in general and described a specific example. The transformation is done by three steps. First, we guarantee the domain independence of STARQL by the Safe Range Normal Form. Second, we build the Relational Algebraic Normal Form and third, we transform the formula into an algebraic query. This algorithm has been implemented in the EU project Optique and will be evaluated and optimized in future work.