  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.
