An event detection algebra for reactive systems.
In reactive systems, execution is driven by external events to which the system should respond with appropriate actions. Such events can be simple, but systems are often supposed to react to sophisticated situations involving a number of simpler events occurring in accordance with some pattern. A systematic approach to handle this type of systems is to separate the mechanism for detecting composite events from the rest of the application logic.In this paper, we present an event algebra for composite event detection. We show a number of algebraic laws that facilitate formal reasoning, and justify the algebra semantics by showing to what extent the operators comply with intuition. Finally, we present an implementation of the algebra, and identify a large subset of expressions for which detection can be performed with bounded resources.
INTRODUCTION
Many real-time and embedded systems are reactive, meaning
that the execution is driven by external events to which
the system should react with an appropriate response. For
many applications, the system should react to complex event
patterns, sometimes called composite events, rather than to
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
September 27-29, 2004, Pisa, Italy.
a single event occurrence. A systematic approach to handle
this type of systems is to separate the mechanism for detecting
composite events from the rest of the application logic.
The detection mechanism takes as input primitive events
and detects occurrences of composite events which are used
as input to the application logic. This separation of concerns
facilitates design and analysis of reactive systems, as
detection of complex events can be given a formal semantics
independent from the application in which it is used, and
the remaining application logic is free from auxiliary rules
and information about partially completed patterns.
Example 1. Consider a system with input events including
a button B, a pressure alarm P and a temperature alarm
T, where one desired reaction is that the system should perform
an action A when the button is pressed twice within
two seconds, unless either of the alarms occurs in between.
This can be achieved by a set of rules that specifies reactions
to the three events, so that the combined behaviour
implements the desired reaction. Alternatively, a separate
detection mechanism can be used to define a composite event
E that corresponds to the described situation, with a single
rule stating that an occurrence of E should trigger the
action A. The two approaches are illustrated by Figure 1.
A
Application logic
A
Event
detection
Application
logic

Figure

