🤖 AI

Efficient Temporal Datalog Materialisation for Composite Event Recognition

This paper addresses the challenge of comparing disparate event specification languages by mapping them to a unified Temporal Datalog framework and introducing Streaming Trigger Graphs to enable efficient, generalizable composite event recognition over high-velocity data streams.

Original authors: Periklis Mantenoglou

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Periklis Mantenoglou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the conductor of a massive, high-speed orchestra where every musician is playing a different instrument, and the music is changing every single second. Your job is to spot specific, complex patterns in the music—like "a violin playing a high note while a drum beats a slow rhythm three times in a row"—and immediately raise a red flag if that pattern happens.

This is the challenge of Composite Event Recognition (CER). In the real world, this isn't just about music; it's about spotting safety threats in a smart city, detecting fraud in a bank, or monitoring a fleet of delivery trucks. The problem is that different teams use different "sheet music" (languages) to describe these patterns, and their "conductors" (reasoners) can't talk to each other.

Here is how this paper solves that problem, using simple analogies:

1. The Problem: Too Many Dialects

Imagine a group of detectives trying to solve a crime. One detective speaks "Event Calculus," another speaks "LARS," and a third speaks "Temporal Datalog." They all describe the same crime scene, but they use different words and sentence structures.

The Issue: If Detective A finds a clue, Detective B might not understand it. They can't compare their notes easily, and they can't use the best detective for the specific job because the languages don't match.
The Paper's Goal: Create a "Universal Translator" that converts the specific dialects of Event Calculus and LARS into a single, common language called Temporal Datalog→⊖.

2. The Universal Translator: Temporal Datalog→⊖

The authors created a special version of a logic language (a set of rules for computers) that acts as this common ground.

No Time Travel: This language has a strict rule: you can only look at the past or the present. You cannot look into the future. This is like saying, "I can only make decisions based on what has already happened or is happening right now." This prevents the system from getting confused or stuck waiting for data that hasn't arrived yet.
Stratified Negation: This is a fancy way of saying the rules are organized in layers to avoid contradictions. Imagine a building with floors. You can only look down from a higher floor to check what's on a lower floor, never the other way around. This keeps the logic clean and prevents the system from getting into a loop of "Is it true? No, is it true? No..."

3. The Engine: Streaming Trigger Graphs (STGs)

Once the rules are translated into this common language, the computer needs a way to process them instantly as data flows in. The authors invented a new engine called Streaming Trigger Graphs (STGs).

Think of an STG as a smart assembly line in a factory:

The Factory Floor: The "stream" of data (events) flows down a conveyor belt.
The Workers (Nodes): Each worker on the line checks for a specific condition.
The "Forget" Button: In a normal factory, you might keep every single part you ever made. But in this high-speed factory, if a part is too old to be useful for the current product, the worker immediately throws it away. The paper calls this "Forgetting." It saves massive amounts of memory by only keeping the facts that are still relevant to the current moment.
The Safety Net (Negation): Sometimes a worker needs to know, "Did a specific event not happen?" The STG has a special mechanism (like a security guard with a "Do Not Enter" list) that instantly blocks a product from moving forward if a forbidden event occurred.

4. How It Works in Practice

The paper shows how to take complex rules from the two main "dialects" (Event Calculus and LARS) and translate them into this common language.

Example: If a rule says, "If a device was repaired in the last 2 hours, mark it as 'Verified'," the translator converts this into a simple rule that checks the current time minus 2 hours.
The Result: The STG engine then runs these translated rules. As new data arrives (e.g., a repair happens), the engine instantly updates its knowledge, checks the rules, and outputs the result (e.g., "Device is Verified") without ever slowing down or getting stuck.

5. Why This Matters

The paper claims that by doing this translation and using this new engine:

Uniformity: You can now compare different event languages fairly because they are all running on the same engine.
Efficiency: The "Forgetting" mechanism and the smart organization of the graph mean the system can handle huge amounts of data very quickly without running out of memory.
Correctness: The authors mathematically proved that this translation doesn't change the meaning of the rules. If the original rule said "X is true," the translated version will also say "X is true."

Summary

In short, the authors built a universal translator for event-detection languages and a super-efficient, memory-saving assembly line (Streaming Trigger Graphs) to process them. This allows computers to spot complex, time-sensitive patterns in high-speed data streams reliably, without getting confused by different languages or running out of space.

Technical Summary: Efficient Temporal Datalog Materialisation for Composite Event Recognition

Problem Statement

Composite Event Recognition (CER) frameworks are essential for detecting critical situations (e.g., safety threats) over high-velocity streams of symbolic events. These frameworks typically consist of an Event Specification Language (ESL) to define patterns and a stream reasoner to evaluate them. However, existing ESLs are often studied in isolation, complicating comparisons regarding expressivity and obscuring the scope of their associated reasoners. Furthermore, patterns expressed in one ESL frequently cannot be faithfully or optimally translated into another, preventing the use of the most suitable reasoner for a specific problem. There is a lack of a unifying formalism that can embed prominent ESLs while supporting efficient, low-latency reasoning over unbounded streams.

