The increasing number of applications that require processing and analyzing high-throughput information in real time has fostered a new eld of study known as Complex Event Processing (CEP). The claimed objective of CEP is to develop techniques that are able to cope with the high-throughput requirements of modern Big Data applications. Also, it is commonly argued that CEP systems are di erent from relational reactive systems such as Active Database Management Systems (ADBMSs) or Data Stream Management Systems (DSMSs) because the latter see new data elements as database transactions (generally insertions or deletions) whose order is not relevant. On the contrary, CEP systems see new data elements as events (e.g. sensor measurements) whose arrival time and order have a semantic meaning. Unfortunately, these di erences come from a high-level description of the underlying applications, but do not reveal fundamental computational di erences between the requirements of CEP systems and relational systems. Moreover, recent developments in Dynamic Query Evaluation (DQE) show that general techniques in the relational setting can be more e cient than current CEP algorithms. In this paper, we study whether there is a fundamental di erence between the computational requirements of CEP and DQE. To answer this question, we identify two concrete assumptions of CEP and investigate their e ects in terms of evaluation complexity. Concretely, we show a realistic CEP query that, if the Online Matrix-vector multiplication (OMv) conjecture holds, cannot be evaluated with sub-linear time per tuple followed by sub-linear-delay enumeration, but under the CEP assumptions can be evaluated with constant time per tuple followed by constant-delay enumeration. Sub-linear here means O(n1 "), where n is the size of the active domain.
In recent years, analyzing high-throughput streams in real time has become a
crucial task for many communities. Examples range from Stream Processing [
The term Dynamic Query Evaluation (DQE) refers to techniques whose aim
is to e ciently maintain an up-to-date version of a query result under updates
to an underlying database. DQE is usually based on a form of Incremental View
Maintenance (IVM) [
Complex Event Processing (CEP) refers to techniques where the objective
is to detect certain temporal patterns in a high-throughput data stream.
Therefore, elements in the input stream are not seen as database transactions but as
events, that represent real-world observations and that thus cannot be retracted.
Moreover, the order at which these events arrive to the system has a semantic
meaning; CEP patterns commonly express sequences based on this temporal
order. CEP and DQE are usually considered very di erent as is perhaps best
illustrated by Cugola and Margara who, in their well-known survey [
This hence raises the question: is there a fundamental computational difference between CEP and DQE ? In order to answer this question, we take a fundamental viewpoint, and de ne CEP systems as systems in which the input is a stream of tuples. In line with the fact that events cannot be retracted, the stream in insertion-only. Moreover, in line with the fact that arrival order is important, we require that every tuple contains a special attribute that represents the arrival time to the system. The value of this attribute is globally increasing across the stream. In contrast, DQE systems take as input a stream of both insertions and deletions with no further assumption on the attributes.
Concretely, we answer the question by showing a query that can be answered e ciently under the CEP assumptions, but not under the DQE assumptions. The notion of e ciency here corresponds to process each new event in constant time (under data complexity) and be able to output the results at any moment with constant-delay enumeration. 2
Tuples, databases, predicates and streams. We assume the existence of three disjoint in nite sets: A domain D, a set of variables fx; y; z; : : :g (which play the role of attribute names), and a set of relation names fr; s; t; : : :g.
An atom is an expression of the form r(x), where r is a relation name and
x is a nite set of variables. A tuple over r(x) (or simply over x) is a function
t : x ! D. A relation R over r(x) is a nite set of tuples over r(x). A schema S is
a nite set of atoms with di erent relation names, and a database D over schema
S is a set of relations, one over each atom of S. A stream over schema S is a
possibly in nite sequence S = (S[
Finally, a predicate over x is a (not necessarily nite) decidable set P of tuples
over x. For example, if x = fx; yg then P (x) = f(x; y) j x < yg is the predicate of
all tuples (x0; y0) 2 D2 satisfying x0 < y0. As usual, we use shorthand notation
for predicates (e.g. P (x) = x < y) and write P (t) to indicate that t 2 P .
Query Language. We follow the query language of Generalized Conjunctive
Queries (GCQs) introduced in [
De nition 1. A GCQ is an expression of the form y r1(x1) on
m on rn(xn) j ^ Pi(zi) where r1(x1); : : : ; rn(xn) are atoms, P1; : : : ; Pm are predicates over z1; : : : ; zm, respectively, and both y and Sim=1 zi are subsets of Sin=1 xi.
Given a database D and a GCQ Q of the form (1), the evaluation of Q over
D is denoted Q(D) and is performed in the expected way: rst compute the
natural join r1(x1) on on rn(xn), from the result keep only those tuples that
satisfy all predicates P1; : : : ; Pm, and nally project them over y. We illustrate
the semantics of GCQs with an example, for a full de nition see [
x;y;ts3 r(x; ts1) on s(x; y; ts2) on t(y; ts3) j ts1 < ts2 < ts3 ^(ts3 ts1) < 5) (2)
Intuitively, the query speci es that we should take the natural join between
r(x; ts1), s(x; y; ts2) and t(y; ts3), from this result keep only those tuples that
satisfy ts1 < ts2 < ts3 and (ts3 ts1) < 5, and nally project over fx; y; ts3g.
From the de nitions of databases, streams and the semantics of GCQs it can be
seen that we use set semantics. We stress, however, that this is only for simplicity,
and the results in this paper can be extended easily to bag semantics.
GCQs for Complex Event Processing. It has been claimed in the past that
CEP languages are generally informal and non-standard [
In contrast to GCQs, CEP languages usually have sequencing and time
windows as primitives. For example, under the assumption that ts1, ts2 and ts3
represent arrival order, query (2) can be written equivalently in SASE [
SEQ(r,s,t) WHERE r.1 = s.1 AND s.2 = t.1 WITHIN 5 seconds: The SEQ operator indicates that the events must arrive in the expected order and the WITHIN clause that they have to occur within a time window of 5 seconds, avoiding the explicit inequalities over the timestamps. The WHERE clause indicates that the rst attribute of r must be equal to the rst attribute of s and the second attribute of s must be equal to the rst attribute of t, which is equivalent to using variable names in GCQs.
For the purposes of this paper, we only require the CEP features of sequencing, time windows and ltering; it is not relevant that other features of CEP languages like iteration (Kleene closure) are not expressible by means of GCQs.
Since we are interested in evaluating GCQs over streams, we need to formally
de ne what evaluation means. Traditionally, the objective of DQE algorithms
like IVM has been to maintain the current version of the result materialized
at all times. Therefore, the processing of an update includes the corresponding
modi cation of the materialized result. In contrast, recent DQE algorithms do
not maintain the full materialized output, but a data structure from which the
result can be generated [
When evaluating a query Q over a stream S, the elements of S are consumed one by one in order. Once the ith element of S is processed, we expect to be able to generate Q(S[1::i]) (recall that S[1::i] is the database produced by S up to position i). Following this, a DQE algorithm A for Q consists of a data structure DA and two routines PROCESSA and ENUMA such that for every stream S: { when PROCESSA receives an element of the stream, it can modify DA and; { after PROCESSA has been called with the rst i elements of the stream, ENUMA enumerates Q(S[1::i]) from DA.
Complexity. We consider query evaluation in main memory and measure time
under data complexity [
The e ciency of enumeration is slightly more involved, since it is measured
as the delay that the enumeration procedure takes between generating two
consecutive results [
De nition 2. A routine ENUM with access to a data structure D supports enumeration of a set E if ENUM(D) outputs each element of E exactly once. Moreover, ENUM(D) enumerates E with delay d 2 N, if when ENUM(D) is invoked, the time until the output of the rst element; the time between any two consecutive elements; and the time between the output of the last element and the termination of ENUM(D), are all bounded by d.
Given a function f from streams to natural numbers, we say that a DQE algorithm A for query Q provides f -delay enumeration if for every stream S and every i 2 N, after PROCESSA has processed the rst i elements of S, ENUMA enumerates Q(S[1::i]) with delay O(f (S1;i)). If f is a constant function, A is said to provide constant-delay enumeration (CDE) of Q(S[1::i]). Computational Model. Another important consideration when studying the e ciency of DQE algorithms is the computational model. Indeed, when dealing with ne-grained notions like constant-time per update or CDE, the computational model might a ect the complexity.
We follow the extended RAM model from [
We further assume the existence of linear-size hash-maps. Concretely a hash
map H over a set of variables x can store an arbitrary data structure H(t) for
each tuple t over x, using size proportional to the sum of the sizes of the data
structures stored. Moreover, given a tuple t we can access H(t) in constant time.
These assumptions amount to perfect hashing of linear size [
As mentioned in the introduction, the di erences between DQE and CEP generally come from high-level descriptions of the targeted applications, and not from fundamental di erences in their processing techniques. It makes sense then to discuss whether CEP really requires new computational insights for achieving better performance, or DQE algorithms are already optimal for the requirements of CEP. To understand this, we rst need to identify the concrete requirements and restrictions that distinguish CEP from DQE. As discussed in the introduction, CEP adds to the dynamic evaluation problem (1) the requirement of selecting tuples based on their arrival times and (2) the restriction that witnessed tuples correspond to real-world events and thus cannot be retracted. This can be concretely re ected in GCQ evaluation by 1. interpreting some attributes as timestamps and assuming that they occur in a globally increasing manner, and 2. assuming that streams are insertion-only.
We show that taking these assumptions into account can make a di erence in terms of complexity of DQE algorithms. Concretely, we prove that the GCQ Q = y;ts3 (r(x; ts1) on s(x; y; ts2) on t(y; ts3) j ts1 < ts2 < ts3 ^ (ts3 ts1) < 5) can be evaluated with constant update time followed by CDE when restricted to streams that satisfy the two assumptions above, but not in general.
We start by presenting the hardness result. We show that there is no DQE
algorithm that evaluates Q over streams with sub-linear update time followed
by sub-linear-delay enumeration. Here, sub-linear means O(n1 "), where n is
the number of elements in the active domain of the database produced by
the processed portion of the stream. We use the dichotomy proved recently
by Berkholz et. al. in [
Lemma 1. If the OMv conjecture holds, there is no DQE algorithm for Q = y;ts3 (r(x; ts1) on s(x; y; ts2) on t(y; ts3) j ts1 < ts2 < ts3 ^ (ts3 ts1) < 5) with sub-linear time per update followed by sub-linear-delay enumeration. Proof (Sketch). We prove this by contradiction. Assume that there is a DQE algorithm A that evaluates Q with sub-linear update time and sub-linear-delay enumeration. We use this algorithm to de ne a second algorithm A0 that evaluates query Q0 = y(u(x) on v(x; y) on w(y)) with the same bounds. First, the data structure DA0 is exactly the same as the data structure DA. Upon the arrival of an element (t; ), the routine PROCESSA0 will simply call PROCESSA(u; ), where u is de ned as follows: if t = u(x0), then u = r(x0; 1); if t = v(x0; y0), then u = s(x0; y0; 2); if t = w(y0), then u = t(y0; 3). Since PROCESSA(u; ) takes sub-linear time, it is clear that PROCESSA0 (t; ) also takes sub-linear time. Finally, the routine ENUMA0 is equivalent to ENUMA except for the fact that it needs to project out ts3. It is clear that this process will generate the expected output with sub-linear-delay enumeration: the lters will be satis ed because ts1 is always 1, ts2 is always 2 and ts3 is always 3. Moreover, enumeration is correct and without duplicates (even though we project away ts3) exactly because ts3 is always 3. We hence have our desired contradiction as we have constructed a DQE algorithm with sub-linear update time followed by sub-linear-delay enumeration that evaluates Q0, which is not q-hierarchical. tu
Next, we show a DQE algorithm A that evaluates Q with constant time per update followed by CDE under the assumptions that streams are insertion-only and ts1, ts2 and ts3 arrive in a globally increasing fashion. We start by presenting the data structure DA, to then describe how PROCESSA maintains it. After the rst i elements of S are processed, DA contains three elements. { A hash-map HR that maps each x to the maximum ts1 for which r(x; ts1) 2
S1;i. Intuitively, HR(x) is the last time that x occurred in an r tuple. { A hash-map HS mapping each y to a timestamp. The timestamp HS (y) is the largest ts1 for which there exist tuples r(x0; ts1) and s(x0; y; ts2) in S1;i satisfying ts1 < ts2. { A relation T over fy; ts3g that contains the actual output Q(S[1::i]).
Having access to DA the enumeration procedure is trivial, since the output is already materialized in relation T of DA. We proceed then to describe the update process.
Update processing. The objective of PROCESSA, shown in Algorithm 1, is to maintain all elements of DA consistent with the de nitions given above. Whenever a new tuple t of type r(x; ts1) arrives, it su ces to insert ts1 as the last timestamp of x (Line 3). Note that we can only do this because we assume that timestamps arrive in a globally increasing fashion. As such, the value of ts1 is the maximum across all timestamps seen so far. When a tuple t = s(x; y; ts2) arrives, we need to check if the x value has already occurred in an r tuple (Line 5), and if so, update the value of HS (y) to HR(x). Again, this maintains the consistency because we know that ts2 is larger than HR(x). Finally, when a new tuple t of type t(y; ts3) arrives, we check if we need to insert it into T . To this end, we only need to check the value HS (y), as this value tells us if there are matching tuples of type r and s in the required time window (Line 8).
It is clear that PROCESSA runs in constant time under our computational model. Also, because we assume that ts1, ts2 and ts3 are globally increasing, it is easy to see that PROCESSA correctly maintains the elements of DA. Theorem 1. There exists a DQE algorithm that evaluates Q with constant time per tuple and CDE under the assumption that streams are insertion-only and that attributes ts1, ts2 and ts3 are globally increasing.
In this section we have shown a computational di erence between CEP and DQE, giving a concrete motivation for studying techniques that di er from those used in the relational setting. We conclude by further discussing this di erence and providing insight into the particular aspects that might make a query easy to compute in a CEP setting.
We have presented the di erence between CEP and DQE by means of a very
particular query. We decided to present this query because (1) it features both
sequencing and time windows, making it realistic for CEP (2) the algorithm
to evaluate it with constant time per update followed by CDE allows for a
clear presentation. Nevertheless, one possible criticism is that this query is too
simple, because every new event can generate at most one output tuple, and
therefore constant-delay enumeration is easy to achieve by materializing the
output (which is actually what we do). This is a very valid argument; queries for
which a single tuple can generate multiple outputs are indeed harder to evaluate.
One possibility to present such a query would have been to add variable x to
the output of Q (as presented in Query (2) of Example 1). In this case, we can
still improve the evaluation performance by using dynamic fractional cascading
techniques [
Apart from structural properties of the query, we can also look at the CEP assumptions. At the moment, we do not know whether both assumptions (insertiononly streams and globally-sorted timestamps) are required, nor how is complexity a ected if we remove each of them separately. We envision this and a general understanding of the query properties that a ect complexity as future work.
Finally, in CEP it is common to distinguish between push-based and
pullbased systems (see for example [