CHAPTER 6

Patterns of Events

This chapter discusses classifying the problems we all face in dealing with the expected and the unexpected in the event cloud—and trying to avoiding false alarms. We will cover:

• Variables, templates, and patterns
• Single event patterns
• Patterns of multiple events
• Pattern matching
• Event patterns and state contexts
• Events and time: creation time, arrival time, time intervals
• Event patterns, state, and timing
• Causality, independence, and beyond today’s event processing tools
• Expressing event patterns—requirements for event pattern languages

This chapter gets into some technical aspects of event patterns. Although it may look technical at first sight, in fact it’s pretty simple stuff. If it gets to be hard going, skip it and move on—you can come back to it later. However, knowing some technical details about event processing helps to understand how a company can use events to solve some of the problems it may have to deal with. It also gives you some help in deciding what products have capabilities that would help with your problems.

Events contain information—here we’re talking about event objects. Very often, events add up to actionable information, not simply one event at a time, but many events over a time interval. Each event may carry just a little information, which by itself gives us nothing actionable, but a set of events happening in a specific pattern over time may add up to something of importance. Most applications of event processing are based upon searching for and detecting patterns of events within the event input.

Everybody has to deal with patterns of events in everyday living. There are traffic patterns on the way to work, patterns of credit card use, or patterns of behavior in children, and so on. Everyone has an intuitive understanding of the concept of a pattern of events. Indeed, it is possible to give an hour’s lecture on patterns of events without ever defining what a pattern is, and nobody complains! But that lecturer will find that there are many different ideas in the audience about exactly what he’s been talking about for the past hour.

So we need to define precisely what we mean by pattern of events. It is important to separate the concepts from all the details of input languages and event processing implementations involved in using various event processing engines. We must not confuse what the event pattern is with how we specify it using XYZ pattern language, etc. That will make life much simpler—as far as talking about patterns of events.

In this chapter we tie down the basic concepts involved in defining and using patterns of events. They are very simple. In contrast, the systems that process patterns can be quite sophisticated, depending upon the kind of input information they’re dealing with, how long it might take for a match of the pattern to show up, and whether the context in which a match happens is important. Some kinds of event pattern processing can happen in milliseconds; other kinds might take weeks or months. So entirely different kinds of systems may be employed in processing patterns of events. But the same basic concepts apply in all cases.

We go beyond the popular definitions of event patterns by introducing the use of causality between events in defining event patterns and its dual, independent events. Causality is a step into the future of event processing, since no commercial tools today provide explicitly for its use in event processing.

Events and Event Objects

As we saw in Chapter 3, event processing deals with event objects. Event objects represent events that happen or are thought of as happening. They contain information such as what the event is, where it happened, and the time that it happened. Also, we agreed to overload the two descriptions and refer to both events and event objects as simply events.

Overloading Two Meanings

Overloading is not new. It is used in programming languages to shorten the names of objects used in programs. That is, the same name is used for two different functions in the same program. Of course, there has to be some way to distinguish which function is being referenced (e.g., one function is used to compute temperatures and one to look up the times of day around the world). If there are no differences in their parameters or results, then they have to have different names!

Interestingly, the relativity physicists in the early twentieth century faced the same problem. The word event could mean either something that happens in the real world or a point in their four-dimensional relativistic model of the universe. They chose the same overloading solution for normal usage.1

Patterns and Pattern Matching

After event, the next concept in CEP is a pattern of events. One can find many different definitions of a pattern of events. And indeed, the concept of event patterns got very clouded during the early 2000s as commercial applications of CEP developed and the vendor community entered the picture. Each vendor had its own ideas, very much determined by its internal technical department’s capability to grapple with both the definitional issues involved in specifying patterns precisely and the implementation issues involved in detection. In some cases, a particular application area was also an influence on pattern language features. Popular computer languages were frequently extended to specify patterns of events, common examples being extensions of Java and SQL. This profusion of definitions only served to confuse the marketplace and the event processing community.

Here, in our examples, we will take a declarative approach to specifying event patterns using simple logical operations. We want to focus on what kinds of patterns are needed in CEP, so we will ignore the diversions of grafting event patterns onto various existing computer languages.

Single Event Patterns

The very first kind of event pattern is a single event pattern.

Example: A single event pattern:

A car runs a red light.

What makes this a pattern? Well, it “matches” or denotes any event where some car, any make or model, runs any red light, anywhere. The pattern has variables, car and red light. An event, say E, such as

Car with California license 8XYZ-123 ran the red light at California and Van Ness in San Francisco.