1: Implicit and explicit detection of composite
events
The mechanism to detect composite events can be constructed
as an event algebra, i.e., a number of operators from
which expressions can be built that represent the event patterns
of interest. In this paper, we propose an event algebra
that specifically targets applications with limited resources,
such as embedded and real-time systems. We present a number
of algebraic laws that facilitate formal reasoning, and
justify the algebra semantics by showing to what extent the
operators comply with intuition. Finally, we identify criteria
under which detection can be performed with limited
resources, and present a transformation algorithm that allows
many expressions to be transformed into a form where
these criteria are met.
The proposed algebra consists of five operators: The disjunction
of A and B represents that either of A and B oc-
curs, here denoted A#B. Conjunction means that both
events have occurred, possibly not simultaneously, and is
denoted A+B. The negation, denoted A-B, occurs when
there is an occurrence of A during which there is no occurrence
of B. A sequence A;B is an occurrence of A followed by
an occurrence of B. Finally, there is a temporal restriction
A# which occurs when there is an occurrence of A shorter
than # time units.
Example 2. The composite event E from the previous example
corresponds to the expression (B;B)2-(P#T ) in the
algebra.
The operator semantics described informally above does
not specify how to handle situations where an occurrence
could participate in several occurrences of a composite event.
For example, three occurences of A followed by two occurrences
of B result in six occurrences of A+B. While this
may be acceptable, or even desirable, in some applications,
the memory requirements (each occurrence of A and B must
be remembered forever) and the increasing number of simultaneous
events means that it is unsuitable in many cases.
A common way to deal with this is to introduce variants
of the operators that impose stronger constraints in addition
to the basic conditions give above. For example, a possible
sequence variant is to require that in addition to A occurring
before B, this should be the most recent occurrence of
A so far. Such variants can be defined by means of general
restriction policies, where each combination of an operator
and a restriction policy yields a operator variant with specific
semantics. When restriction is applied to individual
operator occurrences in the expression, as in existing event
algebras with restriction policies, a user of the algebra must
understand the interference from nested restrictions, and the
e#ect of restriction on di#erent operator combinations.
We have developed a novel restriction policy that is conceptually
applied to the expression as a whole, rather than
to the individual operators, which results in an algebra with
simpler and more intuitive semantics. The policy is carefully
designed so that applying it once at the top level is
semantically consistent with applying it recursively to all
subexpressions, which allows an e#cient implementation.
As far as we know, previous research on event algebras has
not addressed conformance to algebraic laws. In particular,
event algebras suited for systems with limited resources typically
exhibit unintuitive semantics and poor algebraic prop-
erties. Throughout the paper, proofs have been reduced or
left out due to space limitations, and the reader is referred
to [3] for full proofs.
The rest of this paper is organised as follows: Section 2
surveys related work. The algebra is defined in Section 3,
followed by a presentation of the algebraic properties in Section
4. Section 5 presents an implementation, including an
analysis of time and memory complexity. Section 6 describes
a semantic-preserving transformation algorithm, and Section
7 concludes the paper.
2. RELATED WORK
The operators of our algebra, as well as the use of interval
semantics and restricted detection, are influenced by
work in the area of active databases. Snoop [6], Ode [9] and
SAMOS [8] are examples of active database systems where
an event algebra is used to specify the reactive behaviour.
These systems di#er primarily in the choice of detection
mechanism. SAMOS is based on Petri nets, while Snoop
uses event graphs. In Ode, event definitions are equivalent to
regular expressions and can be detected by state automata.
In the area of active databases, event algebras are often not
given a formal semantics, and algebraic properties of the
operators are not investigated. Also, resource e#ciency is
typically not a main concern.
Common to these systems is that they consider composite
events to be instantaneous, i.e., an occurrence is associated
with a single time instant, normally the time at which it
can be detected. Galton and Augusto have shown that this
results in unintended semantics for some operation compositions
[7]. For example, an occurrence of A followed by B
and then C, is accepted as an occurrence of the composite
event B;(A;C), since B occurs before the occurrence of A;C.
They also present the core of an alternative, interval-based,
semantics to handle these problems. We use a similar semantic
base for our algebra, but we extend it with a restriction
policy to allow the algebra to be implemented with limited
resources while retaining the desired algebraic properties.
Solicitor [12] is an interval-based event specification language
based on Snoop. The language targets real-time systems
in particular, and and achieves predictable resource
requirements for composite events with an explicit expiration
time.
Liu et al. use Real Time Logic to define a system where
composite events are expressed as timing constraints and
handled by general timing constraint monitoring techniques.
They present a mechanism for early detection of timing constraint
violation, and show that upper bounds on memory
and time can be derived [11].
In middleware platforms, event detection techniques are
used to handle high volumes of event occurrences by allowing
consumers to subscribe to certain event patterns rather
than to single event types. S-anchez et al. present an event
correlation language where event expressions are translated
into nested Petri net like automata. [14].
The event detection mechanisms described above provide
no assistance to the developer in terms of algebraic properties
or an event expression equivalence theory. In the cases
where memory usage is addressed, for example by means
of restriction policies, this results in complicated and non-intuitive
semantics.
Knowledge representation techniques use similar operators
to reason about event occurrences. Rather than detecting
complex events as they occur, they focus on how to
express formally the fact that some event has occurred, and
on defining inferences rules for this type of statements. Examples
include Interval Calculus [1] and Event Calculus [10].
We propose an algebra for which a large class of composite
events can be detected with limited resources. The algebra
is defined by a simple declarative semantics and we present
a number of algebraic laws that facilitate formal reasoning,
and supports the claim that the intuitive meaning of the
operators is valid also for complex nested expressions. A
preliminary version of the algebra, with less useful algebraic
properties and with no memory bound, was described in a
previous paper [4].
3. DECLARATIVE SEMANTICS
For simplicity, we assume a discrete time model through-out
the paper. The declarative semantics of the algebra
can be used with a dense time model as well, under restrictions
that prevent primitive events that occur infinitely
many times in a finite time interval.
Definition 1. The temporal domain T is the set of all natural
numbers.
3.1 Primitive events
We assume that the system has a pre-defined set of primitive
event types to which it should be able to react. These
events can be external (sampled from the environment or
originating from another system) or internal (such as the
violation of a condition over the system state, or a timeout),
but the detection mechanism does not distinguish between
these categories.
For some primitive events, it is useful to associate additional
information with each occurrence. For example, the
occurrences of a temperature alarm might carry the measured
temperature value, to be used in the responding ac-
tion. These values are not manipulated by the algebra, only
grouped and forwarded to the part of the system that reacts
to the detected events.
Definition 2. Let P be a finite set of identifiers that represent
the primitive event types that are of interest to the
system. For each identifier p # P, let dom(p) denote the
domain from which the values of p are taken.
Occurrences of primitive events are assumed to be instantaneous
and atomic. In the algebra, they are represented
by event instances that contain event type, occurrence time
and a value. Formally, we represent a primitive instance as
a singleton set, to allow primitive and complex instances to
be treated uniformly.
Definition 3. If p # P, # dom(p) and # T , then the
singleton set {#p, #} is a primitive event instance.
Together, the occurrences of a certain event type form an
event stream. We allow simultaneous occurrences in gen-
eral, but occurrences of the same primitive event type are
assumed to be non-simultaneous.
Definition 4. A primitive event stream is a set of primitive
event instances all of which have the same identifier,
and di#erent times.
The set of identifiers and the value domains capture static
aspects of the system. Instances and event streams, how-
ever, are dynamic concepts that describe what happens during
a particular scenario. An interpretation is a formal representation
of a single scenario, as it describes one of the
possible ways in which the primitive events can occur.
Definition 5. An interpretation is a function that maps
each identifier p # P to a primitive event stream containing
instances with identifier p.
Example 3. Let
{high, low}. Now S={{#T, 12, 2#T, 14, 3#T, 8, 5#}}
and S #P, low, 4#}} are examples of primitive event
streams, and I such that I(T)=S and I(P)=S # is a possible
interpretation.
3.2 Composite events
Composite events are represented by expressions built from
the identifiers and the operators of the algebra.
Definition 6. If A#P, then A is an event expression. If
A and B are event expressions, and #T , then A#B, A+B,
A-B, A;B and A# are event expressions.
Next, we extend the concepts of instances and streams to
composite events as well as primitive. The way in which instances
are constructed is defined by the algebra semantics.
For now, we only define their structure.
Definition 7. An event instance is a union of n primitive
event instances, where 0 < n.
Informally, an instance of a composite event represents the
primitive event occurrences that caused an occurrence of the
composite event. Since the semantics should be interval-
based, we associate each instance with an interval, through
the following definition.
Definition 8. For an event instance a we define
The interval [start(a), end(a)] can be thought of as the smallest
interval which contains all occurrences of primitive events
that caused the occurrence of a. Note that a primitive event
instance is an event instance, and if a is a primitive instance
then
Example 4. Let a = { #T, 12, 2#P, low, 4#T, 8, 5# }.
Then a is an event instance, with start(a)=2 and end(a)= 5.
We also need a definition of general event streams. These
will be used to represent all instances of a composite event.
According to this definition, a primitive event stream is an
event stream, just as the names suggest.
Definition 9. An event stream is a set of event instances.
The naming convention is to use S, T and U for event
streams, and A, B and C for event expressions. Lower case
letters are used for event instances. In general, s belongs to
the event stream S, and a to an event stream defined by A,
etc.
3.3 Semantics
The interpretation provides the occurrences of the primitive
events, by mapping each identifier to an event stream,
and the role of the algebra semantics is to extend this mapping
to composite events defined by event expressions.
The following functions over event streams form the core
of the algebra semantics, as they define the basic characteristics
of the five operators.
Definition 10. For event streams S and T , and for # T ,
define:
neg(S,
The semantics of the algebra is defined by recursively applying
the corresponding function for each operator in the
expression.
Definition 11. The meaning of an event expression for a
given interpretation I is defined as follows:
To simplify the presentation, we will use the notation
instead of I when the choice of I is obvious or arbitrary.
These definitions result in an algebra with simple semantics
and intuitive algebraic properties, but it is di#cult to
implement with limited resources. To deal with resource
limitations, we define a formal restriction policy, and require
only that an implementation should compute a valid
restriction of the event stream specified by the algebra semantics

Formally, the restriction policy is defined as a relation
rem, where rem(S, S # ) means that S # is a valid restriction of
S. Alternatively, it can be seen as a non-deterministic restriction
function, or a family of acceptable restriction func-
tions. For reasons of repeatability, it is typically desirable
that an implementation of the algebra is deterministic. From
a theoretical point of view, however, we prefer to leave as
many detailed design decisions as possible open, as we can
ensure that any implementation which is consistent with the
restriction policy relation is guaranteed to have the properties
described in the paper.
The basis of the restriction policy is that the restricted
event stream should not contain multiple instances with the
same end time, as this is one of the e#ciency issues. In-
formally, from the instances with the same end time, the
restriction policy keeps exactly one with maximal start time.
Definition 12. For two event streams, S and S # , rem(S, S # )
holds if the following conditions hold:
1. S # S
2. #s (s#S #s # (s #S # start(s)#start(s #
3. #s, s # ((s#S # s #S # end(s)=end(s # s=s # )
Rather than computing for a given event expression A,
an implementation of the algebra computes an event stream
S # for which rem([[A]], S # ) holds. For the user of the alge-
bra, this means that at any time when there is one or more
occurrences of A, one of them will be detected.
4. PROPERTIES
To aid a user of this algebra, we present a selection of algebraic
laws. These laws facilitate reasoning, both formally
and informally, about the algebra and a system in which
it is embedded. They also show to what extent the operators
behave according to intuition. For this, we first define
expression equivalence.
Definition 13. For event expressions A and B we define
hold if I for any interpretation I.
Trivially, # is an equivalence relation. Moreover, the following
theorem shows that it satisfies the substitutive con-
dition, and hence defines structural congruence over event
expressions.
Theorem 1. If A # A # , then we have
and A# A # .
Proof. This follows in a straightforward way from Definitions
Now, the laws can be formulated. For a more extensive set
of laws, and formal proofs, the reader is refered to [3].
Theorem 2. For event expressions A, B and C, the following
laws hold.
The following laws describes how temporal restrictions can
be propagated through an expression. In Section 6, these
laws are used to define an algorithm for transforming event
expressions into an equivalent expressions that can be detected
more e#ciently.
Theorem 3. For event expressions A and B, and #T ,
the following laws hold.
A # A# if A # P
(A# A min(# )
(A+B)# (A# +B)#
(A-B)# (A# )-B
(A-B)# (A-(B#
(A;B)# (A# ;B)#
(A;B)# (A;B#
The laws identify expressions that are semantically equiv-
alent, but in order to handle resource limitations, we expect
an implementation of the algebra to compute an event
stream S such that rem([[A]], S), rather than computing [[A]].
As a result, detecting A might yield a di#erent stream than
detecting A # , even when A # A # . Consequently, it should
be clarified to what extent the laws presented above are still
applicable when restriction is applied.
Theorem 4. For event expressions A and A # such that
A # A # , if rem([[A]], S) holds then rem([[A # ]], S) holds as well.
Thus, A # A # ensures that the result of an implementation
detecting A is always a valid result for A # . As long as
reasoning is based on the algebra semantics and the restriction
policy, and not on the details of a particular detection
algorithm, it will be equally valid for equivalent expressions.
To further investigate the relation between equivalent expressions
when restriction is applied, notice that the restriction
policy implies that detected event streams for equivalent
expressions always contain instances with corresponding
start and end times. This means that the part of the system
that responds to the detected event occurrences is notified
at the same time for equivalent expressions, but possibly
with di#erent values attached to the detected occurrences.
Formally, we express this as follows.
Definition 14. For event streams S and T , define S
to hold if the following holds:
{#start(s), end(s)# |
Trivially, is an equivalence relation.
Theorem 5. For event streams S, T and T # , if rem(S, T )
and rem(S, T # ) holds then
Proof. Take any t # T . Then, since T # S, t #S. By the
second condition in the definition of rem, there exists some
also have t # S, and thus there is some t # T such that
According to the
third condition in the definition of rem this implies
which means that we have start(t) # start(t # start(t) and
thus start(t # start(t). So, for any t # T there is a t # T #
with the same start and end time. Trivially, the opposite
holds as well.
Corollary 1. If A # A # , rem([[A]], T ) and rem([[A # ]], T # ),
then
Thus, A # A # ensures that for any implementation consistent
with the restriction policy, the instances found when
detecting A and A # have the same start and end times.
This means that the part of the system that responds to
the detected event occurrences is notified at the same time
for equivalent expressions, but possibly with di#erent values
attached to the detected occurrences.
In order to get the desired e#ciency, all subexpressions of
an expression must be detected in an e#cient way, and thus
the restriction policy should be applied recursively to every
subexpression. This scenario would normally require a user
of the algebra to understand how the restrictions in di#erent
subexpressions interfere with each other, and how they e#ect
di#erent operator combinations. To avoid this, the operators
and the restriction policy have been carefully designed to
support the following theorem. Informally, it states that
restricting the subexpressions as well as the whole expression
gives a result which is valid also for the case when restriction
is applied only at the top level.
Theorem 6. If rem(S, S # ) and rem(T, T # ) holds, than for
any event stream U and # T the following implications
hold:
Proof. We present the proof for negation, and refer to [3]
for the full proof. Assume rem(neg(S # , T # ), U ). For any
. By the
subset requirement in the definition of rem, u # S. If there
exists a t # T with start(u) # start(t) and end(t) # end(u),
then there must exist some t # T # with start(t) # start(t # )
and which contradicts the fact that u #
neg(S # , T # ). Since no such t can exist, we have u # neg(S, T )
and thus U # neg(S, T ), satisfying the first condition in the
definition of rem.
Next, take an arbitrary u # neg(S, T ). Then u # S and
there exists an u
end(u). If there exists a t # T # with start(u # start(t)
and end(t) # end(u # ), then the fact that t # T contradicts
no such t can exist, we have that
This means that there exists some u # U
with start(u # start(u # ) and end(u #
the second constraint in the definition of rem.
Finally, rem(neg(S # , T # ), U) ensures that all instances in
U have di#erent end times. Together, this shows that the
three constraints of Definition 12 are satisfied, and thus
rem(neg(S, T ), U) holds.
5. AN EVENT DETECTION ALGORITHM
In this section, we present an imperative algorithm that,
for a given event expression E, computes an event stream
S for which rem([[E]], S) holds. Throughout this section, E
denotes the event expression that is to be detected. The
numbers 1 . m are assigned to the subexpressions of E in
bottom-up order, and we let E i denote subexpression number
i. Consequently, we have
#P.

Figure

2 presents the algorithm. The algorithm is executed
once every time instant, and computes the current
instance of E from the current instances of the primitive
events, and from stored information about the past.
Each operator occurrence in the expression requires its
own state variables, and thus variables are indexed from 1
to m. The variable a i is used to store the current instance of
thus am contains the output of the algorithm after
each execution. The auxiliary variables l i , r i , t i and q i store
information about the past needed to detect E i properly.
In l i and r i , a single event instance is stored, t i stores a
time instant and q i contains a set of event instances. The
symbol # is used to represent a non-occurrence, and we
define start(#)=end(#)=-1 to simplify the algorithm.
The algorithm is designed for detection of arbitrary ex-
pressions, and the the main loop selects dynamically which
part of the algorithm to execute for each subexpression. For
systems where the event expressions of interest are static
and known at the time of development, the main loop can
be unrolled and the top-level conditionals, as well as all in-
dices, can be statically determined. A concrete example of
this is given in Figure 3.
5.1 Algorithm correctness
Next, the relation between this algorithm and the algebra
semantics described in previous sections must be estab-
lished. For this purpose, we need to formalise the algorithm
output by constructing corresponding event streams.
Definition 15. For 1# i # m, define
where out(i, # ) denotes the value of a i after executing the
algorithm at times 0 to # .
Due to space limitations, we only give an informal description
for each operator, and refer to [3] for formal proofs.
for i from 1 to m
a i := the current instance of E i , or # if
there is no current instance.
then a i := ak
else a i := a j
if l
then a i := #
else if start(ak )#start(a j )
then a i := a j #r i
else a i := l i #ak
a
if ak # then
foreach e in q i
then a i := e
if a i # then a i := ak #a i
then a i := a j
else a i := #

Figure

2: Algorithm for detecting event expression
Initially, t i =-1, l i =r
The disjunction operator is fairly simple and requires no
auxiliary variables. If E j and E k occur at the same time,
the restriction policy requires that the one with latest start
time is selected. When the start times are the same, this
implementation gives precedence to the right subexpression.
The fact that the implementation of the disjunction operator
corresponds to the declarative semantics with restriction,
with respect to the instances that are detected for the subex-
pressions, can be formulated as rem(dis(A(j), A(k)), A(i)).
For conjunctions, it is necessary to store the instance with
maximum start time so far from each of the two subexpres-
sions. At the start of time instant # , l i is an element in
{e | e#A(j)# end(e)<#} with maximum start time, or # if
that set is empty. The corresponding property holds for r i
and A(k).
The first two conditionals in the conjunction part of the
algorithm correctly update the state for the next time in-
stant. The new state is then used to construct the current
output instance for the conjunction, if there is one.
:= the current instance of T, or # if there is none.
a2 := the current instance of P, or # if there is none.
a4 := the current instance of B, or # if there is none.
if t5 < start(a4) then t5 := start(a4)
if t5 < start(a3) then a5 := a3 else a5 := #

Figure

3: Statically simplified algorithm for detecting
(T#P)-B. Initially, t5 =-1.
According to the semantics of the negation operator, an instance
of B is an instance of B-C unless it is invalidated
by some instance of C occurring within its interval. If the
current instance of B is invalidated at all, it is invalidated by
the instance of C with maximum start time (of those that
have occured so far). Thus, it is su#cient to store a single
start time, since the end time is trivially known to be less
than the end time of the current instance of B.
At the start of time instant # , t i should be the maximum
start time of the elements in {e | e #A(k) # end(e) < #}, or
if this set is empty. The first conditional updates the
state so that it is valid for the next time instant. Then, the
updated t i variable is used to check if the current instance
of E j is invalidated or not.
The sequence operator requires the most complex algorithm.
The reason for this is that in order to detect a sequence
B;C correctly, we must store several instances of B. Once
C occurs, the start time of that instance determines with
which of the stored instances of B it should be combined to
form the instance of B;C. The following should hold at the
start of time instant
. t i is the maximum start time of the elements in
{e | e#A(j) # end(e)<#}, or -1 if this set is empty.
. q
The first conditional selects the best match for the current
instance from the instances stored in q i , and creates the
output instance if a matching instance is found. Then, in the
second conditional, the state is updated. To ensure that q i
does not contain fully overlapping instances, the E j instance
is checked against t i before it is added.
Temporal restriction:
The temporal restriction is fairly straightforward to implement
and requires no auxiliary state variables.
Putting it all together
The following theorem establishes the correctness of the algorithm
by stating that for each subexpression E i , including
itself, the detected instances correspond to a valid restriction
of
Theorem 7. For any 1 # i # m, rem([[E i ]], A(i)) holds.
Proof. For
# P, we have under the
assumption that the interpretation correctly represents the
real-world scenario. Thus rem([[E i ]], A(i)) holds trivially.
a
if ak # then
foreach e in q i
then a i := e
if a
if a i # then a i := ak # a i
foreach e in q i
-# then q i := q i -{e}; l i := e

Figure

4: Algorithm for
Next, assume that for some i, rem([[E x ]], A(x)) holds for
any 1 # x < i. If
then according to the discussion
above we have rem(dis(A(j), A(k)), A(i)). Since the
subexpressions are numbered bottom-up, we have j < i and
k< i, so by assumption rem([[E j ]], A(j)) and rem([[E k ]], A(k))
holds. According to Theorem 6, rem(dis([[E j ]],
holds, which means that rem([[E i ]], A(i)) holds. A similar
proof can be constructed for each of the operators. By in-
duction, the theorem holds.
5.2 Memory complexity
Instances are not of a fixed size, but an instance from
a subexpression of E contains at most #m/2# primitive in-
stances, one from each identifier occurrence in E. Thus,
assuming that the elements in the value domains are of constant
size, the size of a single event instance is bounded.
A quick analysis of the algorithm reveals that each dis-
junction, conjunction, negation and temporal restriction in
the event expression requires a limited amount of storage.
The storage required for a sequence operator depends on the
maximum size of q i , for which no bound exists in the general
case. For an important class of sequence expressions,
however, the detection algorithm can be redefined to ensure
limited memory and time complexity.
For a sequence A;B where we know that the maximum
length of the instances of B is # , which can be expressed
as B # B# , this limits the number of instances of A that
must be stored in order to detect the sequence correctly.
Informally, the start of any instance of B will be at most #
time units back in time, and thus there is no need to store
more than one instance of A that ends earlier than this, if
we store one with maximum start time. From the instances
of A that end later than this point in time, we need to store
several, as in the original algorithm.
The improved algorithm for detecting A;B when B # B#
with bounded memory is presented in Figure 4. Here, # c is
used to access the current time instant. The state is similar
to the state used for sequences in the original algorithm,
but this q i contains a su#x of the q i variable of the original
version. From the remaining elements, a single element with
maximum start time is stored in l i . Since the size of q i never
exceeds # +1, this type of sequences can be detected with
limited memory.
For large values of # , for example in systems with a fine
granularity timebase, this resource bound might not be sufficient
in practice. Also, for A;B the bound is a large over-approximation
unless A occurs very frequently. If we have
information about the minimum separation time of primitive
events (i.e., the minimum time between two consecu-
where #A
where #A
where #A
where #A
where #A

Figure

5: The transformation function
tive occurrences of the same event), more precise worst case
memory estimates can be derived [3].
5.3 Time complexity
As a result of instances not having a fixed size, assigning
an instance to a variable might not be a constant operation,
but rather proportional to the instance size. Thus, each operator
contributes with at least a factor m to the complexity
for the whole algorithm. For sequences, a straightforward
representation of the q i variables gives a linear time complexity
for finding the best matching instance, with respect
to the size limit of that q i variable. This gives a a total complexity
of O(mn # ), where m is the number of subexpressions
in E, n # =max(m,n) and n is the maximum size limit of the
Due to the particular characteristics of q i , a more elaborate
implementation is possible, where the best match is
found in logarithmic time and updates are only bounded by
the m factor for variable-sized instances (for details, see [3]).
Using this implementation, the total complexity is O(mn # ),
6. TRANSFORMATION ALGORITHM
This section describes how event expressions can be automatically
transformed into equivalent expressions that allow
a more e#cient detection. The transformation algorithm is
based on the algebraic laws describing how temporal restrictions
can be propagated through an expression, presented in
Theorem 3.
To simplify the presentation, we extend the algebra syntax
with two constructs. The symbol # is added to the
temporal domain to allow temporally restricted and unrestricted
expressions to be treated uniformly. Formally, we
define A. Since the improved sequence algorithm is
defined for sequences A;B where B # B# , we introduce the
notation A;# B to label sequences with this information.
The transformation algorithm is based on a recursive function
that takes an expression and a time as input, and returns
the transformed expression and a time. This function
is defined in Figure 5. The input time represents a temporal
restriction that can be applied to the expression without
changing the meaning of the expression as a whole. The
returned time represents a temporal restriction that can be
applied to the transformed expression without changing its
meaning.
The meaning of an expression is unchanged by the algo-
rithm, and sequences are labeled correctly, as specified by
the following theorem. For the proof, the reader is refered
to [3].
Theorem 8. If transform(E, #E # then
Also, all sequences in E # are on the labeled form A;# B, where
holds.
Trivially, the time complexity of the transformation algorithm
is linear with respect to the size of E. If no sequence
in E # is labeled with #, then E # (and consequently E) can
be correctly detected with limited memory.
Example 5. We have transform((B;B)2 -(P;(P+T)),
#(B;0B)2-(P;2 (P+T)2), 2# which means that this expression
can be detected with limited memory. Note that the temporal
restriction in the left subexpression of the negation
has been propagated to the right subexpression, making it
detectable with limited memory.
7. CONCLUSIONS AND FUTURE WORK
We have presented a fully formal event algebra with operators
for disjunction, conjunction, negation, sequence and
temporal restriction. To allow an e#cient implementation, a
formal restriction policy was defined. This restriction policy
is applied to the expression as a whole, rather than to the
individual operator occurrences, which means that a user
of the algebra is not required to understand the e#ects of
nested restrictions.
A number of algebraic laws were presented that facilitate
formal reasoning and justify the algebra semantics by
showing to what extent the operators comply with intuition.
We presented an imperative algorithm that computes a restricted
version of the event stream specified by the algebra
semantics, in accordance with the restriction policy. For the
user of the algebra, this means that at any time when there
is one or more occurrences of the composite event, one of
them will be detected by the algorithm. Finally, criteria
under which detection can be performed with limited resources
were identified, and we described an algorithm by
which many expressions can be transformed to meet these
criteria.
Our ongoing work includes investigating how to combine
the algebra with languages that specifically target reactive
systems, in particular Esterel [2], FRP [13, 15] and Timber
[5]. We are also considering extending the algebra with
a delay operator to allow the definition of timeout events,
and adding support for manipulating the values associated
with event occurrences.
8.



--R

Actions and events in interval temporal logic.
The Esterel-V5 Language Primer
An intuitive and resource-e#cient event detection algebra
An interval-based algebra for restricted event detection
The semantic layers of Timber.
An expressive event specification language for active databases.
Two approaches to event definition.
Events in an active object-oriented database system
COMPOSE: A system for composite specification and detection.
A logic-based calculus of events
A unified approach for specifying timing constraints and composite events in active real-time database systems

Functional reactive programming
Event correlation: Language and semantics.

--TR
A logic-based calculus of events
Snoop: an expressive event specification language for active databases
Functional reactive programming, continued
Event-Driven FRP
COMPOSE
Two Approaches to Event Definition
A Unified Approach for Specifying Timing Constraints and Composite Events in Active Real-Time Database Systems
event algebra;reactive systems;resource-efficiency;event detection