Characterizing Memory Requirements for Queries over Continuous Data Streams

Abstract

We consider conjunctive queries with arithmetic comparisons and optional aggregation over multiple continuous data streams. We specify an algorithm for determining whether or not any given query can be evaluated using a bounded amount of memory for all possible instances of the data streams. When a query can be evaluated using bounded memory, we produce an execution strategy based on constant-sized synopses of the data streams. When it cannot, we produce a data stream scenario in which evaluating the query requires memory linear in the size of the streams.