is an instance of the pattern. That is, E is one example of the pattern. How so?

Well, if we take the actual objects (i.e., values) in E, namely “Cal license 8XYZ-123” and “the red light at California and Van Ness in San Francisco” and substitute them for car and red light in the pattern, then the result is E.

But the same pattern can also match:

My BMW ran the red light at El Camino and Embarcadero in Palo Alto.

Indeed, our example, “a car runs a red light,” has a huge number of instances.

Definition: An event pattern is a template that specifies event objects called instances of the pattern.

A pattern contains variables. When the variables are replaced by objects (sometimes called values), the result is one of the events that the pattern denotes. And that event is called an instance.

Matching: The process of turning a pattern into an instance by replacing its variables by objects is called matching.

Another example of matching applied to a single event pattern is:

Tom buys a stock S for X dollars at time T

The variables are the stock S, the dollar price X, and the time of the transaction, T. But the name of the trader, Tom, is fixed—it is a constant in this pattern. So this pattern will only match buy transactions that Tom executes, like:

Tom buys IBM for 250 dollars at time 12:00 GMT.

This match is made by replacing the variables in the pattern by values as follows: S = IBM, X = $250, T = 12:00 GMT.

The first lesson here is that an event pattern definition must be able to express variable parts of events so that the definition can encompass many event instances. Natural language is not precise enough for today’s machine-processing technology, so what we have at the moment by way of machine-processable pattern definitions is cumbersome. For example, one style of definition is:

BuyStock (Tom, S, X, T)

That’s not very pretty, and it gets unreadable when used to express combinations of lots of events, but you get the idea! It would be called a first order logic specification of an event pattern.

Processing Patterns by Machine

The current generation of event pattern languages allows us to specify very clearly which parts of a pattern are variable, and also what types of values are denoted by the variable parts. There are a number of different ways this is done in commercial event processing languages.

Typically, the variables in event patterns are declared the same way as variables are declared in computer programs. Each variable is first defined as standing for values of a specific type such as integer, string, automobile, or traffic light. So machine-processable versions of our examples in the style of Java might look like:

Automobile car, Traffic light red_light; runs(car, red_light);

Stock Symbol S, Dollar X, Time T; BuyStock (Tom, S, X, T);

The pattern matcher, which is a computer program that detects instances, can tell using the declarations that car is a variable that must be replaced by an automobile and red light is a variable that must be replaced by a traffic light, and so on.

However, in our discussion we’ll omit types and variable declarations in most examples since they are intended for us humans. Remember that when we give event patterns to machines to process, the declarations will have to be included!

Remarks: One or another kind of event pattern matching is the basis for most applications of modern event processing. As we shall see, sometimes the patterns are so simple that matching is little more than testing the values of constants or membership of events in a list. More complex kinds of pattern matching can lead to difficult implementation issues where processing time may be critical.

There are two main focuses of computational effort in pattern matching:

Patterns of Multiple Events Using Operators

Event patterns generally involve more than one single event template. We often want to define patterns of several events. The events may be related to one another—for example, they might have common values or variables. So one issue in defining patterns containing multiple event templates is the ability to express commonality between the event templates in a pattern. Another issue is the set of operators that are available in whatever pattern definition facility you’re using.

For example, to express a coordinated stock trade, we might have a pattern such as:

when Tom buys a stock S for X dollars at time T then

Pete sells stock S for X + Δ dollars at time T’ < T + 1 min

Notice there are two event templates in this pattern, and they have variables in common: S, X, and T. These common variables express that the same stock is being bought by Tom and then sold by Pete at a higher price within one minute. Commonality is expressed by the variables common to both templates.

This pattern could be used to detect collaboration between traders to sell on the uptick created by a buy event. Of course, most of its instances would be coincidental trades close together in time. But some instances could be illegal collaborations between traders. If instances of this pattern are frequently detected in stock market feeds, more complex patterns would be used to decide whether collaboration is taking place.

In our example, when . . . then . . . is an operator that combines two events into a pattern of trading. Common examples are Boolean operators like A and B and A or B.

Common Boolean operators and their meanings are:

A and B	both patterns A and B must match.
A or B	at least one of the patterns A or B must match.
not A	the pattern A must not match.
when A then B	whenever pattern A matches then pattern B must match.
if A then B	if a match of pattern A occurs, then search for a match of B.

These are Boolean operators commonly used in event patterns. Their meanings overlap; that is, patterns with some operators can be rewritten using other operators.

To match A and B, a pattern matching program must simply match both A and B in any order.

To match when A then B, the pattern matcher must first match A and then match B (if A then B has a similar meaning).

