On the Difference between Complex Event Processing and Dynamic Query Evaluation

Abstract

The increasing number of applications that require processing and analyzing high-throughput information in real time has fostered a new field 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 different 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 differences come from a high-level description of the underlying applications, but do not reveal fundamental computational differences 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 efficient than current CEP algorithms.

In this paper, we study whether there is a fundamental difference between the computational requirements of CEP and DQE. To answer this question, we identify two concrete assumptions of CEP and investigate their effects 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(n^(1−ε))), where n is the size of the active domain.