This chapter is from the book
This chapter is from the book
This chapter is from the book
8.7 Relational Operators and Complex Patterns
Relational operators let us write patterns that specify two or more events and a relationship between them. Relational operators are needed to write patterns that match complex behavior in a system.
In the simplest case, relational operators specify how two events are related—for example, whether the events must happen independently or one must cause the other, whether they must happen one before the other or at the same time, and so on. In general, we can use relational operators to specify how two posets are related. So we can start with basic patterns and build more and more complex patterns.
Relational operators are binary operators. A binary relational operator expresses a relationship between two posets. Patterns written with relational operators are called complex patterns to distinguish them from basic patterns, which specify single events.
Example 1: Complex patterns illustrating use of relational operators
1. (Dollars X) Withdraw(X, Accnt#123)Deposit(X); 2. Withdraw ||Withdraw; 3. (Event E, E' ) E(origin is "Bonnie") ~ E'(origin is "Clyde");
The first pattern uses the causal operator, .
It matches whenever a Withdraw event from account Accnt#123 causes a Deposit
of the same Dollar amount (to any account). So the pattern matches posets consisting
of two causally related events, a Withdraw from Accnt#123 and a Deposit of the
same sum of money. Whenever the pattern matches, X is bound to the Dollar amount.
Figure 8.2 shows a poset that contains exactly one match of this pattern.
)
Figure 8.2: Examples of matches of complex patterns
The second pattern uses the parallel operator,||. It matches any two independent Withdraw events. The parameter values in the events do not matter; only their independence determines whether they match the pattern. Figure 8.2 shows a poset that contains two matches of this pattern. If the relational operator in pattern 2 was ~ instead of ||, there would be three matches (see the third example).
The third pattern uses the "any" relationship operator, ~, and placeholders that have the most general type, the Event type. This pattern matches any two events, provided "Bonnie" performs one of them (is its origin) and "Clyde" performs the other. Since we don't know what these desperadoes might do, looking for any action rather than specific actions is the best strategy. The events may be in any relation to one another. This means that the pattern can match events that are causally related or that are independent. Whenever the pattern matches, E and E' will be bound to the events. There are six matches in Figure 8.2. The poset shows "Bonnie" and "Clyde" as separate threads of control that generate events and synchronize at two points.
8.7.1 Relational Operators
There are three categories of relational operators: structural, logical, and set operators. Table 8.2 shows a complete list of the relational operators in Rapide-EPL and what they mean. P and Q are patterns, either basic patterns that match single events or complex patterns that match posets.
Structural operators specify the causal structure and timing of matching
posets. For example, P Q
tells us that the events matching P must all be in the causal history of all
the events in the match for Q. Note, by the way, that the events matching P
don't have to immediately precede those matching Q. For example, a grandfather
is a causal ancestor of a grandchild.
The independence operator, P ||Q, requires that all the events matching P must be independent of all the events matching Q.
The timing operator, P <Q, specifies that all the events matching
P must have timestamps less than any timestamp of an event in the match for
Q. So it specifies a similar structure as but
for timing instead of
Table 8.2: Relational Operators in RAPIDE-EPL
|
Operator Name |
Description |
|
|
Structural operators |
|
|
| P |
causes |
A matching poset consists of two subposets, one matching P and one matching Q so that all events in the match of Q are caused by all the events in the match of P. |
|
P || Q |
independent |
A matching poset consists of two subposets, one matching P and one matching Q so that each event in the match of P is independent of every event in the match of Q, and conversely. |
|
P <Q |
before |
Timing: a matching poset consists of two subposets, one matching P and one matching Q so that any event in the match for P has an earlier timestamp than all events in the match for Q. If there are multiple clocks, a particular clock, C, can be referenced as a parameter of <. |
|
Logical operators |
|
|
|
P and Q |
and |
The events in a matching poset must match both P and Q. |
|
P or Q |
or |
The events in a matching poset match P or Q. |
|
P not Q |
not |
A matching poset must match P and not contain any subposet that matches Q. |
|
Set operators |
|
|
| P |
union |
A matching poset consists of two subposets, one matching P and the other matching Q. |
|
P ~Q |
disjoint union |
A matching poset consists of two disjoint subposets; one matches P and one matches Q. |
causality. If events have timestamps from more than one clock, the relevant clock is an explicit parameter of the < operator, written as <C.
Logical operators require a poset to match a logical combination of two patterns. It must match both patterns, either pattern, or one pattern and not the other.
The set operators, union (
) and disjoint union (~), require a poset to consist of subposets
that each match one of two patterns but don't require any causal or timing
relationship between the events in the subposets (that is, no structure). For
example, P and Q requires the poset to match both patterns, whereas P
Q requires the poset to consist of two subposets, each matching one of the patterns.
Rapide-EPL contains a rich set of relational operators because it was developed for research into CEP. It is unclear which of the logical and set operators are the most useful. Implementation of efficient pattern matching for some of these operators is challenging and demands smart algorithms.