Department of Computer Science and Engineering
Oregon Graduate Institute
4pm Tuesday 2nd July 2002
Room 2511, JCMB, King's Buildings
As most current query processing architectures are already pipelined, it seems logical to apply them to data streams. However, two classes of query operators are impractical for long or infinite streams. Unbounded stateful operators maintain state with no upper bound in its size, and so run out of memory. Blocking operators read an entire input before emitting a single output tuple, and so might never produce a result. We believe that a priori knowledge of a data stream can permit the use of such operators in some cases. We discuss a kind of stream semantics called punctuated streams. Punctuations in a stream mark the end of substreams, allowing us to view an infinite stream as a mixture of finite streams. We introduce three kind of rules to specify the proper behavior of operators in the presence of punctuation. Pass rules define when an operator can pass results on. Keep rules define what must be kept in state to continue successful operation. Propagation rules define when an operator can pass punctuation on. We report on our initial implementation, and show a strategy for proving implementations of these rules are faithful to their table counterparts.