On event semantics -- my talk in the event-based multimedia workshop

Still in Barcelona for the event-based multimedia workshop.   I still need to write on the second day and the closing panel (in which I also participated), and my impression about the event-based multimedia community.

Meanwhile -- I have uploaded my presentation to slideshare, parts of it is reuse of other presentation (e.g. the slides explaining the notion of context),  the new stuff is about the semantics -- who are the players in the event game.    I am planned to give a long tutorial on event modeling in ER 2013 next month - stay tuned. 

The semantic overload of derived events

The term "derived events" is frequently used in the event processing terminology.  Here is an example taken from the Gigaspaces Blog of using the term "derived event".    Recent discussion with somebody who is just learning the event processing area, made me realized that we overload the term "derived event".  On one hand we define event as "something that happens", and say that a derived event is an event, thus one may assume that derived events also happen.    However, the way this term is typically used has some semantic overloading.   There are actually different types of derived events.

One type of derived event is really an event that we did not observe directly, but concluded that it happened by observing other events.  Such cases is the case of fraud detection, money laundering detection and system problem diagnostics.   

Another type of derived event is a notification.   We are doing a calculation based on events and the result is notified to some person of application.  For example: derived event that calculates the highway fees, based on exit and entry events on the highway, and rate calculated by load on the highway.   This is a derived event, however - it does not really stands for something that happens, the happening here is a notification to the driver how much the fees are,  there are many derived events of this type.

The question is whether we should make distinction between the two cases. From semantic point of view they are clearly distinct.    From execution model and language point of view -- they are indistinguishable; both take events as input, apply some assertions and functions over a collection of event, and create a structured message sent on some channel.    From semantic point of view there is a difference,  the question is from pragmatic point of view, is this distinction important for somebody that takes any role in the life-cycle of the application.   More -later.

On context and punctuation

This illustration is taken from the EPIA book and shows the notion of context as a first class construct that groups together events that need to be processed together, where each of its instances is processed as a single unit,  context may have temporal aspects, segmentation aspects, spatial aspects, and state-oriented aspects, and the actual context instance may be combined of one or more aspects.  

Recently I had some discussion with somebody from the data stream community who was in the opinion that the stream oriented way to do it is more simple since they are based on standard thinking (i.e. SQL).

In the stream research literature, the temporal context is divided between windows and punctuation, all the other aspects are somehow expressed by the group-by construct.    I guess that windows and group-by constructs are familiar to many people, punctuation is less familiar, thus I'll explain the idea briefly. 

A good source to learn about punctuation is Peter Tucker's site, from where the illustration below is copied:

Peter Tucker has done his PhD (under the supervision of Dave Maier) on data stream punctuation;  the idea of punctuation is to enable creating sub-streams, since a stream by definition is infinite.   The notion of windows in classical data stream models consists of variations of sliding windows, either by event count, or time, however, in reality there is a need to explicitly end stream, i.e. when the bid ends.  The definition of 
punctuation in the database encyclopedia (the value was written by Maier and Tucker) says:

In other words,  this is a "dummy event" put into the stream to denote the end of a sub-stream.  


Now the question is whether using windows + punctuation + group-by is indeed simple.    The relational model's claim to fame is its simplicity, however, from early days of the relational model, it has been realized that there are semantic anomalies, and all the normalization rules came to resolve those anomalies, yet, the overall model has been simple.  However, this is not really true for the extension of the relational model for streams,  while the relational model has a single entity: relation,  the extension has multiple entities: relation, stream, window.  Punctuation is a kind of trying to add semantics as a kind of logical patch.  


IMHO, the context model is semantically cleaner.  It has a single semantic notion for all the constructs that determine how to group event together (in the stream terminology, create sub-streams).   In the context model  there are no dummy event; the notion of temporal context (window) can also support event intervals - time windows that start by event and end by event; the events that start and end the window are real events, and can be used for other purposes.  Moreover, looking at the definition of punctuation above, it defines the end of a sub-stream, but assumes that the next bid starts when a new bid event arrives.  However, if we look at a situation where bids have not only "end bid" events, but also "start bid" events, then we would like to ignore bids that arrive when no bid is open,  and this has no natural representation, and has to be implemented with tricks, so we also need the equivalent of  "start sub-stream punctuation".   So, we view this as kind of context based on , and not as kind of event within the stream with a special semantics. 