Note that then is used as a part of two different operators, “when . . . then . . .” and “if . . . then . . .” (then is not an operator itself, but a part of these two operators).

Example 6.1 gives a straightforward and combination of two event templates with common variables.

Most event patterns involve timing, which we’ll deal with in the next section. In Example 6.2, the pattern would be used to monitor a call center that deals with enquiries and complaints from customers. The event input contains a stream of enquiries, complaints, responses, apologies, resolution reports, and so on. The pattern in this example will match if there is a complaint from a customer C and no response to that complaint is detected within a short time, Δ, and then there is no apology issued to that customer within 3*Δ. Event patterns such as this are used to monitor for violations of service level agreements, for example, at a call center. It is a common practice for a call center to have a contract requiring that customers must either receive a response or an apology in a timely manner.

Boolean operators can be used recursively in specifying event patterns. So it is quite common to see them nested in patterns. Sometimes nesting can get difficult to read, so most pattern languages will include facilities like pattern definitions for use to improve readability. Example 6.3 gives a clumsy example of nesting.

As we can see, this pattern is a mess to understand! Here’s an explanation; skip it if you want. Assume we are dealing with a cloud of loan applications in progress, each application going through various steps such as income review, house appraisal, credit check, and so on. In the days of easy credit, a large mortgage lender might be dealing with hundreds of applications per day, and the process steps might be farmed out to different specialty organizations around the world.

This pattern monitors the progress of each loan as it is processed. It requires a loan to pass the first three steps or to be denied within three days, or else to have its processing priority level raised at the third day.

We can use pattern definitions to improve readability and hence help us to see if the pattern correctly says what we want it to say.

Approval(A, H, L) = IncomeReview(A, okay) and HouseAppraisal(H, okay) and CreditCheck(A, okay)

So the pattern can be rewritten as,

If LoanApplication(A, H, L) at D then

Approval(A, H, L) or Denial(L) within D + 3 or RaisePriorityLevel(L) at D + 3;

This version of the pattern is easier to understand; more importantly, it is easier to see that it correctly expresses that a loan must either be approved or denied within three days or its processing priority must be raised.

Event Patterns and State

Often a pattern of events becomes important in specific circumstances. One example is traffic control. The rate at which cars are going through a set of freeway entrances will become a lot more important to a traffic-control system when the traffic density is high or there is an accident on the freeway. Another example is credit-card usage. A pattern of credit-card purchases might raise alarms in a monitoring system if the holder’s credit rating suddenly changes. In these examples, the pattern processor is not only matching the pattern against incoming events but also concurrently querying databases or alert lists. We call this pattern matching relative to state.

However, one does not want to burden an event processor with lots of state checks when its primary purpose is to process incoming events and match patterns related to an application. So in its normal state, the processor will do no state checking. A change in a database, such as traffic density becoming high, or a customer’s credit limit being reached, triggers changes in the state of the event processor. This could be as simple as adding an alert to a special alert list. Then the processor will check to determine whether certain circumstances apply when a specific person is the subject of a pattern check.

A common example of the use of state values is simply to count the number of times instances of a pattern have been detected in the recent past. If this number is high enough, then new instances of the pattern become more important than before—for example, an abnormal situation is happening.

Example 6.4 might apply to a cloud of input events that are SMS reports from field agents using mobile devices. Reports are processed in any order. The first rule increments values of Count and the second rule references those values. The when pattern matches whenever a report arrives that includes any symptom S on a list of symptoms. It references the list of symptoms in testing for a match. It then triggers an increment in a Count variable—which is another event. The if pattern matches when the value of Count goes above a Threshold and an Alert has not yet been issued. It then results in executing an alert. Count keeps track of how many reports with symptoms have been received. Symptoms is a database of disease symptoms. Symptoms and Count are called state values—that is, sets of values that are referenced in matching.

Another application of state in pattern matching is to market to customers with good records. Purchases made by good customers are treated as more important in Example 6.5.

Event Patterns and Time

Time is of the essence in many situations today, and nowhere more so that in processing events. Events carry information that goes stale very quickly. The more “up-to-the-minute” a system or activity is, the more it requires immediate attention and response.

Patterns used to detect important situations in event feeds nearly always refer to time and contain timing constraints. Pattern languages must contain powerful features for referring to time in all of its different uses in event patterns. But there is no standard approach to expressing time in event patterns. Indeed, the syntax of timing in every commercial event processing language is different. Here we survey some of common uses of time together with the kinds of syntax that is in use.

Activity at a Point in Time

Example 6.6 is an illustration of this simple concept.

