# The Window Validity Problem in Rule-Based Stream Reasoning

arXiv: https://arxiv.org/abs/1808.02291 · HTML: https://mlsanity.com/paper/1808.02291/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Aug 2018.

## Built on by (most cited first, 2 of 2)

- [Chasing Streams with Existential Rules](https://mlsanity.com/paper/2205.02220/) (2022)
- [Efficient Temporal Datalog Materialisation for Composite Event Recognition](https://mlsanity.com/paper/2605.02488/) (2026)

## Abstract (arXiv)

Rule-based temporal query languages provide the expressive power and flexibility required to capture in a natural way complex analysis tasks over streaming data. Stream processing applications, however, typically require near real-time response using limited resources. In particular, it becomes essential that the underpinning query language has favourable computational properties and that stream processing algorithms are able to keep only a small number of previously received facts in memory at any point in time without sacrificing correctness. In this paper, we propose a recursive fragment of temporal Datalog with tractable data complexity and study the properties of a generic stream reasoning algorithm for this fragment. We focus on the window validity problem as a way to minimise the number of time points for which the stream reasoning algorithm needs to keep data in memory at any point in time.