JCSE, vol. 3, no. 1, pp.27-58, 2009

DOI:

Transformation of Continuous Aggregation Join Queries over Data Streams

Tri Minh Tran, Byung Suk Lee
Department of Computer Science, University of Vermont, USA

Abstract: Aggregation join queries are an important class of queries over data streams. These queriesinvolve both join and aggregation operations, with window-based joins followed by anaggregation on the join output. All existing research address join query optimization andaggregation query optimization as separate problems. We observe that, by putting them withinthe same scope of query optimization, more efficient query execution plans are possible throughmore versatile query transformations. The enabling idea is to perform aggregation before joinso that the join execution time may be reduced. There has been some research done on suchquery transformations in relational databases, but none has been done in data streams. Doingit in data streams brings new challenges due to the incremental and continuous arrival oftuples. These challenges are addressed in this paper. Specifically, we first present a queryprocessing model geared to facilitate query transformations and propose a query transformationrule specialized to work with streams. The rule is simple and yet covers all possible cases oftransformation. Then we present a generic query processing algorithm that works with allalternative query execution plans possible with the transformation, and develop the costformulas of the query execution plans. Based on the processing algorithm, we validate the ruletheoretically by proving the equivalence of query execution plans. Finally, through extensiveexperiments, we validate the cost formulas and study the performances of alternative queryexecution plans.

Keyword: No keyword

Full Paper:   236 Downloads, 4191 View