On Event Stream Processing

This is in part a response to my friend and colleague Claudi for his recent post in the CEP Interest Group

There are many types of streams in the universe - the Gulf stream that affects the weather, a water stream who provide pastoral nature sight, and an audio stream, to name just a few.

In the event processing area the name "stream" appears first in the database research community, as a research project in Stanford. Interestingly the name "event" is never mentioned, and the term "data stream" is the central concept. The first one who made a blend of the "stream" concept and "event processing" concept is my friend Mark Palmer from Progress who did not like the "complex" word and thought that the term "event stream processing" will be more accepted, Mark certainly did not mean to talk about data streams in the academic sense. In the discussion session of the term event stream processing in Wikipedia

Mark writes:

ESP SHOULD GO AWAY AND I HELPED CREATE THE PROBLEM!!!

You are completely correct in my opinion; these should be merged. And I say this from the perpsective of the software vendor that popularized and caused the confusion in the first place. I'm the general manager of the Progress Apama software division and we coined the term "event stream processing" in April of 2005 when we acquired Apama for $30M - we didn't like the term "complex event processing" and decided to make up another term. Yes, stream processing, and data stream processing have been used as terms in academia, but we made up the term ESP as a synonym for CEP. Some on this list will argue that there are subtle, technical differences, but, being in the center of this quagmire of a debate, I think they should be merged, and that ESP should basically go away!
- Mark Palmer, General Manager, Progress Apama, mpalmer@PROGRESS.COM

