Temporal Predicates

<< Click to Display Table of Contents >>

Navigation:  Streaming SQL Reference Guide >

Temporal Predicates

Previous pageReturn to chapter overviewNext page

This topic describes extensions to SQLstream's SQL dialect that let users express temporal relationships simply and elegantly, using new, standards-based syntax. Temporal predicates allow s-Server to perform what Esper and Etalis call “complex event processing” (CEP): “the analysis of complicated, long-running events.” A complicated, long-running event has a non-trivial duration. That is, it spans an interval of time rather than a single instant.

s-Server's temporal predicates let you query relationships between two time periods, using terms such as CONTAINS, OVERLAPS, PRECEDES, SUCCEEDS, and so on.

This page covers the following subtopics:

Advantages of s-Server Temporal Predicates

Overview of s-Server Temporal Predicates

Syntax of s-Server Temporal Predicates

Advantages of s-Server Temporal Predicates

SQLstream's approach to temporal predicates has two big advantages over competing approaches which use event processors modeled with rules-engines and state machine transitions:

1.SQLstream s-Server's query optimizer combines temporal predicates, relational operators, aggregates, and windowed expressions into compact programs which run efficiently on bare metal in a single processing step. In other words, the heavy lifting is done by the optimizer before the data starts flowing. As a result, s-Server runs queries faster, because it does not incur the queuing overhead associated with rules-based and state-machine-based solutions.
2.Because s-Server uses the widely-known SQL as a programming interface, new analysts and engineers face a short learning curve when using SQLstream s-Server. It takes considerably more time to master the proprietary programming models of rules-based and state-machine-based solutions. That, in turn, limits the number of problems which those approaches can solve under a tight deadline.

Overview of Temporal Predicates

SQL 2011 introduced the concept of a period, a time interval with a precise start point and a fuzzy end point. A period represents the following time range:

startTime <= time < endTime

 

The 2011 Standard also introduced a number of temporal predicates to describe the relationship between two time intervals: CONTAINS, OVERLAPS, EQUALS, PRECEDES, SUCCEEDS, IMMEDIATELY PRECEDES, and IMMEDIATELY SUCCEEDS. Here is an example of how SQL 2011 expresses a temporal relationship:

PERIOD (T1.startTime, T1.endTime) CONTAINS

PERIOD (T2.startTime, T2.endTime)

 

The table below describes the meaning of these new predicates in greater detail. We will implement all of them. In addition, we will implement the following extensions to the Standard, also described below:

LEADS - A predicate meaning “the left period begins before the right period.”

LAGS - A predicate meaning “the left period ends after the right period.”

STRICTLY - A predicate qualifier meaning “the two periods neither begin nor end together.”

The following table depicts the meaning of the new predicates that we will  introduce. It shows the relationships that each predicate covers. Each relationship is represented as an upper interval and a lower interval with the combined meaning “upperInterval predicate lowerInterval evaluates to TRUE”. The first 7 predicates are described by SQL 2011. The final 10 predicates, shown in red, are SQLstream extensions to the Standard.

Predicate

Covered Relationships

CONTAINS

sqlrf_contains

OVERLAPS

sqlrf_overlaps

EQUALS

sqlrf_equals

PRECEDES

sqlrf_precedes

SUCCEEDS

sqlrf_succeeds

IMMEDIATELY PRECEDES

sqlrf_immediately_precedes

IMMEDIATELY SUCCEEDS

sqlrf_immediately_succeeds

LEADS

sqlrf_leads

LAGS

sqlrf_lags

STRICTLY CONTAINS

sqlrf_strictly_contains

STRICTLY OVERLAPS

sqlrf_strictly_overlaps

STRICTLY PRECEDES

sqlrf_strictly_precedes

STRICTLY SUCCEEDS

sqlrf_strictly_succeeds

STRICTLY LEADS

sqlrf_strictly_leads

STRICTLY LAGS

sqlrf_strictly_lags

IMMEDIATELY LEADS

sqlrf_immediately_leads

IMMEDIATELY LAGS

sqlrf_immediately_lags

For the sake of conciseness, we also introduce the following additional extensions

Compact chaining - If two of these predicates occur back to back, separated by an AND, then the AND can be omitted provided that the right interval of the first predicate is identical to the left interval of the second predicate.
TSDIFF - This function takes two TIMESTAMP arguments and returns their difference in milliseconds.

The following expression

TSDIFF(s,e)

 

concisely means

CAST((e - s) SECOND(10, 3) * 1000 AS BIGINT)

Finally, SQL 2011 allows the CONTAINS predicate to take a single TIMESTAMP as its right hand argument. So the following expression...

PERIOD(s, e) CONTAINS t

 

is equivalent to

s <= t AND t < e

 

Syntax

Temporal predicates are integrated into a new BOOLEAN valued expression:

<period-expression> :=

  <left-period> <half-period-predicate> <right-period>

 

<half-period-predicate> := 

  <period-predicate> [ <left-period> <half-period-predicate> ]

 

