Multi-Join Query Algorithm Research Over Data Streams

Since data stream is continuous, real time and infinite, traditional database management technology is no longer suitable for its management, continuous query over data streams has been a new research field of database theory. The join query attracts more attention because of its universality in application and complexity, but most of the research results aim at binary join query. As an important aspect of the join query, there is little research paid upon multi-join query over data streams.Firstly, in this dissertation we analyse the sliding window binary join query over data streams, including the execution process and the join cost model, and compare the two motheds of multi-join query over data streams: Mjoin operator and join tree.Secondly, based on the join cost model of sliding window binary join query, the cost model of join process in Mjoin operator is presented, and then we propose two algorithms to find out the optimal probe sequence: DSTQPS-OPT for tree query and DSGQPS-OPT for general query.Then, we analyse the intermediate state of query plan based on linear join tree, and propose an algorithm named DSLJT-MinIS which aims at generating a query plan based on linear join tree with minimal intermediate state.Finally, through the experiments, we prove the validity of cost model of join process in Mjoin operator and the validity of the DSTQPS-OPT algorithm.