Saturday, September 12, 2009

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.

Friday, September 11, 2009

On event processing language standards

I found some time today to get away from the laptop (although, as usual I have a huge to-do list, with people in three continents chasing me...) and go to see the "Time Traveler's Wife" movie. The critics said that anybody who read the book will be disappointed, but although it does not fully following the book, it keeps the spirit, and rather well done.

Anyway, some of my to-dos is prepare for the 5th event processing symposium, in which I have to jump between several hats. One of my hats will be to provide the report of the language analysis workgroup which I am co-chairing with Jon Riecke from Aleri, who would not be able to come (however some Aleri representatives will be there). Going back to the original charter of the workgroup, it was intended to start discussion about event processing standards. We have not really started the discussion, however, the Trento symposium will be a good opportunity to start this discussion. I am showing now a draft of the slide I am going to show there to start the discussion;

In the top part of the chart I am bringing some memories from the database community.

So - those who are going to be in Trento, prepare for a lively discussion around this topic, I am sure that there will be a variety of opinions.

More about the language analysis workgroup - in later postings.

Wednesday, September 9, 2009

More on the upcoming fifth event processing symposium in Trento

Today's event in the Israeli media is the fact that two days ago the Israeli Prime Minister disappeared for a day, without his office notifying the media where he is, in the beginning the media was told that he is in a security-related all day meeting outside his office, but this did not make sense to reporters, and they quickly found out that his office hired for him a private aircraft and he spent that day in Moscow. well -- today, one cannot cheat the media anymore, everybody know everything about anybody; the result of totally interconnected universe.

The 5th event processing symposium in Trento is getting closer, I plan to get to Italy a few days earlier for a vacation, and the plan is getting to closure. Thanks to all that volunteered to contribute and participate in sessions or panels. One of the themes of this symposium is reaching out to other communities, our keynote speakers reflect this theme.

Our first keynote speaker will be John Myloploulos, one of the most notable scientists, who will talk about using event processing to model and monitor business objectives and business processes. This will be in the framework of reaching out to the business process management community. There has been recently a workshop in the framework of the BPM 2009 conference, the flagship conference of the BPM community that dealt with event-driven business process management. Paul Vincent, who has been keynote speaker in that workshop, wrote about it in his Blog. I have been involved in the organization, but could not be there in person.
The synergy between the two areas is being investigated in the framework of a proposed EU project that we are working on now.

The second keynote speaker will be Kristian Stewart who will tell us about the state of the art in IT event management. It will be interesting to discuss the differences and commonalities between our event processing approach,and the approach taken in network and system management.

The third keynote speaker will be Sebatian Wrede. This will be in the framework of the research session, and will deal with event processing in robotics. It turns out that there is a work in the robotics community on event processing, there is even a workshop on event-based systems in robotics in the framework of robotics conference, that is planned for October 2009. It will also be interesting to have synergy with that community. As I believe that event processing is pervasive in many areas and not restricted to certain industry or application type, this reach out will be interesting, and will also provide us feedback about additional directions for event processing technologies. See some of you in Trento. Ciao.

Tuesday, September 8, 2009

On situations and events

Almost midnight, after a long day that started in 8AM and did not end until now.... some days are like that, tomorrow might be a slightly shorter work day. Before retiring to sleep, I'll write something on this Blog as a kind of doing something else...

