Abstract
This paper introduces novel algorithms for reasoning over real-time data streams using $datalogMTL$, a logic that combines recursive rules with precise temporal constraints. By focusing on the "forward-propagating" fragment and identifying a sub-language that ignores instantaneous (punctual) time points, the authors provide a framework for processing complex events with memory requirements that remain stable regardless of data precision.
Introduction
In high-stakes industries such as algorithmic trading, IoT, and network security, systems must analyze massive data streams to detect complex, time-sensitive patterns. While Metric Temporal Logic (MTL) is adept at describing these patterns, it lacks the recursive capabilities needed for complex event triggering. $DatalogMTL$ was developed to bridge this gap, but its application to infinite streams is hindered by two primary issues: the "Past Problem," where backward-propagating rules prevent data from being discarded, and the "Precision Problem," where memory usage scales poorly with high-frequency data.
Methodology
The authors address these challenges by focusing on forward-propagating $datalogMTL$ ($datalogMTL^{FP}$), where rules only derive information about the present or future. This allows the system to safely discard old data using a sliding window approach.
Two distinct algorithms are proposed:
- Algorithm 1: A general stream reasoning algorithm for $datalogMTL^{FP}$ that utilizes a window for recent facts and a history to summarize older information. Its memory usage is inherently tied to the temporal granularity of the input data.
- Algorithm 2: Designed for the non-punctual fragment ($datalogMITL^{FP}$). By disallowing rules that trigger at exact, instantaneous moments, the authors introduce a new "sufficiently often" operator ($\#$). This allows the algorithm to track facts over intervals rather than specific points, decoupling memory consumption from temporal precision.
Key Insights: Decoupling from Precision
A significant breakthrough in this work is the realization that punctual intervals are the primary driver of memory instability in high-precision streams. By moving to the non-punctual fragment, the system can reason about dense time without storing every millisecond of data.
The novel $\#$ (Sufficiently Often) operator allows the window memory to store a single "extended fact" representing multiple readings across an interval, provided they occur frequently enough to satisfy the logic rules. This makes the system robust against increases in sensor sampling rates.
Key Results and Complexity
The paper provides the first tight bounds for memory consumption in recursive metric temporal logic. For the non-punctual fragment, memory usage depends only on the ruleset and the number of unique objects, not the frequency of the data.
From a complexity standpoint, the authors establish that checking facts in this framework is PSPACE-complete when timestamps are encoded in binary and P-complete when encoded in unary. They also provide a new PSPACE lower bound for the data complexity of the full $datalogMTL$ language, refining the theoretical understanding of these problems.
Conclusion and Future Work
While the forward-propagating restriction precludes certain retrospective data cleaning tasks, it makes real-time stream reasoning computationally feasible for most monitoring applications. Future research will focus on extending these algorithms to support the "Since" operator for duration-based reasoning, incorporating non-monotonic negation, and testing the framework in practical environments like autonomous vehicle coordination.
Summary updated