The paper contributes to the recent efforts on temporalizing and streamifiying ontology based data access (OBDA) by discussing aspects of rewritability, i.e., compilability of the TBox into ontology-level queries, and unfoldability, i.e., transformability of ontology-level queries to queries on datasource level, for the new query-language framework STARQL. The distinguishing feature of STARQL is its general stream windowing and ABox sequencing strategy which allows it to plugin well known query languages such as unions of conjunctive queries (UCQs) in combination with TBox languages such as DL-Lite and do temporal reasoning with a sorted first order logic on top of them. The paper discusses safety aspects under which STARQL queries that embed UCQs over DL-Lite ontologies can be rewritten and unfolded to back-end relational stream query languages such as CQL. With these results, the adoption of description logic technology in industrially relevant application areas such as industrial monitoring is crucially fostered.
The work described in this paper is part of recent efforts on streamifying OBDA
[
Stream window operators play an important role also in the new query language framework STARQL (Streaming and Temporal ontology Access with a Reasoning-based Query Language, pronounced Star-Q-L, [17,16]). Its framework character relies in the facts that 1) it can embed queries of various query languages, 2) refer to ontologies in various DL languages, and 3) use a first order ? This work has been supported by the European Commission as part of the FP7 project Optique. logic (FOL) fragment for temporal reasoning over ABox sequences constructed within the query. In this paper, we focus on the latter aspect assuming for the first two unions of conjunctive queries (UCQs) w.r.t DL-Lite ontologies.
In STARQL, the idea of processing over windows is pushed further by
extending these with sequencing operators that set up at every time point a finite
sequence of ABoxes on which temporal reasoning can be applied. STARQL does
not assume a stream of ABoxes which hold universally but rather
modifies/exploits the given ABox streams to build its own stream of finite ABox sequences.
This sequencing strategy, among other things, distinguishes STARQL from the
approaches in [
In this paper, we consider an instantiation of STARQL where Intra-ABox reasoning within sequences is handled by answering UCQs over DL-Lite ontologies w.r.t. the certain answer semantics. (Which logic from the DL-Lite family to choose does not matter, as long as it allows for FOL rewriting.) Within InterABox reasoning certain answers from the different ABoxes are related and constrained with an outer temporal FOL formula. This is challenging if one allows in the FOL template negation, disjunction and all quantifiers in combination with concrete domains, as these, if not constrained, would immediately lead to infinite sets of answers, in particular w.r.t. concrete domain values.
STARQL uses a new adornment technique for variables to guarantee
safeness. We demonstrate the safety mechanism which will guarantee that the FOL
template language is domain independent [
We describe the syntax and the semantics for a fragment of STARQL (see [17] for the full version).
Our running example for illustration purposes is a measurement scenario in which there is a (possibly virtual) stream SMsmt of ABox assertions. Its initial part, called SM5smst here, contains timestamped ABox assertions giving the value of a temperature sensor s0 at 6 time points starting with 0s.
SM5smst = fval (s0; 90 )h0si; val (s0; 93 )h1si; val (s0; 94 )h2si
val (s0; 92 )h3si; val (s0; 93 )h4si; val (s0; 95 )h5sig Assume further, that a static ABox contains knowledge on sensors telling, e.g., which sensor is of which type. In particular, let BurnerT ipT empSens(s0) be in the static ABox. Moreover, let there be a pure DL-Lite TBox with additional information such as BurnerT ipT empSens v T empSens saying that all burner tip temperature sensors are temperature sensors.
We want to formalize the following information need: Starting with time point 0s, output every second those temperature sensors whose value grew monotonically in the last 2 seconds. A possible STARQL representation of the information is illustrated in the following listing.
CREATE STREAM S_out AS CREATE PULSE AS START = 0s , FREQUENCE = 1s SELECT { ?s rdf : type MonInc }< NOW > FROM S_Msmt [ NOW -2s , NOW ] - >1 s USING STATIC ABOX < http :// Astatic >, TBOX < http :// TBox > WHERE { ?s rdf : type TempSens } SEQUENCE BY StdSeq AS SEQ HAVING FORALL i < j IN SEQ ,?x ,? y:
IF ({ ?s val ?x }<i > AND { ?s val ?y }<j >) THEN ?x <= ?y Syntax The example demonstrates much of the syntactical possibilities within STARQL whose grammar is sketched in Fig. 1. The rules for the HAVING clause are not given there but are discussed in more in the following sections.
After the create expressions for the stream and the output frequency the
queries’ main contents are captured by the select expressions. The head of the
select expression describes the output format of the stream giving a RDF basic
graph pattern (BGP) with an attached time expression, here < N OW >, for
the evolving time. The general motivation for this approach is similar to the
CONSTRUCT operator in the SPARQL query language. So the actual result in the
monotonicity example is a stream of ABox assertions of the form M onInc(s0)hti.
Sou5ts = fM onInc(s0)h0si; M onInc(s0)h1si; M onInc(s0)h2si; M onInc(s0)h5sig
Within the WHERE clause one can bind variables w.r.t the KBs mentioned in the
USING clause by using UCQs. We assume an underlying DL-Lite Logic for the
static ABox, the TBox and the UCQs which allows for concrete domain values,
e.g. DL-LiteA [
The heart of the STARQL queries is the window operator in combination with the sequencing mechanism. In the example, the operator [NOW-2s, NOW]->1s describes a sliding window operator, which collects the timestamped ABox assertions in the last two seconds and then slides 1s forward in time. Every temporal ABox produced by the window operator is converted to a sequence of (pure) ABoxes. At every time point, one has a sequence of ABoxes on which temporal (state-based) reasoning can be applied. This is realized in STARQL by a sorted first order language template in which timestamped UCQs conditions (notated here as BGP) are embedded. In the example above, the HAVING clause expresses a monotonicity condition stating that for all values ?x that are values of sensor ?s w.r.t the ith ABox and for all values ?y that are values of the same sensor ?s w.r.t. the jth ABox, it must be the case that ?x is less than or equal to ?y. createExp pulseExp selectExp ! CREATE STREAM name AS [pulseExp] selectExp j pulseExp ! CREATE PULSE AS START = startTime; FREQUENCE = freq ! SELECT selectHead(x; y) FROM listWinStreamExp [USING listOfRessources] WHERE whereClause(x)
SEQUENCE BY seqMethod [HAVING safeHavingClause(x; y)] selectHead (x; y) listWinStreamExp ! sparqlTriple(x; y) <time1> . fselectHead (x; y) <time2> g ! (name j selectExp)windowExp[ , listWinStreamExp] windowExp listOfRessources typedRessourceList ! [ timeExp1 ; timeExp2 ]->slideConst ! typedRessourceList [ , listOf Ressources] ! STATIC ABOX listofURIstoStaticABoxes j
TEMPORAL ABOX listofURIstoTemporalABoxes j TBOX listofURIstoTBoxes
(x) (with (x) a UCQ with distinguished variables x) whereClause(x) ! seqMethod ! StdSeq j SeqMethod ( ) Semantics STARQL queries have streams of ABox assertions as input and output. That means that the definition of the semantics for STARQL has to explicate how the output stream of ABox assertions is computed from the input streams. Using the compositionality principle, the semantics definition for SPARQL can be accomplished by defining the semantic denotations for the substructures of the query (be it subqueries or other data structures) and then by composing them to the denotation of the whole query. We are going to sketch the semantics of the window operator, of the sequencing, and of the HAVING clause.
A stream of ABox assertions is an infinite set of timestamped ABox assertions of the form axhti. The timestamps stem from a flow of time (T; ) where T may even be a dense set and where is a linear order. Let S be a stream name with its denotation JSK being such a stream of timestamped ABox assertions. We declare the denotation of the windowed stream ws = S winExp = S [timeExp1 ; timeExp2 ]->sl as a stream of temporal ABoxes, where a temporal ABox is a set of timestamped assertions.
Let t:g1(t) = JtimeExp1K and t:g2(t) = JtimeExp2K be the functions corresponding to the time expressions. The pulse declaration defines a subset T 0 T of the time domain. T 0 is the set of timestamps of the stream of temporal ABoxes JwsK. Let T 0 be represented by the increasing sequence of timestamps (ti)i2N, where t0 is the starting point fixed in the pulse declaration.
Now, one defines for every ti the temporal ABox Ati such that (A~ti ; ti) 2 ~ JwSK. If ti < sl 1, then A~ti = ;. Else set first tstart = bti=slc sl and tend = maxftstart (g2(ti) g1(ti)); 0g, and define on that basis ~ Ati = f(ass; t) j (ass; t) 2 JSK and tend t tstartg So in the example above, timeExp1 = N OW 2s, timeExp2 = N OW and sl = 1s; the example’s results for second 4s and 5s are the following.
Time Temporal ABox 4s fval (s0; 94 )h2si; val (s0; 92 )h3si; val (s0; 93 )h4sig 5s fval (s0; 92 )h3si; val (s0; 93 )h4si; val (s0; 95 )h5sig If the STARQL query refers to more than one stream, than these are joined by timewise union of the temporal ABoxes of the windowed streams, which is possible as the pulse declaration synchronizes all streams of temporal ABoxes.
The stream of temporal ABoxes is the input for the sequencing operator which produces for every time point of the pulse a sequence of (pure) ABoxes. The sequencing methods used in STARQL refer to an equivalence relation to specify which assertions go into the same ABox. The equivalence classes [x] for x 2 T form a partition of T . We restrict the class of admissible equivalence relations tho those that respect the time ordering, i.e., the partition of equivalence classes should be convex intervals on the time domain.
Now, we define the sequence of ABoxes generated by seqM ethod( ) on the stream of temporal ABoxes as follows: Let (A~t; t) be the temporal ABox at t. Let T 0 = ft1; : : : ; tlg be the time points occurring in A~t and let k the number of equivalence classes generated by the time points in T 0. Then define the sequence at t as (A0; : : : ; Ak) where for every i 2 f0; : : : ; kg the pure ABox Ai is
Ai = faxht0i j axht0i 2 A~t and t0 in ith equivalence classg In the example above, the equivalence is the identity (keyword StdSeq for standard sequencing), so that the resulting sequence of ABoxes at time point 5s is trivial as there are no more than two ABox assertions with the same timestamp: fval (s0; 92 )gh0i; fval (s0; 93 )gh1i; fval (s0; 95 )gh2i.
STARQL’s semantics for the HAVING clauses relies on the certain answer
semantics (see [
As demonstrated with the monotonicity example, STARQL allows a sorted FOL
to reason on the ABox sequences. The semantics for the HAVING clauses rests on
the structure It whose domain It does not consist only of the individual and
value constants in the interpretations of the relations, the so called active domain
according to database terminology [
Figure 2 contains the grammar for the HAVING clause language with its safety mechanism realized by variable guards/adornments. The safe having clauses (denoted by safeHavingClause, which is the start symbol of the grammar) contain only those variables for individuals that have guard status +. We illustrate the meaning of the rules with Rule (1) for the OR case and then go in more detail w.r.t. adornments.
hCl (zg1_g2 ) ! hCl (zg1 ) OR hCl (zg2 ) (1) A having clause hCl may be constructed as (produces) a disjunction of two having clauses under some conditions on the variables occurring in them. If during production a clause hCl (zg) with variables z and some adornment g for them is reached, then Rule (1) justifies the production of hCl (zg1 ) OR hCl (zg2 ) if the adornment g can be represented as g = g1 _ g2, i.e., if g is the result of applying a function _ on the adornment lists g1; g2.
The adornments g = g1; : : : ; gn are lists of guard status gi (g-status for short), where gi 2 f+; ; ; ;g. We use zg as an abbreviation for z1g1 ; : : : ; zngn where z = z1; : : : ; zn and g = g1; : : : ; gn. We assume the ordering ; + on the guards. This ordering is relevant for the calculation of gmax in the rule of Fig. 2 where the clause is constructed from an arbitrary clause hCl and an identity atom. The special case of gi = ; is a convenience notation meaning for x; that x does not occur at all in the formula.
The meanings of the functions :; _; ^; ! over vectors of g-status are fixed by the tables in Figure 3. Combinations with the g-status ; is handled in an extra table 3b. So for example, assume that one has produced a HAVING clause F (x1 ; x2+; x3 ), where x1 has g-status , x2 has g-status +, and x3 has g-status . Then rule (1) and the tables allow, e.g., the production of F1(x1 ; x2+; x3 ) OR F2(x1+; x2+; x3;). Let us verify this for the variable x1: Its gstatus in F1 and its g-status + in F2 combines to the g-status = _+ in F—according to the entry for the pair ( ; +) in the table of _.
Now, we will show how to transform HAVING clauses to the relational algebra (SQL). In particular this will show that the HAVING clause language is domain independent as relational algebra is domain independent. For a formula F let SRN F (F ) be the formula in safe range normal form (SRNF) [1, S.85] resulting from applying the following normalization rules – Rename variables such that no variable symbol occurrence is bound by different quantifiers and such that no variable occurs bound and free – Rewrite IF F THEN G to NOT F OR G. – Eliminate double negations – Eliminate FORALL quantifiers by FORALL z ; NOT EXISTS z NOT. stateArithAtom(ig11 ; ig22 ) stateArithAtom(ig11 ; ig22 ; ig33 ) stateAtom(x ; y ) stateAtom(x+) term(i+) ! i
term() ! max j 0 j 1 stateAtom(y+; i+) ! (x; y) <i > (for a UCQ (x; y) and x X, y V arind [ V arval n X) ! x = y (for y; x 2= X [ V arval) ! x = a j a = x
(for a 2 (X \ V arind) [ Constconst, x 2 V arind n X) vAtom(z1+) ! z1 = v j v = z1
(for z1 2 V arval n X and v 2 Constval) vAtom(z1+) ! z1 = z2 j z2 = z1
(for z1 2 V arval n X, and z2 2 X \ V arval) vAtom(z1 ; z2 ) ! z1 op z2
(for op 2 f<,<=, >, >=, =g; z1; z2 2 V arval n X) vAtom(z1 ) ! z1 op z2 (for op 2 f<,<=, >, >=g, z1 2 V arval n X, z2 2 V alconst [ (X \ V alvar) ! term1(ig11 ) op term2(ig22 )
(for op 2 f<,<=, =, >, >=g) ! plus(term1(ig11 ); term2(ig22 ); term3(ig33 )) hCl (zg) hCl (zg1_g2 ) hCl (zg1^g2 ) hCl (z1gmax ; z2gmax ; z3g3 )
hCl (z:g) hCl (zg1!g2 ) hCl (zg1!g2 ) hCl (zg1^g2 ) ! stateAtom(zg) j vAtom(zg) j stateArithAtom(zg) ! hCl (zg1 ) OR hCl (zg2 ) ! hCl (zg1 ) AND hCl (zg2 ) (both conjuncts are
not of form x = y for x; y 2 V arind [ V arval) ! hCl (z1g1 ; z2g2 ; z3g3 ) AND z1h1 = z2h2
(for gmax = maxfg1; g2; h1; h2g) ! NOT hCl (zg) ! IF hCl (zg1 ) THEN hCl (zg2 ) ! FORALL y IF hCl (zg1 ; y+) THEN hCl (zg2 ; yg) ! EXISTS y hCl (zg1 ; y+) AND hCl (zg2 ; yg) + + + + + + + + + + + + + + + + g1 g2 g1 ^ g2 g1 _ g2 g1 ! g2 ; ; + ; + ; ; ; + + (a) Variables existent in both subformulas (b) Variable missing in one subformula Please note that these rules are applied in some order until they cannot be applied anymore. A formula F is said to be in SRNF iff F = SRN F (F ).
Domain independence for formulas in SRNF are handled in the literature [
A formula F in SRNF is called range restricted iff f ree(F ) = rr(F ) and no subformula returns ?. A well known theorem states that range restricted formulas in SRNF are exactly as expressive as relational algebra—which is known to be domain independent. Hence it is well known that safe range formulas are domain independent (in particular all sets of answers are finite).
Relating our set of g-status with the set of g-status used in [
Theorem 1. All safe HAVING clauses (considered as queries on the DB It of certain answers within the actual ABox sequence at t) are domain independent.
Let saf ehCl(u+) be a safe HAVING clause. Let saf ehClN F (u) be the formula resulting from applying the SRNF normalization rules. The status of all the guards are not changed by the rules. Now, we see that for all subformulas G(x+; y ; z ) in saf ehClN F (u) we have (*) rr(G) = x (= all variables in G with g-status +)
The proof of ( ) is by structural induction on construction of the formula saf ehcLN F (u). Let G(x+; y ; z ) be an atomic clause. Then rr(G) = x follows from looking at the adornments of the atomic clauses G in Fig. 2 and checking that only those with g-status + are in rr(G). Hereby, variables x 2 X, whereX is defined in the grammar, are treated as constants in the definition of rr( ). The case of conjunction is clear too as any + g-status combines with any other g-status to +. Now take negation G = NOT F (x+; y ; z ). The definition of rr for the negation case says rr(G) = ;. Actually we know that F is an atomic formula. Looking at all variables for these formulas in the grammar we see that no one of these as g-status , hence actually y = ; and we have G(x ; z ), so there is no variable in G with g-status +, hence indeed we get that rr(G) = ; = the variables in G with g-status +. The case for disjunction is clear as a positive g-status results for a variable in a disjunction only if both variables exists in the disjuncts and are labelled +. Now the last case is that of the exists quantifier G = EXISTS xF (x+; y ; z ). According to induction assumption rr(F ) = x. G may result from a transformation of an exists subformula EXISTS xhCl(x+; : : : ) AND F 0 in hcl(u+). So the variable x is by definition in the set x of variables in F with g-status +, hence rr(G) = rr(F )nfxg. But G does not occur as free variable in G, hence the set of variables in G with g-status + is actually x without x, which proves the induction claim. Now G may also result from applying somewhere the rule FORALL NOT EXISTS NOT. But again, there is a formula with variables that have g-status + and are bounded by the all quantifier so that one gets again a formula of the form EXISTS xhCl(x+; : : : ) AND F 0. 4
Having shown domain independence for the the HAVING clause language is the main step towards using STARQL for OBDA in the classical sense according to which queries on the ontology level are rewritten and unfolded into queries over the data source. Rewriting is done locally w.r.t. every ABox in the sequence, resulting in a new STARQL query. Hence we only discuss unfolding.
We illustrate how to unfold STARQL queries into CQL queries; CQL [
Following the classical OBDA approach we assume that the streams to which STARQL refers are produced by mappings. In our example, let be given a CQL stream of measurements M smt with schema Msmt(MID, MtimeStamp, SID, Mval). A mapping takes a CQL query over this stream and produces a stream of assertions of the form val(x; y)hti. val(x; y)hzi
SELECT Rstream(f(SID) as x, Mval as y, MtimeStamp as t) FROM Msmt[NOW]
The main challenge for unfolding STARQL is the new data structure of an ABox sequence, which is not representable in CQL. So we therefore that the STARQL queries use the standard sequencing only, so that from every state i in the sequence associated with tNOW one can reconstruct the timestamps of the tuples occurring in the ABox Ai. Moreover, we assume a default streamto-stream operator implemented into the CQL answering system and applied directly after every window-to-stream operator, transforming dhti to (d; t)hti.
The CQL query in the following listing is the unfolded pendant of the STARQL query. The outer WHERE clause is the pendant of the monotonicity formula expressed in the HAVING clause.
CREATE VIEW windowRelation as SELECT * FROM Msmt [ RANGE 2s Slide 1s ]; SELECT Rstream ( sensor , timestamp ) FROM windowRel , sensorRel WHERE sensorRel . type = ’’ BurnerTipTempSens ’’ AND NOT EXISTS (
SELECT * FROM ( SELECT timestamp as i , value as x FROM windowRelation ) , ( SELECT timestamp as j , value as y FROM windowRelation ) WHERE i < j AND x > y ); Experiments with our STARQL prototype (using a CQL like back end language) show correctness and completeness for a representative set of STARQL queries. Performance and scalability experiments are on our TODO list. 5
Much of the relevant work on stream processing has been done in the context of
data stream management systems (DSMSs), mainly with SQL-like stream query
languages such as CQL [
First steps towards streamified OBDA are C-SPARQL [
The semantical foundation of evaluating HAVING clauses is similar to that of
[
Safety conditions are considered in the classical DB literature [
Though not directly related to OBDA, other relevant work stems from the
field of complexed event processing. For example, EP-SPARQL/ETALIS [
The paper has presented a query framework lying in the intersection of classical OBDA and stream processing. The query language (necessarily) extends the sliding window concepts, which are known from many languages for relational stream data management systems as well as recent systems for RDFS, with ABox sequencing constructors. The advantage of using a sequence based methodology over other approaches are, first, that the sequence sets up a (nearly) standard context in which standard OBDA reasoning services can be applied, and second, that the query language can be equipped with a neat semantics based on the certain answer semantics for pure DL-Lite ABoxes (see [17]). Though the results in this paper show that ABox sequencing w.r.t. the standard sequencing strategy is syntactic sugar, it is not a redundant operator if non-standard sequencing strategies are used. For example, in many cases one does not want to handle (certain) answers over inconsistent ABoxes as these do not result in useful information. Hence, a non-standard sequencing strategy would only build ABoxes in the sequence that are consistent, so that only these are queried.
STARQL’s combination of sufficient expressiveness on the conceptual level with high expressiveness w.r.t. arithmetical, and statistical computations as well as event specifications can be implemented in a safe manner in order to reach domain independence. This lays the ground for a complete and correct transformation to streaming query languages on the backend data sources. 15. Krämer, J., Seeger, B.: Semantics and implementation of continuous sliding window queries over data streams. ACM Trans. Database Syst. 34(1), 1–49 (Apr 2009), http://doi.acm.org/10.1145/1508857.1508861 16. Özçep, O.L., Möller, R., Neuenstadt, C.: Obda stream access combined with safe first-order temporal reasoning. Technical report, Hamburg University of Technology (2014) 17. Özçep, Ö.L., Möller, R., Neuenstadt, C., Zheleznyakov, D., Kharlamov, E.: Deliverable D5.1 – a semantics for temporal and stream-based query answering in an OBDA context. Deliverable FP7-318338, EU (October 2013) 18. Phuoc, D.L., Dao-Tran, M., Parreira, J.X., Hauswirth, M.: A native and adaptive approach for unified processing of linked streams and linked data. In: International Semantic Web Conference (1). pp. 370–388 (2011)