Title: Foundations of Complex Event Processing,
Abstract: Complex Event Processing (CEP) has emerged as the unifying field for
technologies that require processing and correlating distributed data sources
in real-time. CEP finds applications in diverse domains, which has resulted in
a large number of proposals for expressing and processing complex events.
However, existing CEP languages lack from a clear semantics, making them hard
to understand and generalize. Moreover, there are no general techniques for
evaluating CEP query languages with clear performance guarantees.
In this paper we embark on the task of giving a rigorous and efficient
framework to CEP. We propose a formal language for specifying complex events,
called CEL, that contains the main features used in the literature and has a
denotational and compositional semantics. We also formalize the so-called
selection strategies, which had only been presented as by-design extensions to
existing frameworks. With a well-defined semantics at hand, we study how to
efficiently evaluate CEL for processing complex events in the case of unary
filters. We start by studying the syntactical properties of CEL and propose
rewriting optimization techniques for simplifying the evaluation of formulas.
Then, we introduce a formal computational model for CEP, called complex event
automata (CEA), and study how to compile CEL formulas into CEA. Furthermore, we
provide efficient algorithms for evaluating CEA over event streams using
constant time per event followed by constant-delay enumeration of the results.
By gathering these results together, we propose a framework for efficiently
evaluating CEL with unary filters. Finally, we show experimentally that this
framework consistently outperforms the competition, and even over trivial
queries can be orders of magnitude more efficient.