A Formal Approach to Data Stream Processing

Cornell University, Ithaca NY

Investigators

Abstract

IIS-0621438 Johannes E Gehrke <johannes@cs.cornell.edu> Cornell University Developing Formal Semantics for Data Streams In many applications, for example stock monitoring to large-scale system monitoring, data is not static but arrives in high-speed data streams. Unlike in traditional Database Management Systems, research in data streams has been driven by the development of many application-specific systems and languages. The result has been a plethora of stream query languages, with no unified formal framework for optimization or general study. This project is developing a formal semantics to unify data stream query languages, like what already exists for traditional relational databases. This project is (1) developing a formal data stream language powerful enough to encompass all of the existing data stream query languages, (2) using this framework to identify the expressive power of these existing languages, and (3) developing a language hierarchy within this framework that identifies the trade-off between expressiveness and performance. The proposed educational program will train a graduate student for research in the theory of data streams. Success in this project will bring tremendous benefits to data stream processing, as it will provide a uniform framework for studying optimization of data stream queries. It will also connect the area of mathematical logic with data stream systems, a connection that has already been shown to be beneficial for traditional database systems. Our results will be disseminated via the following website: http://www.cs.cornell.edu/database/cayuga/expressiveness/.