Reasoning over Streaming Data in Metric Temporal Datalog

Przemyslaw Andrzej Walega, Mark Kaminski, Bernardo Cuenca Grau

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.

Interval-based reasoning and propagation in the forward-propagating fragment.

Two distinct algorithms are proposed:

  1. 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.
  2. 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 'sufficiently often' operator (#) enables the storage of extended facts over intervals, optimizing memory usage.

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

Abstract

We study stream reasoning in datalogMTL—an extension of Datalog with metric temporal operators. We propose a sound and complete stream reasoning algorithm that is applicable to a fragment datalogMTLFP of datalogMTL, in which propagation of derived information towards past time points is precluded. Memory consumption in our algorithm depends both on the properties of the rule set and the input data stream; in particular, it depends on the distances between timestamps occurring in data. This is undesirable since these distances can be very small, in which case the algorithm may require large amounts of memory. To address this issue, we propose a second algorithm, where the size of the required memory becomes independent on the timestamps in the data at the expense of disallowing punctual intervals in the rule set. Finally, we provide tight bounds to the data complexity of standard query answering in datalogMTLFP without punctual intervals in rules, which yield a new PSPACE lower bound to the data complexity of the full datalogMTL.
BibTeX
@inproceedings{walega2019reasoning,
  author = {Przemyslaw Andrzej Walega and Mark Kaminski and Bernardo Cuenca Grau},
  title = {{Reasoning over Streaming Data in Metric Temporal Datalog}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33013092},
}

Loading related content...

Figure