Welcome to D
SIGMOD 2004
PODS 2004
SIGMOD RECOR
CIKM 2004
DASFAA 2004
DBPL 2003
DE-BULLETIN
DEBS 2004
DMKD 2004
DMSN 2004
DOLAP 2004
DPDJ 2004
EDBT 2004
ER 2003
GIS 2004
HDP 2004
HYPERTEXT 20
ICDE 2004
ICDT 2003
JCDL 2004
MDM
MIR 2004
MIS 2004
MMDB 2004
MOBIDE 2003
RIDE 2004
SBBD 2003
SIGIR FORUM
SIGIR 2004
SIGKDD EXPLO
SIGKDD 2004
SSDBM 2004
SSTD 2003
TIME 2004
TODS 2004
VLDB 2004
<<< = VLDB'04 Pape>>>
VLDB Journal
WEBDB 2004
WIDM 2004
XIME-P 2004
Footer

Query Languages and Data Models for Database Sequences and Data Streams


Yan-Nei Law, Haixun Wang, and Carlo Zaniolo

  View Paper (PDF)  

Return to RESEARCH SESSION 12:STREAM DATA MANAGEMENT SYSTEMS


Abstract

We study the fundamental limitations of relational algebra (RA)and SQL in supporting sequence and stream queries, and present effective query language and data model enrichments to deal with them. We begin by observing the well-known limitations of SQL in application domains which are important for data streams, such as sequence queries and data mining. Then we present a formal proof that, for continuous queries on data streams, SQL suffers from additional expressive power problems. We begin by focusing on the notion of non blocking (NB) queries that are the only continuous queries that can be supported on data streams. We characterize the notion of non blocking queries by showing that they are equivalent to monotonic queries. Therefore the notion of NB-completeness for RA can be formalized as its ability to express all monotonic queries expressible in RA using only the monotonic operators of RA. We show that RA is not NB-complete, and SQL is not more powerful than RA for monotonic queries. To solve these problems, we propose extensions that allow SQL to support all the monotonic queries expressible by a Turing machine using only monotonic operators. We show that these extensions are(i) user-defined aggregates (UDAs) natively coded in SQL (rather than in an external language), and (ii) a generalization of the union operator to support the merging of multiple streams according to their timestamps. These query language extensions require matching extensions to basic relational data model to support sequences explicitly ordered by timestamps. Along with the formulation of very powerful queries, the proposed extensions entail more efficient expressions for many simple queries. In particular, we show that non blocking queries are simple to characterize according to their syntactic structure.


©2005 Association for Computing Machinery