Wednesday, November 26, 2008

On event hirearchies and types


In a comment to my previous posting Harvey has reminded me that Israel won second place ("gold medal") in the Chess Olimpics, actually it has been number one through part of the games and then moved to number two which is also very respectable. I have not played chess since high school, but I have registered to play in an internal IBM championship in Backgammon;
A game I have not played a lot recently, so need to practice...

I am following with interest Marco's Rulecore Blogging about geo-spatial operators, I think this is in the right direction, and there is a lot of potential in spatial and even spatio-temporal patterns and I also view space as one of the main dimensions of context. However, today I would like to write about one of the other topics that Marco has been writing about -- event hirearchies, in this posting Marco suggests hirearchy level of events and rules, such as rules in level 1 consume only events of level 1 and produce event of level 2, and so forth. This reminds me a great scholar named Bertrand Russell, whose picture you can see below:
Russell has introduced a well-known paradox which in its popular form is called the "Barber Paradox" (Wikipedia claims that
which states that in a village there is a barber who shaves everybody who does not shave himself. The question is who shaves the barber? if the barber shaves himself that means that the barber is not shaved by the barber, however if the barber shaves the barber that means that the barber does not shave himself, meaning that the barber shaves himself if the barber does not shave himself and vice versa. Russell also provided solution for the paradox called "type theory" saying that we have hierarchy of terms and functions/predicates based on "types". Thus if a "person" is of type 1, Barber is a predicate of a person, which makes it term of type 2, being a term of type 2, it cannot participate in predicates on type 1, and thus the entire paradox does not happen. Type theory indeed resolves the paradox (if you wonder the "types" in programing languages are indeed derived from Russell's terms), however, the price is that the expressive power of the language is compromised, things which seem to us perfectly valid in natural language are not valid under the types theory.

Back to event processing -- let's look at the following example:
  • Our location-based event processing system manages fleet of cabs and travel reservation.
  • An order arrives for a travel in 30 minutes
    - this is an event of type 1, it is processed and matched against taxis locations and directions to assign the right cab and makes "cab assingment" which is an event of type 2 (since it was created by an event processing agent - "rule" in Marco's terminology that processed events of type 1).
  • After a short while the perspective traveller changed his mind and called to cancel the order. This is again, event of type 1.
  • However, now we have to find out if the travel has already been allocated and if yes deallocate the travel and free the allocated taxi. This operation has to take two events as input -- the travel cancellation (type 1) and the travel allocation (type 2)... Oops... our system works purely on strict hierarchy of event types --- can't do that!.
This demonstrates that using strict hieratchy we'll have, like Russell's type theory, to give up expressive power. So it seems that while hierarchy is a good idea, it may also serve as a restriction... One modification is indeed to order the event types and the agents, however enable agent of type 2 to accept as input events at type 1 and 2.

With this correction there are certain benefits for using the hierarchy levels, relate to optimization possiblities that Marco have not mentioned. We'll discuss them in one of the next postings.


6 comments:

david said...

Opher,

I think you’ll find that event hierarchies, and rule-based hierarchies are emphasized in my book, Power of Events.
Starting very early on in the introductory part, Chpt 3 “Viewing the Electronic Enterprise”, see 3.7, and later Chpt 7 “Complex Events and Event Hierarchies”.
Then in Part II, “Building Solutions with CEP”, you’ll find Chpt 13 “Implementing Event Abstraction Hierarchies” deals with a variety of problems that occur in event hierarchies, e.g., organizing constraints and rules hierarchically, and implementing induced causality between levels. You’ll find examples of event hierarchies in frabrication processes, and in Chpt 14 “Viewing a Financial Trading System” there’s a detailed example of how to design and build a constructive event hierarchy.
Of course, new examples are always good to have, and we need more of them,, and more applications of these ideas.
Cheers
- David

Opher Etzion said...

Hi David.

I know your book, of course, and the central role of event hierarchies. The point I was making about Marco's posting is that STRICT hierarchy is sometimes a limitation, and am thinking on a model of hierarchy of agents.

cheers,

Opher

harvey said...

Hello David and Opher,

I think an illustration of the challenge any _strict_ application of conceptual hierarchies poses is this:

Organization A has their hierarchy of rules and events. Organization B has theirs. Organization A sends an "event" to Organization B. Organization B may "use" and "interpret" the event in a manner much different than how Organization "A" intended.

One response could be "that should be worked out in the agreement and SLA between the organizations before an event is sent", which in a tight community (say trading, insurance) is likely the case.

However, in the arena of preparedness and response (think Mumbai) a large number of organizations will be making high level agreements on what to do when receiving events, when to send them etc.

It may be impractical to work out agreement on conceptual levels prior to getting initial agreement in a large grained sense between orgs.

This is the challenge I am facing. Any insight is appreciated.

Take care,
++harvey

harvey said...

And as a follow-up to my previous comment:

How will we conceptually classify these "events" (via twitter)?:

http://edition.cnn.com/2008/WORLD/asiapcf/11/27/mumbai.twitter/

Take care,
++harvey

Opher Etzion said...

Hi Harvey.

As said, I don't believe that strict hierarchies of events are feasible in the general case.

As for cross-organizational event processing network, this can be partitioned into within-organization EPN, where events from another EPN will be treated as raw event (event that came from producer), no matter what level it has been within the source's EPN, so there is no need to agree on conceptual levels.

cheers,

Opher

harvey said...

Opher,

I agree, within a cohesive organization it should be possible for at least a high level conceptual hierarchy, but even this takes years - based on my involvement in US DoD semantic activities.

Now I am considering what happens when we try to "glue together" disparate orgs for a particular purpose - such as that of forming a capability like emergency preparedness and response. Case in point -- recent events in Mumbai.

At some point in forming such a capability, there would be a shared architecture (at some conceptual level) that can facilitate (among many things) the rights and responsibilities of exchanging events related to said capability.

I do not have answers at this point, but there are certainly a lot of questions. Perhaps these questions are suitable for the EPTS "Grand Challenge". I hope you and David agree, and look forward to tackling this next year :-)

Take care,
++harvey