Timely Reporting and Response

Another very common use of time is to specify that if something happens at one time, then something else must happen at another time. Typically, if some event happens, then search for some other pattern, but only within a short time beyond when the first event happened. For example, if the boiler gets too hot then the alarm must go off, quickly!

As Example 6.7 shows, timing is often used to ensure that something happens within a specified time after something else.

This pattern would be used to monitor stock market feeds for timely reporting of sales. Note that the use of timing here serves not only to specify a boundary in which a report must be made, but also to limit the search for a match. A sale event at Time1 will lead to a partial match, and a search for the corresponding report event to complete the match. But that search is limited by the boundary Time1 + Δ. A failure to match will likely trigger an action such as reporting a failure to report a sale, as shown in Example 6.8.

Time Windows and Focusing Search for Matches

Another use of time is to restrict the time in which an attempt to match a pattern needs to be made. Usually, the search is restricted to an interval of time, called a time window. A common notation for a time window is [T1, T2], where T1 and T2 are times and T1 ≤ T2. Example 6.9 shows one use of this strategy.

Realistic and Unrealistic Uses of Time as a Constraint

Time is often used to specify constraints on the performance of a system. Typically, if something happens, then a timing constraint will require something else to happen, within a specified time limit or a time window, as illustrated in Example 6.10.

But sometimes the use of time to specify system constraints can become unrealistic, difficult to understand, and more to the point, very difficult to monitor and to implement correctly. Example 6.11 expands the types of requirements.

This causes a race condition in evaluating whether the requirement is being violated because as it is being evaluated, the set of trades to which it should be applied is changing. It is called a race condition between the edge of the window as it “slides” and the evaluation of the requirement for a potential violation. We regard this as an impractical use of timing.

Example 6.12 is another example of impractical use of timing.

Proliferation of Timing Operators

There are many other operators that are in use in CEP tools put out by various vendors. Some of them are esoteric and peculiar to one vendor’s event pattern language. Most of them can be defined using the basic set of operators given above, together with event timing constructs such as at and time intervals. Often, various notations are intended as convenient shorthand. Some notations assume that event input is either a stream of events, or that events are processed in their order of arrival,2 as shown in Example 6.13.

Causality between Events

In CEP, an event pattern can include combinations of event templates together with timing conditions and state conditions. An important operator in CEP that is not yet available commercially is the causal relationship between sets of events.

It is very common to talk about events causing other events. For example, “did the car running the red light cause the accident?” Or “did that large sale of IBM stock cause the price to dip at 2:00 ~PM?” In fact, “cause” often goes by other names, a common one being “risk factor”: Is smoking a risk factor in premature death?

However, it is interesting to note the current situation regarding the use of cause in event processing. No commercial CEP tools or products so far have an ability to define event patterns in which some events cause other events. There are several reasons for this.

First of all, the definition of causality is clouded in philosophy, mystery, and confusion. The English philosopher Bertrand Russell once remarked: “The average married couple has sexual intercourse four thousand times during their married life, and they produce 2.4 children. If one were to slam a door four thousand times and hear a bang 2.4 times, would one conclude that slamming the door caused the bang?”

Second, few if any technical engineering teams in industry know how to implement the tracking of causal relationships between events, even if they could settle on a clear definition.

Third, commercial applications of CEP have been successful so far without employing causality between events. They have been able to get away with operators such as when . . . then . . . or if . . . then . . . or followed by applied to event streams. There has been little demand for causality from customers.

Fourth, causality would be a difficult concept to teach to marketing departments or to the current generation of customers for CEP.

And finally, in many event spaces it is often not known which events cause which other events. Or to say the least, such knowledge is far from complete!

Despite all these issues, there are many event spaces where causality is well known and easily determined—for example, in discrete event simulations and many event driven systems such as air traffic control systems, highway traffic systems, and natural disaster warning systems. The use of causality in specifying event patterns can lead to more precise and efficient detection of matches and avoidance of false alarms, because causality reduces the space of input events that need to be searched for possible matches.

No matter the trepidations of Bertrand Russell, there is a very simple definition of causality between events that is appropriate for event processing purposes. Notwithstanding the issues raised above, we predict that causality between events will become an important event operator in patterns in the future, both to improve the efficiency of the search for matches and to define important patterns precisely.

Causality: If event A had to happen in order for event B to happen, then A is a cause of B and we say, A caused B.

Note that this definition is given in terms of events (activities) rather than event objects. If there is a causal relation between two events, then it applies to the event objects representing those events. Also, an event may have several causes.

