Temporal Predicates

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

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:

  • 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.
  • 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
OVERLAPS
EQUALS
PRECEDES
SUCCEEDS
IMMEDIATELY PRECEDES
IMMEDIATELY SUCCEEDS
LEADS
LAGS
STRICTLY CONTAINS
STRICTLY OVERLAPS
STRICTLY PRECEDES
STRICTLY SUCCEEDS
STRICTLY LEADS
STRICTLY LAGS
IMMEDIATELY LEADS
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
MEETS IMMEDIATELY PRECEDES
MET BY IMMEDIATELY SUCCEEDS
INCLUDES STRICTLY CONTAINS
DURING STRICTLY OVERLAPS
BEFORE STRICTLY PRECEDES
AFTER STRICTLY SUCCEEDS
OVERLAPS STRICTLY LEADS
OVERLAPPED BY STRICTLY LAGS
FINISHED BY IMMEDIATELY LEADS
STARTED BY IMMEDIATELY LAGS
FINISHES Reverse the order of the arguments and apply IMMEDIATELY LEADS.
STARTS Reverse the order of the arguments and apply 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 AND P2 (s,e) CONTAINS P1 AND (s,e) CONTAINS P2
P1 DURING (0 SEQ 6) (s,e) CONTAINS P1
NOT(P3).[P1,P2] NOT( (P1.s, P2.e) CONTAINS P3)
P1 FINISHES P2 P2 IMMEDIATELY LEADS P1