The model we presented in EPIA (which we keep evolve)  to be a semantic model that provides abstractions above the current implementations of both event and stream processing systems;  several product owners have already told us that they use concepts from the book as inspiration to next versions of their products, and I guess that full implementation that is based on this model as native is yet to come.   

More on the semantics of synonyms

Still lazy days of the holiday week, I took advantage of the time to help my mother, who decided that she wants to leave home and move to seniors residence located 10 minutes walk from my house, this requires to deal with many details, so that is what I was doing in the last three days.... In the picture above (taken from the residence site) you can see the front entrance and the view seen from the residence tower, on the right hand side of the upper picture one can see part of the neighborhood we are living in (Ramat Begin) surrounded by pine trees all over.

Now, holiday eve again, and this is a good time to visit the Blog again. Last time I started the discussion in the semantics of synonyms by posing a simple example of conjunction over a bounded time interval (same pattern that Hans Glide referred to in his Blog), and slightly different from the "temporal sequence" pattern.

In the previous posting I have posed the following example:

Detect a pattern that consists of conjunction of two events (order is not important) - e1, e2.
e1 has two attributes = {N, A}; e2 has also two attributes = {N, B} ; the pattern matching is partitioned according to the value of N (on context partitions I'll write another time).
For each detection, create a derived event e3 which includes two attributes = {N, C}; E3 values are derived as: E3.N := E1.N ; E3. C = E1. A * E2. B.

Let's also assume that the relevant temporal context is time-stamps = [1, 5] - and the events of types E1 and E2 that arrived during this period are displayed in the table below:




The question is: how many instances of event E3 are going to be created, and what will be the values of their attributes?

Looking at this example, for N = 2, there is exactly one pair that matches the pattern
E1 that occurs in timestamp 5, and E2 that occurs in timestamp 4, so E3 will have the attributes {N = 2, C = 24}. However, for N = 1 things are more complicated. If we'll take the set oriented approach that looks at it as "join" (Cartesian product), since we have 3 instances of E1 and two instances of E2, we'll get 6 instances of E3 with all combinations. In some cases we may be interested in all combinations, but typically in event processing we are looking for match and not for join -- that is the difference between "event-at-a-time" type of patterns and "set-at-a-time" patterns that is being used by some of the stream processing semantics. So what is the correct answer ? -- there is no single correct answer, thus what is needed is to fine tune the semantics using policies. For those who are hard-coding event processing, or using imperative event processing languages, this entire issue seems a non-issue, since when they develop the code for a particular case they also build (implicitly) the semantics they require for a specific case, however policies are required when using higher level languages (descriptive, declarative, visual etc...), policies are needed to bridge between the fact that semantics is built-in inside higher level abstraction, and the need to fine-tune the semantics in several cases. In our case we can have several types of policies:

Policies based on order of events - example:

For E1 - select the first instance; for E2 - select the last instance.
For E1 - select the last instance; for E2 - select the last instance

Policies based on values - example:

For E1 - select the highest 2 instances for the value of A ; for E2 select the lowest instance for the value of B.

These are examples only -- it is also important to select a reasonable default which satisfies the "typical case", so if the semantics fits this default, no more action is needed.

These have been examples only, in one of the next postings I'll deal with identifying the set of policies required in order to make the semantics precise.

On semantics of synonyms

Holidays time - and I had to spend time in replacing my home wireless router (not of the same firm that is shown in the picture) who did not work well - to get another expensive one, whose signal is not received well in the lower floor well -- I hate wasting my time on restore things to work, this is never-ending story, every time something else need fix... we need more robust appliances..

Well - back from my personal frustrations to event processing thinking. I have posted a couple of postings about the different possible interpretations of "event_1 occurs before event_2", however, different interpretations are not unique to temporal issues, and the specific anomaly of having different temporal semantics. Let's take a case in which time does not matter - the function defined this time as follows:
Detect a pattern that consists of conjunction of two events (order is not important) - e1, e2.
e1 has two attributes = {N, A}; e2 has also two attributes = {N, B} ; the pattern matching is partitioned according to the value of N (on context partitions I'll write another time).
For each detection, create a derived event e3 which includes two attributes = {N, C}; E3 values are derived as: E3.N := E1.N ; E3. C = E1. A * E2. B.

Let's also assume that the relevant temporal context is time-stamps = [1, 5] - and the events of types E1 and E2 that arrived during this period are displayed in the table below:

The question is: how many instances of event E3 are going to be created, and what will be the values of their attributes? Think about it -- I'll discuss it next week.

More on semantics and race conditions

In previous posting I have posed the following sceanario:

Given the simple application shown below:

• There is a single event source (so no clock synchronization issues) which generates events of three types e1, e2, e3.


• Let's also say that in our story there is a single events of each type that is published (so no synonyms issues), the table shows their occurrence time (when they occurred in reality) and detection time (when they have been reported to the system) - each of them has been reported 1 time unit after its occurrence, no re-ordering problem.


• Events e1, e2 serve as an input to an EPA of type "pattern detection" which detects a temporal sequence pattern "e1 before e2", and when this is detected, it derives an event e4 - some function of e1 and e2.


• Events e3 (raw event) and e4 (derived event) serve as input to another EPA of type "pattern detection" which again detects a temporal sequences pattern "e3 before e4", if this pattern is detected - create event e5 which triggers some action in the consumer.

I also asked the question is -- given the above - will the action triggered by e5 occur?, i.e. will the pattern - "e3 before e4" be evaluated to true?

I got a few answers to this and you can read them as comments to the original posting; as promised I am dedicating this postings to analysis of this simple case:

The first thing to discuss is the semantics of "temporal sequence". There are two possible types of semantics for temporal sequence, which I call "detection time semantics" and "occurrence time semantics".

• The detection time semantics is implemented in various languages and means that the temporal order is the order of the time-stamps in which the "event processing platform" detects that this event occurs; if there is a single thread of such detection, then the events are totally ordered, otherwise, there may be several events with the same "detection timestamp".
• The occurrence time semantics also implemented in various languages means that the temporal order is the order of the time-stamps that are provided as part of the event information, and designate - when this event happend in reality. There are some complexity of synchronization of time in multi-producer environment, however, in this example we assume a single producer (I'll write about multi-producer cases in another posting).
• Note that this two order relations may not be identical.
• There is also kind of hybrid solution ("total order semantics") -- the semantics is really "detection time" semantics, but in order to allow events that arrive a bit late to take their proper role, the events are queued at a buffer (and not considered as detected) until time-out to let "out of order" events to arrive and re-order the buffer, and then send the events according to the buffer order.

Getting back to the example - in the small table on the bottom left-hand side of the figure above, there are occurrence and detection times of e1, e2, e3. For e4 there is only detection time - e4 is different from {e1, e2, e3} by the fact that it is a derived event and not raw event like the other three. The question is "what is the occurrence time of a derived event" ? -- there is no clear answer for it - there are several possible answers:

• In the derived event case the occurrence time = detection time, since this event is not real event but a virtual one, thus, its source is the EPA that creates it, and it occurred when created. In our case it means that occurence-time (e4) = 4.
• Its occurence time is the occurrence time of the last event that completed the pattern - since the participating events in the creation of e4 are {e1, e2} and e2 was the last that completed the pattern, occurrence-time (e4) = occurrence-time (e2) = 2
• Interval semantics: The event e4 occurs in the interval in which all the participants occur, which is this case means occurrence-time (e4) = [1, 2].

The phenomenon of multiple semantic interpretations apply to various other semantic decisions in the semantic of event processing language, and the preferred solution is to provide the user with semantic "fine tuning" policies, under which the user can chose the desired semantics, instead of "hard code" a certain semantics (using the most common one as a default), this is one of the benefits of using COTS for event processing, since it is quite difficult to think about such issues when developing EP manuaully using conventional language.

The semantics of the second "temporal sequence" (e3, e4) is thus:

• According to "detection time" semantics -- both have detection-time of 4. As such the sequence condition is not satisfied. However, if we impose total order by a single thread, this may create race conditions between the two events. In this case it is recommended to use a consistent priority policy - either breadth first (the raw event always comes first) or depth first (the derived event always comes first) to ensure deterministic result.
• According to the "occurence time" -- it depends on the policy chosen, but according to all interprerations - e4 occurs before e3 - thus the temporal sequence is not satisfied.

Bottome line: the temporal sequence (e3, e4) is satisfied if:

• The temporal semantics is detection time
• It is implemented by total order
• The total order policy is "breadth first" - namely priority for the raw events.

In all other cases the temporal sequence will not be satisfied and the corollary action will not execute.

On Semantics and Race Conditions - introduction

In this Blog posting I'll touch upon an issue that requires some attention to the exact semantics.

I'll introduce the topic today -- wait a few days to see if there are comments - and then post the analysis of this case.

Given the simple application shown below:

Let's explain this simple example, since I would like to concentrate on a single issue, I'll simplify all other things to eliminate any noise.

• There is a single event source (so no clock synchronization issues) which generates events of three types e1, e2, e3.


• Let's also say that in our story there is a single events of each type that is published (so no synonyms issues), the table shows their occurrence time (when they occurred in reality) and detection time (when they have been reported to the system) - each of them has been reported 1 time unit after its occurrence, no re-ordering problem.


• Events e1, e2 serve as an input to an EPA of type "pattern detection" which detects a temporal sequence pattern "e1 before e2", and when this is detected, it derives an event e4 - some function of e1 and e2.


• Events e3 (raw event) and e4 (derived event) serve as input to another EPA of type "pattern detection" which again detects a temporal sequences pattern "e3 before e4", if this pattern is detected - create event e5 which triggers some action in the consumer.

The question is -- given the above - will the action triggered by e5 occur?, i.e. will the pattern - "e3 before e4" will be evaluated to true.

Before getting to the analysis -- I wonder what will be the results in current EP solutions:

1. The action will always be triggered.


2. The action will never be triggered.


3. The behavior is non-deterministic (sometimes yes and sometimes no)


4. Any other possibility (specify).

Please send it as a comment to this post, I'll publish an interesting analysis of this case next week.

Happy New Year.

On Event Processing Network and Situations - the semantic bridge

One of the challenges in building a semantic meta-language that captures event processing behavior is to bridge the gap between terms that are in different domains. I have written before about Situations following the CITT meeting, in which this term has been discussed. In fact, we have used the term "situation" in AMiT , we also called its core component the "situation manager" We used the term situation to denote a meta-data entity the defines combination of pattern and derivation, but I must admit that this has been a mismatch of terms, although there is a strong correlation among these terms.

First - let's go back to the operational world, in this world events are flowing within event processing networks, in the EPN there are agents of various types: simple (filtering), mediating (transformation, enrichment, aggregation, splitting), complex (pattern detection) and intelligent (uncertainty handling, decision heuristics... ), in the roots of the network there are producers, and in the leaves of the network there are consumers. This is an operational view of what is done, the term "situation" is in fact, not an operational term, but a semantic term, in the consumers' terminology and can be defined as circumstances that require reaction.

How can we move from the operational world to the semantic world - we have two cases here:

• Deterministic case: there is an exact mapping between concepts in the operational world and the situation concept;
• Approximate case: there is only approximate mapping.

In order to understand it, let's take two examples:

Example 1 - toll violation (determinstic, simple)

• The cirumstance that require reaction is the case that somebody crosses a highway toll booth without paying (in Israel the only toll highway is completely automatic, but we'll assume that it occurs elsewhere, and that the toll is not applicable between 9PM - 6AM and in weekends).
• Getting it to the operational domain - there are two cases - one: go in the EZ pass lane and don't pay, two: go in a manual lane and somehow succeed to cross the barrier (obstacle?) without paying.
• The action in both cases: apply camera to capture the license plate, SMS the picture to officer on duty in the other side of the bridge.

From the EPN perspective, we have events of car cross a certain section of the road (the raw event), the EZ pass reading is an attribute of this event, and if no EZ pass it gets a "null" value. There is context information which is --- temporal (it is in hour and day where toll is in effect), spatial (the location of EZ pass lane), note: sometimes people mix the notion of context with the notion of situation, I have explained the difference in the past. Within this context a filter agent that looks for null value in the EZ pass reading is applied, if the filter agent evaluates to true then the situation phrased has been applied in deterministic way, and indeed the edge going out of the filter agent is going directly to a consumer (the camera snapshot may or may not be considered as part of the EPN). This is a case of "simple event processing", stateless filtering, whose output is a situation. This gives a counter example to the misconception that situation is closely related with complex event processing [I can continue the example to the other case, but I think that you got the point by now]

Example 2 - Angry Customer (approximate, complex)

The setting is a call center, the situation is -- detect an angry customer -- refer him or her to the "angry customers officer".

Here the life is not that easy, a human agent can detect angry customers by the tone of their voice (or electronic message), but this does not include all cases of angry customers, so we can look at some pattern saying -- a customer that applied 3rd time in a single day is an angry customer, and then we need to have a "pattern detection" agent that detects the pattern "3rd instances of application" where the context partition refers to the same date, same customer, same product. In this case also a leaf edge is mapped to a situation, but there are two differences from the previous case:

1. The agent is now complex event processing agent since it detects pattern in mu;tliple agents;

2. The edge represents the situation in an approximate way, which means that it can have false positives (the CEP pattern is satisfied but the customer is not really angry, just asked for a lot of information to install the product), or false negatives (the customer called twice, and does not talk in an aggressive tone, yet he is furious).

In some case it also makes sense to associate "certainty factor" with the leaf edge, approximating the measure of belief in the fact that this edge represents the situation. I'll leave the discussion about uncertain situations to another time.

On the first class citizens of enterprise computing

These are the citizens of hawktown, chosen to start this Blog posting. The issue of first class citizens has been discussed recently by Paul Vincent in a recent Blog posting that also cites Forrester's Blog on the four classical elements : Process, Services, Events and information.

This is interesting, since it presents events as first class citizens in the computing world. Paul asks whether CEP is a fifth element and proposes the following diagram.

In the introduction class that I am giving to my students in the event processing course I am showing a slide that explains how events relate to the rest of the universe, interestingly in this slide as first class citizens there are all the four elements identified by Forrester -- process, service, event and information, with addition of two elements - entity and context; entity is often considered to be hidden behind information which represents it, and context has not yet gained recognition as a first class citizen, although some analysts think it will become a first class citizen.

This illustration does not provide all connections among all elements, but it is an event-centric view of the universe, let's go briefly over the different connections of events to the rest of the universe:

1. Event can be related to another event - by various types of causality, by the fact that an event is included in a complex event, and by the fact that an event is a participant of the derivation function of a derived event (further discussion is here).

2. Event can be related to context - by the fact that it starts or ends context-instance, classified to context, and is created within a certain context.

3. Event can be related to service - by the fact that service can be either a producer or a consumer of an event, a service may emit events, and an event may be sent to a service, or even invoke a service.

4. Event can be related to process - by the fact that process state may be observed as event, while an event can affect (insert/modify/cancel) a process, or affect the orchestration of processes.

5. Event can relate to entity - by the fact that event references entities within a certain role; more semantic view of event processing can be done also according to relationships among entities.

6. Event has various relations to information -- it can be represented as a (kind of) information, a database operation by itself can be an event (like in active databases) and the result of derived events can be a database update action.

For Paul's question - how does CEP fit in? I agree that CEP touches all, but would not use Venn Diagrams to show the connections here.

• I view event, process, information, entity, service and context as conceptually different terms, thus there is no intersection between any two; There are relations between each pair.
• The main function of event processing is to process event, meaning take one or more events as input, do something (transform, enrich, aggregate, find pattern, derive...) and produce one or more events as output. Interestingly event processing has relations with all the six entities (I'll use EP instead of CEP, since I am using the CEP according to its glossary definition and not according to the "marketing" definition - see discussion here)

1. EP consumes and produces events.

2. EP executes within context that determines what will be executed.

3. EP can be wrapped as a service. Also EP interacts with services.

4. EPN is a kind of process - but cannot be managed by typical BPM tools due to the different scheme of routing, it can also interact with processes.

5. Entities are not explicitly part of EP, although some type of processing may also process dependencies among entities.

6. EP has various interactions with information - same as events.

Note that sometime conceptually there are activities on the borderline between event processing and other terms, for example - the action to determine what should be done with an event on the consumer side, can be done as part of EP system, or as part of the consumer software - depends on the level of coupling between them.

More - including discussion how does the term situation fits in this game - later.