Topics in Database Systems

CS 848, Waterloo, Winter '06

  Instructor:   David Toman (david@uwaterloo.ca)
  Org. Meeting: DC 3313, January 6, 2006, 11am 
  Lectures:     Tuesday 4:30-7 pm DC3313
  Office:       DC 3344, x4777
  Class Info:   http://db.uwaterloo.ca/~david/cs848/

Summary:

The class will focus on various issues connected with processing of inherently ordered data, in particular on streaming data. Of particular interest will be extensions/improvements to existing designs of streaming query languages and to efficiency of streaming queries.

Week 1: Orientation meeting (01/06 @ 11a.m. DC3313)

Week 2: Introduction to Data Streams and their Relation to Temporal Databases

Topics: Introduction to the streaming model and CQL and comparison to work on temporal databases. Salient issues: are streams finite or infinite (and what are the implications?) and how do we implement streaming languages (a.k.a. how will algebras for streams look like?)

Week 3: Construction of Exact Synopses for Streaming Query Languages

Topics: Introduction to synopsis construction (why and what do we want to achieve), comparison with work on data expiration (slides). Quick review of materialized view maintenance.

Week 4: Construction of Approximate Synopses

Topics: Introduction to approximate synopsis construction (why and what do we want), when is sub-linear space for synopses feasible? Based on a survey by Muthukrishnan.

Week 5: Streams and Constraints

Topics: Constraints on data streams (why do we want it?). Windowing in Queries, Punctuated data streams, and Temporal constraints.

Week 6: Topic Presentations, Project Topics

Weeks 7-11:

Feb 14: Jiang Wu: The STREAM System, Kevin Chen: The AURORA System

Feb 21: Evan Chen: Execution of Streaming Operators, Helen Li: The TELEGRAPH System

Feb 28: Jie Zhang: Description Logics and Time (slides), Yunqi Zhang: Streaming XML

Mar 7: Yang Sun: Sensor Networks, Feng Xue: Similarity in Streaming Data

Week 11-12: Project Presentations/Demos