Window specification over data streams

Abstract. Several query languages have been proposed for managing data streams in modern monitoring applications. Continuous queries ex-pressed in these languages usually employ windowing constructs in order to extract finite portions of the potentially unbounded stream. Explicitly or not, window specifications rely on ordering. Usually, timestamps are attached to all tuples flowing into the system as a means to provide or-dered access to data items. Several window types have been implemented in stream prototype systems, but a precise definition of their semantics is still lacking. In this paper, we describe a formal framework for express-ing windows in continuous queries over data streams. After classifying windows according to their basic characteristics, we give algebraic ex-pressions for the most significant window types commonly appearing in applications. As an essential step towards a stream algebra, we then pro-pose formal definitions for the windowed analogs of typical relational operators, such as join, union or aggregation, and we identify several properties useful to query optimization.