I have written before about situations, however, I am not sure that this term is still well understood (the same applies for context, but I'll leave context for another posting). In the EPIA book, when revising the book, we decided that the term situation is a very basic one in event processing, and put it in the introduction chapter. Situation can be thought of as event that requires reaction, but this is somewhat simplistic definition, since indeed situation is an event, but it is something that is considered as event in the user's domain, and not necessarily an event in the physical domain. Sometimes we wish to react to a raw event, sometimes we can say that a derived event represent the circumstances which we want to react, and sometimes a derived event is just approximation for the situation.

Let's look at a couple of example.

Example 1: The situation we would like to react is that a driver crosses toll both without paying -- In Israel, as high-tech country, in the only toll highway, we have camera that takes pictures of the license plate and send the bill to the driver (unless one is subscriber and then it has some identification device in the car), thus we don't really have toll booths, but in the USA it is quite pervasive. Anyway -- this situation can occur if a driver moved through "EZPASS" lane without having a device, or somehow sneaks without paying. Assuming that there are cameras that capture it, then the derived event, which is a disjunction pattern of these two events, is a complete match for detecting the situation.

However, life is not that simple, and we move to example 2. This example, that I used before in different opportunities, is that in a call center we are looking for frustrated customers in order to send a friendly customer relations officer to call them and ease their frustration.
Sometimes the person who handles request can detect the frustration, by the tone of the voice, if it is a phone call, or style of writing, if Email, but sometimes not, so what we can do is based on past experience, devise criteria for who is frustrated customer, and this may be -- a customer that sent three requests on the same topic during a single day. This criterion may be an approximation for the "frustrated customer" situation, but not an exact match, thus we can get false positives or false negatives. Handling such approximation cases is part of inexact event processing, and this seems to be one of the issues that will be part of the next generation of event processing languages and models. More - Later.

Monday, September 7, 2009

On Event Processing Patterns

This is an illustration that has been created by my of my former colleagues to the AMiT team, Tali Yatzkar, when she attended a "presentation course" as an excercise in the course to explain what is an event processing pattern (we did not use this term at that time), this is the original picture, it is animated (the animation is not presevered when copying from file to picture) and the geometric shapes in the left-hand side of the picture are moving. The idea is simple, there are patterns that designate the relationship between a set of events, e.g. a conjuction: event E1 and event E2 both hoccur in the same context (e.g. relate to the same person within 2 hours). This rather simple idea is the jewel of the crown in event processing systems, and the basis of what David Luckham called: Complex Event Processing. It is also what makes a composite event in active database terminology (I have discussed in the past the subtle differences between those term definition). This illustration in some variations has a life of its own, and we saw it in presentations of some other companies and people, I even once had to comment on a Slideshare presentation when it was attributed to (see my comment to this presentation). Anyway, besides giving Tali her due credit, I am writing about event processing patterns, since one of the chapters we complete now for the second-third review of the EPIA book deals with the notion of event processing pattern as a major abstraction. As all abstractions in our meta-language, a specific languages may implement a certain pattern as a language primitive, or implement it through a combination of language primitives. Those interested in the formal definition will need to read the book since the formal definition require definitions of several terms, so I'll give some a less formal definition here -- pattern is really a function that takes a collection (or stream) of input events that satisfy some filtering assertions (e.g. they have to be within context, and have certain other patterns) and returns zero or more "matching sets", which include a collection of individual events that collectively satisfy the pattern. Let's take a couple of examples:

The first example: Bid example: There is a bid for some auction that has been provided on an auction site. The idea is to select a single winner. The input events are acution offering events and bid events. The bid events are partitioned according to the auction offering they are refering to, and are also filterred out according to time (each auction is open for a certain amount of time only) and according to threshold condition (has to be no less than a minimal price).The matching set in this case consists of a single bid event per auction offering. The matching pattern here is - "relative max", which means that any event that we are looking for the event with the relative (to the other input events) maximal value of some attribute (in this case the bid amount). Note that the "relative max" pattern does not necessarily provide a single bidder, thus we also need a "synonyms policy" to determine what happens when we have multiple events of the same type that match the criteria. In this case we take the fairness criterion of FCFS, and the synonyms policy will be -"first", meaning the first bidder that offerred the maximal price. In our meta-language this looks like:
Pattern name = Bidder selection; Pattern type = relative max; Input events = (Auction offering, Bid); Context = (segment = by auction offering, temporal = auction offering is open); Filtering assertion = (Bid.Price >= Auction Offering.Minimal Price); policies = (cardinality = single, synonyms = first)

Note that in these three and a quarter lines we have expressed logic that is quite complex, and this is the magic of patterns. As an exercise to the reader, write the equivalent logic in Java, and then change it so that it will chose all bidders that have provided the relative maximum for a second round of bids.

The second example is a sequence example, this figure is being taken from the EPIA book; the example is looking at the case in which a patient is released from the hospital and then admitted again within 48 hours with the same complain that brought this patient to the hospital in the first time.

Here we are looking for a sequence (the order is important, of course), of the patient release event, and the patient admission event for the same patient with the same complain within 48 hours. The definition in our meta-language will be roughly:

Pattern name = Repeating admission, Filter type = sequence, input events = (Patient Release, Patient Admission), Context = (segment = by patient and complain) temporal = Patient release + 48 hours).