Another indication of the blurring between ESP and CEP is that the vendor descendants of the academic projects - Streambase and Coral8 now positioned themselves as "complex event processing" vendors. Both have "complex event processing" all over their homepages, Streambase labels its product as - "complex event processing platforms" (well -- we'll discuss platforms in another posting); Coral8 has a portal which is offers self-service CEP. Aleri which also provides SQL oriented API, also uses the term CEP, although they are also using the term "Aleri streaming platform" as the way to do CEP. Thus, while the term "stream processing" is very much alive in the academic database community - see the VLDB 2007 program, for example, it seems that the market has already voted on the unification of these two terms, behind the CEP term.

Why did it happen ? - in the beginning we have seen some 2 x 2 matrices, showing that CEP is - complex and l0w-performance, while ESP is simple and high-performance. It does not seem that any vendor thought it is positioned in one of the extremes, since most applications are somewhat in the middle, and confusing the customers with two names from vendors who have competed on roughly the same applications and customers did not help any of the vendors, thus, the market wisely moved to one name (BTW - this name could have also been "event stream processing" as Progress suggested, but for some reason the term CEP has caught, and some potential customers are still nervous about the word "complex", but it got the traction nevertheless).

This has been until now discussion on branding, and did not answer the questions - whether there are real differences between ESP and CEP ? in some cases, people indicated theoretical differences, the most notable is: stream processing is ordered, while CEP is partially-ordered.

It may be true, though, I was never convinced that "total order" is an inherent property of stream, it is just the way it was happened to be defined in the academic projects, but I think that the more important difference is - whether we start from set-oriented thinking (stream processing) or from individual-event-oriented thinking (event processing), and there are pros and cons of thinking in each of them, but the bottom line is that real applications may be mixed, they may have ordered events from the same type (e.g. when we are looking at trends in time-series), or it can have unordered events of the same type (e.g. when we are looking at information from various sensors whose original timestamps may not be synchronized), in fact, it can have both in the same application. It is true that the space of CEP applications is not monolithic, but there are other classifications that are more useful then the classification of partial vs. ordered set, thus, for practical purposes, let's assume that "stream processing" as defined by those who are looking for the theoretical differences indeed covers a subset of the space of functionality, however - this subset is not important enough to have separate products covering it, or even to mention it as a sub-class.

Last but not least -- an answer to Claudi on his claim that there is not really a CEP engine, since none of the current products know how to obtain general relations among events and calculate transitive closures.

My answer is that event relationship definitions do exist, but this is not the main point, the point is that one may claim that "there is not really a CEP engine that contains all the possible language features that one can think of", and this is true, the EP discipline is young, and I am sure that we just scratched the surface, and EP products will include many features that we event did not think of them today (otherwise it is an indication that the area has failed!), however, without talking about a certain feature, CEP engines do exist today, none is perfect, but probably sufficient for big majority of the existing applications today, so theoretical perfection may not be the criterion to call something "CEP engine", we'll have to settle in "sufficient conditions"

I'll relate to relations among events, including transitive closure in another postings - but the way they exist or don't exist does not really matter for the question. Long posting today - so this is all for now.

On simple events and simple event processing

This is a picture I have borrowed from Siemens, however, I'll use it talking about simple events and simple event processing. There is a constant confusion around the terms "simple" (and "complex") here due to the ambiguity of the phrase: simple (complex) event processing - does it mean: processing of simple (or complex) events? or does it mean simple (or complex) processing in events. In this posting, I am drilling down to the simplicity notion.

Let's start with simple event - I prefer to contrast simple event with composite event where the contrast is in the structure - composite event is a collection of simple events and simple event is an atomic event, nothing said about the processing yet.

Now - is there different processing for simple events and composite events ? - in principle no - there are some functions on collections that are not applicable for atomic events, but if we take a collection of simple events that has not been concatenated we can apply the same processing for them.

Thus - my preference is to attach the simple to the processing and not to the event type, and define simple event processing as simple type of processing, no matter what the event structure is. What are the characteristics of simple event processing ?

• processing is done on a single event - not looking on other events, but events are processed "one at a time".


• only types of processing possible are: filtering and routing


• filtering decides whether this event should be passed


• routing decides to whom this event should be passed

Basic pub/sub with filtering is simple event processing.

ECA (Event-Condition-Action) rule is also simple event processing -- this does not say that the event cannot be derived/complex/composite - but regardless of the history of the event, its structure, the reason why it is created, and its source the ECA rule still performs a simple event processing, and processes one event at a time, where the condition provides filtering, and the action is indeed routing to somewhere to do this action.

Furthermore, in many cases, the "simple event processing" is a preamble to the event processing network done by the event producer, or post-processing done by the consumer, however, it can still be part of the Event Processing Network.

More related concepts - in the next postings.

On Event processing and Event Driven Architecture

As those who read this blog can notice, I use the term - "event processing" as the name of the discipline that this blog deals with. Other people are using the term EDA - "event driven architecture" as their key terms? one of the questions I was recently asked - are they the same, or similar like the two Arizona Moths that you can see in the picture above ? this, of course, depends on the exact meaning, and people do use them interchangeably.

In my opinions these terms are different.

EDA deals with the way components communicate, and in this case, unlike the request/response style, EDA is loosely coupled, asynchronous, and delivered via push.

Event Processing deals with the end-to-end processing of events, it may or may not be based on EDA. There are some cases that are EP, and are not EDA, examples:

• Event can be obtained in pull (periodically or on demand)
• Event can be part of transaction -and thus there is a dependency
• Event can be communicated to an event processor using request/response protocol, but the actual functionality is event processing.

(may be other reason).

So EP and EDA are not really identical...

On sources for uncertainty in Event Processing

There are various sources of uncertainties associated with event processing - here is an attempt to list some of them:

Uncertainties related to the source:

• Uncertainty that an event happened due lack of credible source, or inaccuracy in the source reporting (e.g. has the sensor really detected an object, or there has been some power failure in the process).
• Uncertainty to classify an event that happened (murder? suicide? accident?)
• Uncertainty about a value of a certain attribute in the event (again - inaccuracy of measurement or lack of information)
• Uncertainty about the timing of an event (happened sometimes during last night, but we don't know when).
• Uncertainty that our sources reported all events (we cannot assume "closed world")
• Events that are inherently probabilistic (e.g. future/predicted events).

Uncertainties related to the processing:

A pattern in the event history designates a "business situation" in the application domain

• Uncertainty whether the pattern detection is a sufficient condition to identify the situation, or it is only an approximation (which is a major source for "false positives" and "false negatives").
• Uncertainty about the meaning of a "partial satisfaction" of the pattern, e.g. the pattern consists of a conjunction of four events, what happens if three out of the four occur ? is it a really a binary game?
• Uncertainty that is driven by one of the uncertainties related to the source (e.g. uncertainty in the timing of event occurrence may inflict uncertainty in a temporal-oriented pattern).
• Processing of probabilistic events.

There are also uncertainties associated with the event consumer - but there are for now outside the scope of this discussion. More - Later.

On Virtual Events

The glossary defines event as something that happens, it also has some escapte to talk about virtual events that is: an event that does not happen in the physical world but appears to signify a real world event; an event that is imagined or modeled or simulated

Which leads to the question- when we are processing events, is there a place to process events that don't really happen in the physical world - well, today that people have second life in a virtual reality, and there are some events in this reality that worth processing, this is an example of a virtual event, but there are some other examples -- when event processing is used in a simulated mode, the simulated event also does not happen in the physical world, if an event is predicted it has not happened (yet?) in the physical world and there are some other examples. The question is -- what is the difference between event and virtual event ? are the boundaries even clear ? - in the meta-physical world the answer is YES, an even either occurs or does not occur (following the law of excluded middle), however, in reality we may have uncertain events, thus, when processing this event we don't really know if it is a real event or a virtual event. In previous posts I have started to talk about the importance of context and this is the key to handle these events - an event happens within a context. The context may be physical deterministic world, virtual world, physical stochastic world, simulated world, predicted world etc - and the event happen within this context. The type of processing for these events is the same, so something that is real in one context may be virtual in another context and vice-versa.

Furthermore, something that may be considered as an important event in one context For example:

the event that the Dow Jones is up by 5 percent is an exciting event for some people, and a non-event to the fisherman on the Pacific island beach who does not even know what Dow Jones is, but for him the capture of a fish that weighs 100 KG is a big event, and the broker in Wall Street is not excited from such an event, thus - the question whether something deserves to be called "event" is also a question of context. I'll get to a more formal definition of context in the next posting.

On Event Representation

Back to micro-oriented issue, and today I'll start discussion about -what's behind the definition of the event processing glossary and get to the issue of event representation. As the glossary says - event is something that happens in reality. We also tend to call "event" to the representation of this reality for the purpose of processing by a computer. This notion in event has in the glossary several aliases: event object, event message and event tuple. The various aliases are indications that the space of event representation is not uniform, some think about event as a message that moves around, some thinks of it as a tuple, which is part of a stream, and really the twin brother of a tuple in relational database, some think of it as an object with arbitrary structure (which may also be hidden). Obviously, there is no "universal event", and unfortunately, since in many cases, events are already given from the sources with their given formats, and the event processing designer has little to say about it, then a generic event processing system has to support multiple type of events, or have adapters that translate all types of event to some cannonic type of event (and typically both -- supporting some cannonic type of events and having adapters translating other types of events to the cannonoic type). Event can be structured, semi-structured (XML), and unstructured (the area of unstructured events processing deserves more focused attention). One of the questions is - whether there are common attributes that each event should have to enable event processing. In the data world - the answer is no - there is not a single attribute that must exist in all relations (besides the fact that each tuple should be a member of some relation - no floating tuples). For event processing -- there are some attributes that have been proposed as common attributes:

• Event-type
• Source
• Time-Stamp (or Time-Interval)

Let's look about the question - are they mandatory or not:

• The first question is whether each event is an instance of an event-type (or event-class). The glossary says - yes ! "all events must be instances of event-type". This seems reasonable, however, we may think of some exceptions - such as rare events that have not been classified.. I need to drill down on rare events in some other post.
• The second question is whether the source should be mandatory - again, this is desirable if we want to have lineage or tracing back actions/decisions, but there may be cases in which the source is indefinite, or we wish to hide the source (e.g. leaking of information).
• The third question is whether each event must have a time-stamp (or time-interval in case it happens over an interval - another area that needs more discussion) - the answer is that many event processing patterns are time related, and if we want to know which event occurs first, or if two events occurred within 5 minutes of each other, we need to know WHEN this event occurred in reality. However - in some cases it is not known, in other cases it is not really needed.

It seems that all common attributes are useful, but may be optional in some cases.

There are attributes that are common for types - such as probability for uncertain events, spatial coordinates for spatial events etc -- this is before relating to the content.

The content is determined according to domain related ontologies - and there is a lot of work today in different application domain or industry to define such ontologies. XML is the ontology language, and it has its own benefits, it also carries overhead relative to "flat" events in which the attributes are positional oriented and not keyword oriented.

Events also carry semantic information - such as: reference to entities in certain roles. In fact, event can be thought of a transition between one state to another and the information included in the event refers to a change in the universe such as:

what was changed ? what entities are affected? when it was change ? where did the change take place ? what other information is important about the change ?

This short discussion raised already several open issues that deserve further discussion - so I'll put these topics on the queue for further postings.... more - later.

On False positives and False Ngatives

From syntactic point of view, CEP looks for patterns and derives event / trigger action based on each pattern detected, however, detecting the patten is the mechanic work, the patterns designate a "situation" which is an "event" in the customer's frame of reference to which the customer wants to react to (there are also "internal" situation for further processing. There is obviously a gap between the intention (situation) and the way it is detected (patter no the event flow). In many cases,satisfying the pattern is sufficient condition to detect the intended situation, however, in other cases, this serves as "best approximation". This leads to the phenomenon of false positives (detecting of patterns, but the situation did not really happen) and post negatives (situation occurred but pattern has not been detected). Some reasons are:

• Raw events are missed - do not get at all, or do not get on time (source or communication issues).
• Raw events are not accurate - values are not accurate (source issues).
• Temporal order issues - Uncertainty in correct order of events.
• Pattern does not accurately reflect the conditions for situation (e.g. there are probabilistic elements)
• (other reasons) ?

Like the time constraints case there are various utility functions to designate the damage from either false positives or false negatives.

More on that issue - later.