Complex Event Recognition under Time Constraints: Towards a Formal Framework for Efficient Query Evaluation

Complex Event Recognition (CER) establishes a relevant solution for processing streams of events, giving users timely information. CER systems detect patterns in real-time, producing complex events and generating responses to them. In these tasks, time is a first-class citizen. Indeed, the time-sequence model distinguishes CER from other solutions, like data stream management systems. Surprisingly, until now, time constraints are usually included in CER query languages and models in a restricted way, and we still lack an understanding of the expressiveness and of efficient algorithms concerning this crucial feature: time. This work studies CER under time constraints regarding its query language, computational models, and streaming evaluation algorithms. We start by introducing an extension of Complex Event Logic (CEL), called timed CEL, with simple time operators. We show that timed CEL aids in modeling CER query languages in practice, serving as a proxy to study the expressive power of such languages under time constraints. For this purpose, we introduce an automata model for studying timed CEL, called timed Complex Event Automata (timed CEA). This model extends the existing CEA model with clocks, combining CEA and timed automata in a single model. We show that timed CEL and timed CEA are equally expressive, giving the first characterization of CER query languages under time constraints. Then, we move towards understanding the efficient evaluation of timed CEA over streams concerning its determinization and efficient algorithms. We present a class of timed CEA that are closed under determinization; furthermore, we show that this class contains swg-queries, an expressive class of CER queries recently introduced by Kleest-Meißner et al. Finally, we present a streaming evaluation algorithm with constant update time and output-linear delay for evaluating deterministic monotonic timed CEA with a single clock, which have only less equal or greater equal comparisons.