Methodology

The authors propose a unified approach centered on Temporal Datalog $^{\rightarrow}_{\ominus}$ , a variant of Temporal Datalog featuring stratified negation and no future dependencies (forward-propagating). The methodology involves two primary components:

1. Embedding ESLs into Temporal Datalog $^{\rightarrow}_{\ominus}$

The paper presents mappings from two prominent logic-based ESLs into Temporal Datalog $^{\rightarrow}_{\ominus}$ , proving that these translations are equivalence-preserving with respect to query answering:

Plain LARS: A fragment of the LARS language (based on Answer Set Programming with window operators). The translation (Algorithm 2) handles temporal modalities ( $\diamond$ , $\square$ ) and window operators ( $\boxplus$ ) by introducing auxiliary predicates and grounding time variables. It ensures the resulting program is forward-propagating and temporally stratified.
Event Calculus with Delayed Effects (ECDE): A variant of the Event Calculus used in large-scale CER. The translation (Algorithm 3) eliminates functors (event/fluent types) by introducing specific predicates for each type and value. It encodes the law of inertia, delayed effects, and static fluent definitions into forward-propagating rules, ensuring temporal stratification.

2. Streaming Trigger Graphs (STGs)

To support efficient materialisation of Temporal Datalog $^{\rightarrow}_{\ominus}$ , the authors propose Streaming Trigger Graphs (STGs), an extension of Trigger Graphs (TGs). Standard TGs are insufficient because they do not natively support negation or the infinite grounding of time variables required for streaming.

Streaming Execution Graphs (SEGs): STGs are built upon SEGs, which extend Execution Graphs to include:
- Negation: Represented via $n$ -edges (hyperedges) that act as filters, preventing the derivation of facts if specific negative conditions are met.
- Time: Nodes are associated with specific time-points, and edges enforce temporal offsets consistent with the rules.
Incremental Stratification: To enable incremental updates without recomputing the entire graph, the authors define an incremental stratification. This allows the system to process rules in strata for a specific time-point $t$ , ensuring that facts for time $t$ are derived using facts from $t$ or earlier, but never the future.
Consistency vs. $k$ -compatibility: The authors introduce a "consistency" criterion for node construction. Unlike standard $k$ -compatibility (which requires at least one input node to be from the current iteration $k-1$ ), consistency allows nodes to be constructed if they were built in any prior iteration, provided their time labels match the rule's requirements. This prevents the materialisation process from stalling when dependencies span multiple time steps.
Optimisations: The approach incorporates standard TG optimisations (subsumption removal, delta-based updates) and introduces a "forgetting" mechanism. Nodes and facts are removed from the graph once their time-stamps exceed the maximum temporal offset required by any rule, ensuring bounded memory usage.

Key Contributions

Formal Mappings: The paper provides and proves the correctness of mappings from practical fragments of Plain LARS and ECDE to Temporal Datalog $^{\rightarrow}_{\ominus}$ . This establishes Temporal Datalog $^{\rightarrow}_{\ominus}$ as a natural formalism for embedding and comparing these languages.
Streaming Trigger Graphs (STGs): A novel reasoning algorithm and computational model specifically designed for Temporal Datalog $^{\rightarrow}_{\ominus}$ . STGs support stratified negation and handle the infinite nature of time variables through incremental stratification and consistency checks.
Uniform CER Mechanism: By unifying ESLs under a single formalism and reasoning engine, the work facilitates formal analysis and comparison of different event specification languages, moving away from ad-hoc, isolated solutions.

Results and Correctness

The paper provides theoretical proofs rather than empirical experimental results.

Correctness of Translation: Theorem 1 and Theorem 2 prove that the translations from Plain LARS and ECDE to Temporal Datalog $^{\rightarrow}_{\ominus}$ preserve the perfect model semantics of the original programs.
Correctness of STGmat: Theorem 3 proves that Algorithm 4 (STGmat) correctly constructs a Streaming Trigger Graph that yields the same facts as the standard model-theoretic evaluation of the program over a stream.
Termination and Efficiency: The use of incremental stratification and the "forgetting" mechanism (Proposition 1) ensures that the materialisation process does not get trapped in infinite derivations and that memory usage is managed by discarding facts that can no longer influence future derivations.

Significance and Claims

The authors claim that this work addresses the fragmentation in the CER field by providing a uniform composite event recognition mechanism.

Generalisation: The approach is designed to generalise across a wide range of practical event specification languages that share the properties of stratified negation and no future dependencies, which are common requirements in stream reasoning.
Efficiency: By extending state-of-the-art Datalog materialisation techniques (Trigger Graphs) to handle temporal streams with negation, the proposed STGs offer a path to efficient, low-latency reasoning without the need for ad-hoc optimisations for each specific language.
Foundational Consolidation: The work helps consolidate the theoretical foundations of CER, allowing for principled trade-off studies between expressivity and reasoning tractability.

The paper concludes by noting that while it assumes ordered input streams, handling out-of-order streams and probabilistic extensions are left for future work. The contributions are framed as a step toward advancing the state of the art in composite event recognition through unification and efficient materialisation.