Modern event-driven applications implement sophisticated and highly specialized algorithms for detecting and correlating events from event streams or clouds. The correlation logic and resulting actions are declaratively de ned as EA (event action) rules. An EA language allows the de nition of complex correlation rules with the help of logical, temporal, content-based and other operators. On the other hand, production rule systems provide a declarative means to express and compute CA (condition action) rules. CA rules de ne constraints. The most prominent scienti c and commercial production rule systems rely on the RETE algorithm in order to e ciently compute CA rules. As the industry is on the way towards a loosely coupled service-oriented and eventdriven architecture, there is a high demand for an integrated solution of computing ECA (event condition action) rules. In this paper we give a survey of already nished as well as ongoing research in the eld of combining event processing algorithms with the RETE algorithm. We compare the di erent approaches and present our approach of combining SnoopIB, a specialized event detection algorithm, with the RETE algorithm.
In a production rule system the RETE algorithm [
The open research question remains of how both matching operations can be
integrated in an e cient manner. There are many approaches of either adding
event processing to production rule systems or integrating scalable condition
pattern matching algorithms into event processing engines. In this paper we describe
the di erent approaches and present their Pros and Cons. We present a novel
approach of combining the two rule execution paradigms: Data-driven and
eventdriven execution. Our algorithm is an excerpt of our ongoing research of adding
complex event processing (CEP) to RETE. It is a middle course which refrains
from merging the two algorithms but still exposes synergistic e ects. However,
the question is not whether the event and condition speci cations should be
consolidated. Conceptually, events and conditions are concerned with di erent
information with di erent semantics. Therefore, it makes sense to distinguish
events from non-temporal facts in an ECA rule speci cation. Considering an
application as a state machine, events represent transitions, cf. [
Table 1 outlines some notable di erences in semantics and behavior of events
and non-temporal facts. Events are transient and are consumed after they are
delivered to all consumers. Facts, on the other hand, are persistent and must
explicitly be deleted. Events are usually immutable, whereas facts may be changed.
Analogies may be drawn to transitions and state, respectively. Another analogy
from [
The paper is structured as follows: Section 2 surveys the di erent approaches of adding event processing capabilities to the RETE algorithm. In Section 3 the several approaches introduced in Section 2 are accessed and the pros and cons are outlined. We give an elaborated insight into our algorithm that combines CEP with RETE in Section 4. We conclude the paper in Section 5 with a discussion and outlook.
Maloof et al. [
Berstel [
Berstel also devised a garbage-collection mechanism to expunge unneeded events when they are no longer needed. Events are special facts which are asserted through a special API. Only these facts are considered for garbagecollection. When a join node encounters a new event in one of its input memories, the lifetime of the event is calculated from the time stamp of the event and the join conditions of the node which must at least be ful lled. A callback service is used by the join node to raise a timeout when the lifetime is passed. The node then issues its parent memory to delete its local reference to the event. Global retraction of events is not discussed.
Walzer [
Walzer implemented a garbage-collection mechanism, taking into account the constraints in join nodes, time-based windows in join nodes, the time stamps of events and maximum lifetimes of events. When a new token or a new working memory element (WME) reaches a RETE memory, their lifetimes are calculated if they contain events. The working memory is noti ed to increase the reference counts on these objects. Using the calculated lifetimes the working memory starts the creation of timers in the garbage-collector. When a timer runs out, the garbage-collector removes the referenced token or WME from its memory. The reference count in the working memory is then decreased, and if it reaches zero, the event is completely retracted from the working memory. 3
There are several features concerning CEP in which the mentioned approaches di er and there are some which they have in common due to the RETE algorithm.
An important distinctive feature is the treatment of events as time intervals
instead of time points. For the eld of CEP this has been discussed for quite some
time, e.g. in [
The next distinctive feature is garbage-collection. Events arrive in streams. They may then be processed and must be discarded in order not to use inde nite amounts of space. Events are transient representations of incidents which happened. These events may be used on a subscriber-basis by di erent consumers, i.e. rules in the RETE context. When no further consumer is interested in an event, it can be discarded. Thus, there is a fundamental di erence between facts and events. Facts have a potentially inde nite lifetime. They are only removed if they are explicitly retracted. Events, on the other hand, have individual lifetimes which may be calculated from constraints imposed by their consumers. After these lifetimes have expired, the event can be completely removed.
Another distinctive feature is the operators introduced by the di erent approaches. Berstel proposes the operators before and after for time-points. As there are no intervals, Berstel's approach does not contain an during -operator. Maloof adds the during -operator. Walzer nally adds all operators representing the 13 interval relations. This is the richest set of operators one of the approaches o ers.
All approaches share the notion of a working memory. All events go into the working memory and stay there as long as they are not garbage-collected. However, providing a global pool of events is not appropriate for a publish/subscribe environment. For example an event should be only visible to rules which subscribe to it and there should be no reason to expose the event further. The working memory, however, retains the event as long as it might still match one of the current rules. Only then is the event discarded. When a new rule is introduced it should not match events from the past; Ideally all events will be deleted. However, a new rule might still see an older event if is still in the working memory, retained by some existing rule / consumer. Therefore the matches for the new rule depend on the existence of other rules. This is a very much undesired e ect for a rule system.
The semantics of an event being visible in the working memory is therefore
unspeci c, meaning only that the event has not been consumed by all subscribers.
Other features of the working memory are also not applicable for events. This
questions the purpose of adding events to a working memory in the rst place.
For example as events should be immutable (cf. spoken word analogy mentioned
in Section 1) the modify-operation of the working memory is not applicable. In
fact, Walzer marks events as immutable facts (cf. [
None of the RETE-based approaches have a notion of event selection and
consumption. Selection and consumption are described e.g. in [
In all of the approaches mentioned above a given join node correlates the available events from both inputs. This results in a cross product of all events which have a suitable lifetime and therefore are not garbage-collected yet. However, there is no way to specify e.g. that successive events should supersede their predecessors as in the so-called Recent context. Also, there is no way to consume events in the process of correlation. Rather, events will take part in further correlations as long as only its temporal constraints are ful lled. 4
Instead of incorporating the event detection in the RETE network, we decided to process events in a disjoint set of nodes and only merge the two graphs at the nal nodes. Figure 1 shows an example graph.
This allows us to retain an event graph which is not subject to assumptions
from the RETE algorithm. We use an event detection graph as proposed with the
event pattern language Snoop [
Simple events coming from the event sources are fed into the graph at the bottom. According to the connected nodes, the events are either discarded, queued or propagated further if they match an event expression. 3 http://www.jboss.org/drools
ECA rule
ECA rule
CA rule
The RETE network and the described event detection graph have several things in common. They are both DAGs used for incremental pattern matching, in a data-driven, bottom-up fashion. Both employ state saving by not recalculating previous matches. Both reuse partial matches shared by more than one rule. However, especially for the application of CEP, the event graph has some advantages.
{ The event graph can have nodes with more than two input edges. This more
closely resembles higher-level event operators from Snoop which we are using.
{ Also garbage-collection comes more naturally. Events are stored and
discarded in the queues of event nodes where they are still needed. There is
no global repository for unused or partially unused events like the working
memory from RETE.
{ Consumption modes are selectable (on a per-node basis, if necessary). This
allows for the controlled selection of events from a stream, if more than one
events have arrived and might be tting for a match. For example in selected
applications only the newest event of its kind might be of interest. This
behavior is called Recent context. There are several contexts as described in
[
On top of the event graph and RETE a new layer of nodes is introduced, cf. Figure 1 at bottom right. It represents the rules. For a CA rule, the production node from RETE is connected solely to the rule node. For an ECA rule, additionally an event node is connected to the rule node. The rule node res its associated rule actions according to the ECA semantics. For an ECA rule action to re, an event must be detected, and for its complete interval, the condition must be ful lled.
Vice versa this means that no events need to be correlated as long as RETE supplies no matched tokens. Using this realization, computation time (and space) can be saved in the event detection graph, when unneeded event nodes are disabled during the time the rule condition has no matches. We are disabling nodes recursively down from the top event node (which is to-be-disabled) down to all of its contributing children nodes. Care must be taken when encountering a shared node which has further consumers. Such a node is only disabled when all its consumers are disabled.
The achieved savings from this procedure varies depending on several factors. If no event nodes are reused, the saved computations are a function of the event frequencies and the probability of the rule condition being unmatched. To calculate the necessary event operations of one rule, one must consider the added frequencies of all participating events, simple and complex, including all intermediate stages.
However, determining the average frequency of events might not always be practicable or accurate, e.g. if a source emits events aperiodically. Also, if nodes are shared by several consumers, assessing the amount of saved computations becomes more di cult. Event operations can only be cut down if all consumers are disabled. The event-frequency of each participating node must then be multiplied by the probability of all other consumers being disabled as well. 5
In this paper we compared di erent approaches of incorporating CEP in a RETE
network. As RETE is designed to reason over persistent and mutable facts, it
is not a natural t for doing event processing. Many changes towards temporal
capabilities as well as event expiry must be added. And because the RETE
network relies on a working memory where events reside, such an approach does
not resemble an event processing network as described in [
We presented our approach of blending CEP with RETE as a solution to avoid the indicated mismatch of requirements. Our approach works by combining dedicated event processing nodes with RETE nodes. In our opinion it is a promising way of coupling event and condition processing, creating synergistic e ects without constricting the features of CEP. Features of CEP which are not available in current RETE adaptation are mentioned in this paper. The features include selectable detection contexts to determine the precise candidates of events for correlation. Also the features include local visibility of events and garbage collection which guarantees the isolation of di erent rules. These requirements for CEP have not been addressed by the current RETE-based adaptations.
As an outlook for our approach we are going to evaluate our implementation, in order to produce numbers for the savings in event processing time mentioned in Section 4. Benchmarking ECA rule performance depends on many factors and we are looking for a suitable ratio of event frequency, number of rules, and changes to the working memory. For that purpose we are going to evaluate existing metrics on scoring of event-driven and rule-based systems.
In the future we are also looking into further improvements for our approach.
The four detection contexts from Snoop can possibly be generalized by an algebra
for event selection and consumption as proposed in [