There is no universal test that can be applied to determine whether A is a cause of B. But in many event spaces, causality is well known. Each situation must be judged on the semantics of the event space individually. Consider Examples 6.14 and 6.15.

Remarks: This definition of causality was implemented in CEP tools in the Stanford CEP project going back to 1995 and used extensively in experiments in event processing applications—for example, in the analysis of discrete event simulations of processor designs and of network protocols. The tracking of causality between events in simulator output made analysis of the simulation results more efficient.

Causality between events is not to be confused with followed by in the order of arrival, or indeed in any stream order or time order. Events can arrive at a processing point in any order. That is, it is possible for A to cause B and for B to arrive before A at an event processor.

Operators for Causality and Independence

Causality between event patterns was expressed syntactically by the “→” operator in the Rapide event processing language.4 It would be appropriate to add this operator to our list of basic operators in the previous section, “Patterns of Multiple Events Using Operators.”

A → B means A had to happen in order for B to happen.

Note that “→” means the A is a cause of B, but it does not mean that A is the only cause of B.

The opposite relation to causality is independence. Two events happened independently of one another if neither is a cause of the other. The operator for independence in Rapide is “||.”

A || B means A is not a cause of B, and B is not a cause of A.

These operators are demonstrated in Examples 6.16 and 6.17.

Causality and Time

As one would expect, there is a relationship between causality between events and the time at which events happen. But it is weaker than one might expect.

Intuitively, an event that causes another event should be expected to happen earlier. That is usually the case, but not always!

If A causes B, it is possible for A and B to happen at the same time. But A cannot happen later than B.

This means that there’s a weak relationship between cause and time.

On the other hand, independence has no relationship with time at all. If A and B happen independently, they can happen at the same time or different times, as Figure 6.1 shows. Independence between events simply means that the events are not causally related. They can happen at the same time, but that is not necessary for them to be independent.

Repetitive and Unbounded Behavior

Some patterns of events must allow for events to be repeated, and sometimes the number of repetitions is not known when the pattern is written. So the pattern language must be able to express repetitions both when the number of “repeats” is known and when it is not known in advance. An additional problem is the need to be precise about which matches of a repeated activity should be detected. For example, if there are ten buy events in an input stream, do we want to detect the first buy, the first two buys, etc., or just the maximal sequence of all ten buys? The last case is sometimes called maximal match semantics5 and is usually what one wants. This is further discussed in Example 6.18.

Examples 6.19 and 6.20 demonstrate some applications of event pattern matching with repeated events that have seen recent commercial application.

Requirements for an Event Pattern Language

Perhaps this is where you hand this book, or this chapter, over to your IT group! It should help in discussing a choice between CEP products that you might consider purchasing.

Here is a summary of the features of event patterns that have been discussed in this chapter. This is a minimal set of features that should be provided in languages intended for event pattern searching in a general event input (i.e., an event cloud).

A and B	both patterns A and B must match
A or B	at least one of the patterns A or B must match
not A	the pattern A must not match
when A then B	whenever pattern A matches then pattern B must match
if A then B	if A is matched then search for a match of B
A → B	A causes B
A*	an unspecified number of A’s

Correctness and Other Questions

There has been little discussion in event processing literature of the correctness of implementations of pattern matching, nor indeed of the correctness of event processing engines in general. Also lacking is discussion of the adequacy of current event pattern languages, or whether users are able to express the patterns they want or understand the semantics of the pattern languages (e.g., does the pattern matching mean first-match semantics or maximal-match semantics).

Customers of CEP products should ask whether they are getting the correct matches, all the matches, only some matches, or perhaps only the first match or no matches where some do exist. But then, upon reflection, perhaps this situation is simply a symptom of software industry in general—and a reason for its users to evaluate products carefully and ask questions!

Clearly, these are research areas for event processing. But CEP tools are being applied in a wide variety of fields today, as we discussed in Chapter 5, and the fact that there are open questions is no reason not to go ahead with a CEP application. Simply recognize what you don’t know!

Notes

1 A. S. Eddington, Space, Time and Gravitation: An Outline of the General Relativity Theory, p. 45. (Cambridge, MA: University Press), 1920. www.archive.org/stream/spacetimegravita00eddirich#page/44/mode/2up

2 See Chapter 3.

3 Due to Dr. John Bates, Apama, Inc.

4 http://complexevents.com/stanford/rapide

5 Luckham, The Power of Events (Boston: Addison-Wesley, 2002) Section 8.9, p. 170, Example 1.

6 Note that then is a part of two different operators with slightly different meanings and is not an operator on its own.