New England Database Society Friday, February 21, 2003 sponsored by Sun Microsystems
NEDS

Exploiting Punctuation Semantics in Continuous Data Streams

David Maier
OGI School of Science & Engineering 
Oregon Health & Science University

Friday, February 21, 2003, 4:00 PM
Volen 101, Brandeis University

(preceded by a wine and cheese reception at 3:00 pm)

Abstract:

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.

Speaker Bio:

Dr. David Maier is a professor of Computer Science and Engineering. He is the author of books on relational databases, logic programming and object-oriented databases, as well as papers in database theory, object-oriented technology and scientific databases. He received the Presidential Young Investigator Award from the National Science Foundation in 1984 and was awarded the 1997 SIGMOD Innovations Award for his contributions in objects and databases. He is also an ACM Fellow. His holds a B.A. in Mathematic and Computer Science from the University of Oregon (Honors College, 1974) and a Ph.D. in Electrical Engineering and Computer Science by Princeton University (1978).

Maintained by Dina Goldin dqg AT cse.uconn.edu
Last updated on 02/10/03