This pattern creates a matching set which consists of a pair of events of types patient release and patient admission).

Note that the pattern return the selected events, and the EPA can derive new events as the function of these selected event.

Here we saw two type of patterns: relative max, which is a set oriented pattern, and sequence which is event oriented patterns. I'll provide the list of patterns collected so far in one of the future postings.

Sunday, September 6, 2009

On event processing grand challenges

This is the logo of the "Grand Challenges SIG" of the UK Electronic design knowledge transfer network. In the 4th Event Processing Symposium last year, Arkady Godin from MITRE, proposed in the business meeting to launch a work group that will deal with grand challenges in event processing. The EPTS steering committee decided that such a workgroup may be premature, and it is better to complete some work in the other workgroups -- languages, architecture, use cases, interoprability, in order to have a better understanding of the grand challenges, however, this issue has neither forgotten nor forsaken. We determined that the best forum to discuss the grand challenges is the (second) Dagstuhl seminar on event processing, which I'll co-organized with Rainer von Ammon and Mani Chandy, we also asked to invite all people that we saw as the right set of people to participate in such an event (if you have not been invited and think you would like to contribute, please let me know, there is a waiting list for available slots if any, no promises though).

In the coming 5th event processing symposium in Trento, we shall hold the first brainstorming about grand challenges. Pending technical feasibility (still requires confirmation from local organizers) we plan to do this as a public session that all EPTS members will be able to use through audio conference call, EPTS members will get full details with call-in numbers when it will be finalized.

Grand challenges can be in multiple areas and also refer to multiple addressees. There are grand challenges that will require a community effort, and these challenges should be picked up by EPTS, some challenges are to advance the state-of-the-art, and this will be addressed to the research community, with some creative incentives. Some will be referred to the product vendors, and may be some to other adjacent communities.

Idea for such grand challenges are solicited from various sources:
  • EPTS workgroups that already are active, each workgroup will be asked to contribute a challenge in its area
  • The reach-out sessions for other communities in the symposium (the BPM community and the the IT management community) might also lead to some challenges
  • The research community is always a source for such challenges
  • Last but not least -- all EPTS members (and other interested people that wish to contribute, and thus are hopefully future EPTS members), specifically customers who has long-term vision about their systems, like our MITRE colleagues who started this discussion, and our analysts colleagues who have cross-vendor and cross-customer perspective.

    Anybody who wishes to contribute ideas to this session, please let me know by the end of this week.
I'll wrap-up this posting, by pointing out a Blog entry I have seen just now, written by Niels, who runs a consultancy company called "SQL Develop" as its name testifies deals with DB related issues. The upcoming Microsoft product "StreamInsight" has raised the interest in the database community, as Microsoft seems to take an SQL oriented approach to its product, and Niels is blogging about "CEP resources" he covers Blogs in this area, on my Blog he writes: THE blog about CEP, if you were to read only one blog about CEP, this is it! First, thanks to Niels for the endorsement, I don't view the Blogging area as a competition, as people who read Blog tend to read multiple Blogs, and it is also kind of a network of Blogs that sometimes react to each other. To be fair, also most Blogs in this area are marketing oriented Blogs, that they have somewhat different motivation from my Blog, and one cannot compare. Anyway, a good way to start the day.