Oliver Kennedy's talk on DB Seminar

Title: Database Toasting Made Easy

Abstract
Many modern applications (like algorithmic trading for example) require the ability to rapidly react to complex conditions that arise over rapidly changing state.  An ideal framework for such applications would allow users to specify these conditions in a simple, declarative form.  Unfortunately, existing declarative monitoring systems have strict limitations on the expressiveness with which the conditions may be specified, typically by requiring the use of windows with joins.

In this talk, I present DBToaster, a compiler that produces efficient monitoring code out of conditions specified declaratively as SQL queries.  DBToaster is built around a novel dynamic-programming approach to query processing that aggressively identifies and exploits incrementality in monitoring the conditions with respect to individual state changes.  State is represented in terms of relations, and conditions are specified in terms of queries over these relations.  DBToaster produces code that materializes and incrementally maintains these condition queries.  Like traditional incremental view maintenance systems, updates to relations appearing in the condition query trigger a view maintenance, or delta query: A simpler query that computes how the condition query result changes after the update.  Unfortunately these queries are often dependent on the entire state of the system, and not just the tuple being updated.

Unlike traditional incremental view maintenance systems, DBToaster materializes and incrementally maintains delta queries as well.  These materialized delta queries are maintained using a series of delta-of-delta queries, which are also materialized.  This continues until after several levels the delta query is a constant, dependent only on the tuple being inserted and not any existing state.  The result is a hierarchy of incrementally maintained views, each substantially reducing the cost of maintaining its parent. 

Bio
Oliver Kennedy is a postdoctoral associate at EPFL Switzerland, working with Christoph Koch working on stream processing and distributed and in-memory databases. Oliver recently graduated from Cornell University, where he studied databases: distributed, probabilistic, toasted, and otherwise.  In addition to DBToaster, Oliver's projects include a distributed data and event processing system called Cumulus, and two probabilistic database systems: PIP and Jigsaw respectively.