When does a derived event actually happen? - (posting II)

In the previous posting I've shown some possible anomalies when dealing with derived events. The picture above shows a snowfall as a derived event, actually where I am located, in Haifa, this is a very rare event (once every 20 years for a few minutes). There are various types of derived event, this time I'll discuss derived events of two different patterns: sequence pattern, and time-out pattern.

Example 1: The pattern is: if a sequence of events E1 and then E2 occur, derive event E3.

Let's assume that event E1 occurs at 9:00 and arrives to the system at 9:02, and event E2 occurs at 9:30, and arrives to the system at 9:31. The derived event is derived by the system in 9:33. The question is when does event E3 occurs. One can think of three logical possibilities:

I: E3 occurs when it is produced in 9:33; the rationale: since it is a virtual event, it does not occur in reality, and exists only since it is derived by the system.

II: E3 occurs when the last event that triggers the pattern matching occurs, in this case, in 9:30; the rationale: the derived event occurs when the patterns conditions are satisfied in reality, and this occurs when E2 occurs.

III: E3 occurs over the interval [9:00, 9:30]; the rationale: the derived event occurs over the interval of all participating events.

Example 2: The pattern is time-out (absence event). Example: if there is no bid for an auction by the end of the auction time, derive an event "no bidders".

Scenario: A bid was issued in 9:00 and is valid for 2 hours, in 11:00 it is closed without any bidders, in 11:02 the system issues the derived event.

We have similar three alternatives here:

I: The no bidders event occurs in 11:02, the time that the derived event is issued.

II: The no bidders events occurs in 11:00, when the "bid close" event occurs, which completes the pattern.

III: The no bidders event occurs during the interval [9:00, 11:00] --- since the "absent" event relates to the entire interval.

Like some other cases, there is no single solution that fits all cases; and the actual semantics of a specific case is a matter of policies, we see here three policies, which seem to cover most cases, but not necessarily all, that's why there is a need also to enable explicit derivation of the occurrence time of a derived event, i.e. the value of the occurrence time itself can be computed and derived.

More about temporal issues -- later.

On temporal aspects of event processing

In the past I was involved in work on temporal databases, in the picture you can see a 1998 book about temporal databases that I co-edited with Sury Sripada and Sushil Jajodia. Although there were some attempts to create substantial extension to SQL with temporal capabilities, and move temporal databases to the mainstream. This did not work, and there are several reasons, the event processing area provides a second chance for these idea to come to the mainstream now, as event processing have strong relations to temporal issues. Bob Hagman from Aleri (former Coral8) has recently written some survey of implementation alternatives related to time aspects in the Aleri Blog. In the DEBS 2008 language analysis tutorial we had dealt quite briefly with the topic of time. Earlier this year I have written a chapter in the upcoming book of the book "Handbook of Research on Advanced Distributed Event-Based Systems, Publish/Subscribe and Message Filtering Technologies; edited by Annika Hinze and Alejandro Buchmann"

This chapter is entitled: "Temporal Perspectives in Event Processing".
Here is the chapter's main topics:

• Temporal dimensions: in temporal databases we dealt with the temporal semantics of a collection of snapshots (states), in event processing we deal with the temporal semantics of events (transitions). Are the temporal dimensions the same ? do they have the same semantics ?
• The "instantaneous" issue -- do event occur over a time-point or an interval, and if it is interval what does it mean from computational point of view ?
• Time granularity -- in temporal databases we introduced the term "chronon" which stands for the time granularity that makes sense for a particular use. This idea is also applicable to event processing, for different events, different chronons make sense.
  
• Temporal contexts: the term "time window" in stream processing is a kind of a temporal context. What kinds of temporal contexts are required, and what is the computational implications of them. I'll write more about contexts soon, as this is the topic of chapter 7 of the EPIA book.
• Temporal patterns: "complex event processing" is about finding patterns among collections of events; some (but not all) of these patterns are temporal in nature -- what are the temporal oriented patterns ?
• Temporal properties of derived events: An event processing system derives events as result of its processing. What is the time properties of the derived events? this is a rather tricky question that deserves a discussion.
• Ordering events: for some temporal patterns, knowing the order of events is important. What are the issues associated with keeping such an order, how out-of-order events should be handled ?
• A related issue is "retrospective events" -- what happens if events that relate to the past are detected, where the assumption that they did not occur already triggered some processing ?

• Issues of time in distributed environment -- clock synchronization, time-zone handling, time validity for mobile clients --- are all applicable for event processing.

As written, this is an outline of topics surveyed at that chapter, I'll write more about some of them in the future.