A Formal Framework for Complex Event Recognition
A Formal Framework for Complex Event Recognition
复制标题
DOI：
10.1145/3485463
复制
发表时间：
2021-12-01
影响因子：
1.8
通讯作者：
Vansummeren, Stijn
中科院分区：
文献类型：
--
作者：
Grez, Alejandro;Riveros, Cristian;Vansummeren, Stijn
复杂事件识别（CER）已经成为需要实时处理和关联分布式数据源的技术的统一领域。CER在不同的领域都有应用，这就产生了大量表达和处理复杂事件的建议。但是，现有的CER语言缺乏清晰的语义，这使得它们难以理解和泛化。此外，没有通用的技术来评估具有明确性能保证的CER查询语言。在本文中，我们将着手为CER提供一个严格而有效的框架。我们提出了一种用于指定复杂事件的形式化语言，称为复杂事件逻辑（CEL），它包含了文献中使用的主要特征，并具有指称和组合语义。我们还形式化了所谓的选择策略，它只是作为对现有框架的设计扩展而呈现的。我们深入研究了语言设计中关于CEL的严格排序操作符和选择策略的权衡。有了定义良好的语义，我们讨论了如何通过使用一元过滤器评估CEL公式来有效地处理复杂事件。本文首先介绍了复杂事件自动机（complex event automata， CEA）的形式化计算模型，并研究了如何将带有一元过滤器的CEL公式编译成复杂事件自动机。此外，我们提供了有效的算法来评估事件流上的CEA，使用每个事件的恒定时间，然后是结果的输出线性延迟枚举。
Complex event recognition (CER) has emerged as the unifying field for technologies that require processing and correlating distributed data sources in real time. CER finds applications in diverse domains, which has resulted in a large number of proposals for expressing and processing complex events. Existing CER languages lack a clear semantics, however, which makes them hard to understand and generalize. Moreover, there are no general techniques for evaluating CER query languages with clear performance guarantees.In this article, we embark on the task of giving a rigorous and efficient framework to CER. We propose a formal language for specifying complex events, called complex event logic (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. We give insight into the language design trade-offs regarding the strict sequencing operators of CEL and selection strategies.With a well-defined semantics at hand, we discuss how to efficiently process complex events by evaluating CEL formulas with unary filters. We start by introducing a formal computational model for CER, called complex event automata (CEA), and study how to compile CEL formulas with unary filters into CEA. Furthermore, we provide efficient algorithms for evaluating CEA over event streams using constant time per event followed by output-linear delay enumeration of the results.