🤖 AI

Efficient Temporal Datalog Materialisation for Composite Event Recognition

本文通过将不同的事件规范语言映射到统一的时序 Datalog 框架，并引入流式触发图，以解决比较这些语言所面临的挑战，从而实现对高速数据流的高效、可泛化的复合事件识别。

原作者： Periklis Mantenoglou

发布于 2026-05-06

📖 1 分钟阅读☕ 轻松阅读

原作者： Periklis Mantenoglou

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一位指挥着一支庞大、高速运转的乐团的指挥家，每位乐手都在演奏不同的乐器，而音乐每一秒都在变化。你的任务是识别音乐中特定且复杂的模式——例如“小提琴演奏高音的同时，鼓连续三次敲击出慢节奏”——一旦该模式出现，立即拉响红色警报。

这就是**复合事件识别（Composite Event Recognition, CER）**所面临的挑战。在现实世界中，这不仅仅关乎音乐；它关乎在智慧城市中识别安全威胁、在银行检测欺诈行为，或监控整个配送卡车车队。问题在于，不同的团队使用不同的“乐谱”（语言）来描述这些模式，而他们的“指挥家”（推理器）彼此无法沟通。

本文通过简单的类比来解决这一问题：

1. 问题：方言过多

想象一群侦探试图破解一起犯罪案件。一名侦探使用“事件演算（Event Calculus）”，另一名使用"LARS"，第三名使用“时序逻辑 Datalog（Temporal Datalog）”。他们都在描述同一处犯罪现场，但使用的词汇和句子结构各不相同。

问题所在：如果侦探 A 发现了一条线索，侦探 B 可能无法理解。他们难以轻松比对笔记，也无法为特定任务选用最佳侦探，因为语言不匹配。
本文目标：创建一个“通用翻译器”，将事件演算和 LARS 的特定方言转换为一种统一的通用语言，即时序逻辑 Datalog→⊖（Temporal Datalog→⊖）。

2. 通用翻译器：时序逻辑 Datalog→⊖

作者创建了一种特殊的逻辑语言版本（一套计算机规则），作为这一共同基础。

禁止时间旅行：该语言有一条严格规则：你只能查看过去或现在，不能查看未来。这就像说：“我只能基于已经发生或正在发生的事情做出决策。”这防止了系统因等待尚未到达的数据而陷入困惑或停滞。
分层否定：这是一种高级说法，意指规则被组织成层级以避免矛盾。想象一栋有多层楼的建筑。你只能从较高的楼层向下查看较低楼层的情况，绝不能反过来。这保持了逻辑的清晰，防止系统陷入“是真的吗？不，是真的吗？不……"的循环。

3. 引擎：流式触发图（Streaming Trigger Graphs, STGs）

一旦规则被翻译成这种通用语言，计算机就需要一种方法在数据流入时即时处理它们。作者发明了一种新引擎，称为流式触发图（STGs）。

将 STG 想象成工厂中的智能装配线：

工厂车间：数据“流”（事件）沿着传送带流动。
工人（节点）：流水线上的每位工人检查特定条件。
“遗忘”按钮：在普通工厂中，你可能会保留制造过的每一个零件。但在这条高速工厂中，如果某个零件对于当前产品来说过于陈旧而无用，工人会立即将其丢弃。本文称之为**“遗忘”**。它通过仅保留与当前时刻仍相关的事实，节省了海量内存。
安全网（否定）：有时工人需要知道“某个特定事件是否未发生？”STG 拥有一种特殊机制（如同持有“禁止进入”名单的保安），一旦检测到被禁止的事件发生，会立即阻止产品继续流转。

4. 实际应用方式

本文展示了如何将来自两种主要“方言”（事件演算和 LARS）的复杂规则转换为此通用语言。

示例：如果规则说“若某设备在过去 2 小时内被维修过，则将其标记为‘已验证’"，翻译器会将其转换为一条简单规则，检查当前时间减去 2 小时。
结果：STG 引擎随后运行这些转换后的规则。当新数据到达时（例如发生了一次维修），引擎会即时更新其知识，检查规则，并输出结果（例如“设备已验证”），而不会减速或陷入停滞。

5. 为何这很重要

本文声称，通过进行这种转换并使用这种新引擎：

统一性：你现在可以公平地比较不同的事件语言，因为它们都在同一引擎上运行。
效率：“遗忘”机制和图的智能组织意味着系统能够极快地处理海量数据，而不会耗尽内存。
正确性：作者从数学上证明了这种转换不会改变规则的含义。如果原始规则说"X 为真”，转换后的版本也会说"X 为真”。

总结

简而言之，作者构建了一个用于事件检测语言的通用翻译器，以及一条超高效、节省内存的装配线（流式触发图）来处理这些语言。这使得计算机能够可靠地在高速数据流中识别复杂且对时间敏感的模式，而不会因语言差异感到困惑或因空间不足而停滞。

技术摘要：用于复合事件识别的高效时序 Datalog 物化

问题陈述

复合事件识别（CER）框架对于在高速符号事件流中检测关键情况（例如安全威胁）至关重要。这些框架通常包含一个用于定义模式的事件规范语言（ESL）和一个用于评估这些模式的流推理器。然而，现有的 ESL 往往被孤立研究，这使得在表达能力方面进行比较变得复杂，并掩盖了其相关推理器的适用范围。此外，用一种 ESL 表达的模式通常无法被忠实或最优地翻译成另一种 ESL，从而阻碍了为特定问题使用最合适的推理器。目前缺乏一种统一的形式化方法，既能嵌入主流的 ESL，又能支持在无限流上进行高效、低延迟的推理。