<period-predicate> :=

   EQUALS

 | [ STRICTLY ] CONTAINS

 | [ STRICTLY ] OVERLAPS

 | [ STRICTLY | IMMEDIATELY ] PRECEDES

 | [ STRICTLY | IMMEDIATELY ] SUCCEEDS

 | [ STRICTLY | IMMEDIATELY ] LEADS

 | [ STRICTLY | IMMEDIATELY ] LAGS

 

<left-period> := <bounded-period>

 

<right-period> := <bounded-period> | <timestamp-expression>

 

<bounded-period> := [ PERIOD ] ( <start-time>, <end-time> )

 

<start-time> := <timestamp-expression>

 

<end-time> := <timestamp-expression>

 

<timestamp-expression> :=

  an expression which evaluates to a TIMESTAMP value

 

where <right-period> may evaluate to a <timestamp-expression> only if

the immediately preceding <period-predicate> is [ STRICTLY ] CONTAINS

 

This Boolean expression is supported by the following new builtin function:

BIGINT tsdiff( startTime TIMESTAMP, endTime TIMESTAMP )

 

Returns: The value of (endTime - startTime) in milliseconds

 

Example

The following code records an alarm if a window is open while the air-conditioning is on:

CREATE SCHEMA "Test";

SET SCHEMA '"Test"';

 

create or replace pump alarmPump stopped as

 insert into alarmStream( houseID, roomID, alarmTime, alarmMessage )

 select stream w.houseID, w.roomID, current_timestamp,

                  'Window open while air conditioner is on.'

 from

         windowIsOpenEvents over (range interval '1' minute preceding) w

 join

         acIsOnEvents over (range interval '1' minute preceding) h

 on w.houseID = h.houseID

 where period(h.startTime, h.endTime) overlaps period(w.startTime, w.endTime);

 

Sample Use Case

The following example models a real-world use case in which a mobile phone service provider wants to detect cell towers that are dropping connections. The query involves the self-joining of an incoming stream of cell tower events, and uses a temporal predicate and a window size of 1 minute. The measured latency of this join is less than 1 millisecond:

create pump reconnectAlarmPump stopped as

 insert into alarmStream

 select stream

   l.eventStart, l.cellTowerID, l.mobilePhoneID, 'Suspicious re-connect event'

 from

   celltowerEvents over (range interval '1' minute preceding) l,

   celltowerEvents over (range interval '1' minute preceding) r

 where

   l.cellTowerID = r.cellTowerID

   and l.mobilePhoneID = r.mobilePhoneID

   and l.eventType = 1

   and r.eventType = 1

   and period(l.eventStart, l.eventEnd) precedes period(r.eventStart, r.eventEnd)

;

 

 

Comparison to Esper

Esper supports the 13 Allen relationships. The following table lists Esper predicates and the proposed SQLstream equivalents.

Esper Predicate

Proposed SQLstream Predicate

Covered Relationship

COINCIDES

EQUALS

sqlrf_equals

MEETS

IMMEDIATELY PRECEDES

sqlrf_immediately_precedes

MET BY

IMMEDIATELY SUCCEEDS

sqlrf_strictly_succeeds

INCLUDES

STRICTLY CONTAINS

sqlrf_strictly_contains

DURING

STRICTLY OVERLAPS

sqlrf_strictly_overlaps

BEFORE

STRICTLY PRECEDES

sqlrf_strictly_precedes

AFTER

STRICTLY SUCCEEDS

sqlrf_strictly_succeeds

OVERLAPS

STRICTLY LEADS

sqlrf_strictly_leads

OVERLAPPED BY

STRICTLY LAGS

sqlrf_strictly_lags

FINISHED BY

IMMEDIATELY LEADS

sqlrf_immediately_leads

STARTED BY

IMMEDIATELY LAGS

sqlrf_immediately_lags

FINISHES

Reverse the order of the arguments and apply IMMEDIATELY LEADS.

sqlrf_immediately_leads

STARTS

Reverse the order of the arguments and apply IMMEDIATELY LAGS.

sqlrf_immediately_lags

Comparison to Etalis

The Etalis EP-SPARQL query language supports a different set of compound relationships between intervals. Those relationships can be expressed with the basic Allen relationships and therefore they map onto our proposed SQLstream syntax as follows:

Etalis Syntax

SQLstream Syntax

(P1).3

TSDIFF(P1.startTime, P1.endTime) < 3

P1 SEQ P2

P1 PRECEDES P2

P1 AND P2

(s,e) CONTAINS P1 AND (s,e) CONTAINS P2

P1 OR P2

(s,e) CONTAINS P1 OR (s,e) CONTAINS P2

P1 DURING (0 SEQ 6)

(s,e) CONTAINS P1

P1 EQUALS P2

P1 EQUALS P2

NOT(P3).[P1,P2]

NOT( (P1.s, P2.e) CONTAINS P3)

P1 STARTS P2

P2 IMMEDIATELY LAGS P1

P1 FINISHES P2

P2 IMMEDIATELY LEADS P1

P1 MEETS P2

P1 IMMEDIATELY PRECEDES P2