loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
26th IEEE International Conference on Distributed Computing Systems Workshops (ICDCSW'06)
Finding Optimal Join Tree forMulti-Join Stream Queries in a Production System
Lisboa, Portugal
July 04-July 07
ISBN: 0-7695-2541-5
Joseph S. Gomes, George Washington University
Heyong-Ah Choi, George Washington University
Data Stream Management Systems (DSMS) handle a particular type of database applications that involve multiple continuous data streams with inputs arriving at highly variable and unpredictable rates. Since data rate fluctuates over time in this type of applications the appropriate join tree is crucial for maintaining high system throughput. We consider the problem of finding optimal join tree for performing count based sliding window multi-joins over continuous streams. We use a unit-time based cost model to evaluate the expected performance for a given join tree. We materialize all intermediate results assuming there is enough main memory to store all partial results and window buffers. We give a polynomial time algorithm that finds the optimal join tree under our cost model for a given noncommuting (single permutation) order of streams. This algorithm can be used in conjunction with any linear order producing heuristic to give the optimal tree for that order. Our algorithm is implemented in the Jess rule engine and an extensive experimental evaluation is provided.
Citation:
Joseph S. Gomes, Heyong-Ah Choi, "Finding Optimal Join Tree forMulti-Join Stream Queries in a Production System," icdcsw, pp.27, 26th IEEE International Conference on Distributed Computing Systems Workshops (ICDCSW'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.