方法论

作者提出了一种以时序 Datalog $^{\rightarrow}_{\ominus}$ 为核心的统一方法，这是时序 Datalog 的一个变体，具有分层否定且无未来依赖（前向传播）的特性。该方法包含两个主要组成部分：

1. 将 ESL 嵌入时序 Datalog $^{\rightarrow}_{\ominus}$

本文展示了从两种主流的基于逻辑的 ESL 到时序 Datalog $^{\rightarrow}_{\ominus}$ 的映射，并证明了这些翻译在查询回答方面是等价保持的：

Plain LARS： 基于带有窗口算子的答案集编程（ASP）的 LARS 语言的一个片段。该翻译（算法 2）通过引入辅助谓词和实例化时间变量来处理时序模态（ $\diamond$ 、 $\square$ ）和窗口算子（ $\boxplus$ ）。它确保生成的程序是前向传播且时序分层的。
带延迟效应的事件演算（ECDE）： 一种用于大规模 CER 的事件演算变体。该翻译（算法 3）通过为每种类型和值引入特定谓词来消除函子（事件/流类型）。它将惯性定律、延迟效应和静态流定义编码为前向传播规则，并确保时序分层。

2. 流触发图（STGs）

为了支持时序 Datalog $^{\rightarrow}_{\ominus}$ 的高效物化，作者提出了流触发图（STGs），这是触发图（TGs）的扩展。标准 TG 不足以支持，因为它们原生不支持否定，也不支持流推理所需的时间变量无限实例化。

流执行图（SEGs）： STGs 建立在 SEGs 之上，SEGs 扩展了执行图，包含：
- 否定： 通过 $n$ -边（超边）表示，这些边充当过滤器，如果满足特定的否定条件，则阻止事实的推导。
- 时间： 节点与特定的时间点相关联，边强制执行与规则一致的时间偏移。
增量分层： 为了在不重新计算整个图的情况下实现增量更新，作者定义了增量分层。这允许系统针对特定时间点 $t$ 按分层处理规则，确保时间 $t$ 的事实仅利用时间 $t$ 或更早的事实进行推导，而绝不利用未来事实。
一致性与 $k$ -兼容性： 作者引入了节点构建的“一致性”标准。与标准 $k$ -兼容性（要求至少一个输入节点来自当前迭代 $k-1$ ）不同，一致性允许节点在任何先前的迭代中构建，只要其时间标签符合规则的要求。这防止了当依赖关系跨越多个时间步时物化过程停滞。
优化： 该方法结合了标准 TG 优化（包含消除、基于 delta 的更新），并引入了一种“遗忘”机制。一旦节点和事实的时间戳超过任何规则所需的最大时间偏移，它们就会从图中移除，从而确保内存使用量有界。

主要贡献

形式化映射： 本文提供并证明了从 Plain LARS 和 ECDE 的实际片段到时序 Datalog $^{\rightarrow}_{\ominus}$ 的映射的正确性。这确立了时序 Datalog $^{\rightarrow}_{\ominus}$ 作为嵌入和比较这些语言的自然形式化方法。
流触发图（STGs）： 一种专为时序 Datalog $^{\rightarrow}_{\ominus}$ 设计的新型推理算法和计算模型。STGs 支持分层否定，并通过增量分层和一致性检查处理时间变量的无限性质。
统一 CER 机制： 通过将 ESL 统一在单一形式化方法和推理引擎下，这项工作促进了对不同事件规范语言的形式化分析和比较，从而摆脱了临时的、孤立的解决方案。

结果与正确性

本文提供了理论证明，而非实证实验结果。

翻译的正确性： 定理 1 和定理 2 证明了从 Plain LARS 和 ECDE 到时序 Datalog $^{\rightarrow}_{\ominus}$ 的翻译保留了原始程序的完美模型语义。
STGmat 的正确性： 定理 3 证明了算法 4（STGmat）正确构建了流触发图，该图产生的事实与程序在流上的标准模型论评估结果相同。
终止性与效率： 增量分层和“遗忘”机制（命题 1）的使用确保了物化过程不会陷入无限推导，并且通过丢弃不再影响未来推导的事实来管理内存使用。

意义与主张

作者声称，这项工作通过提供一种统一的复合事件识别机制，解决了 CER 领域的碎片化问题。

泛化能力： 该方法旨在泛化到广泛的实用事件规范语言，这些语言共享分层否定和无未来依赖的特性，这是流推理中的常见要求。
效率： 通过将最先进的 Datalog 物化技术（触发图）扩展以处理带有否定的时序流，所提出的 STGs 提供了一条实现高效、低延迟推理的途径，而无需针对每种特定语言进行临时的优化。
基础巩固： 这项工作有助于巩固 CER 的理论基础，允许在表达能力与推理可处理性之间进行原则性的权衡研究。

本文最后指出，虽然假设输入流是有序的，但处理乱序流和概率扩展留待未来工作。这些贡献被视为通过统一和高效物化推动复合事件识别技术现状向前发展的一个步骤。