Research On Dynamic Programming Based Join Tree Generation Algorithms

Join-tree generation algorithm is mainly used by the query optimizer of a database.Finding the optimal join-tree plays an important role for the efficiency of database management system.By transforming unordered query graph to different join-trees,the algorithm generate the optimal join-tree according to the cost estimation method.The literature shows analytically and experimentally about two dynamic programming based join-tree generation algorithms,DPsize and DPsub.By analyzing the structure and performance of the two algorithms,we design and implement a new dynamic programming based join-tree generation algorithm,DPccp.Algorithm DPsize generates join-trees by increasing the size of the relations in a bottom-up fashion.Algorithm DPsub represents different relations as a binary number,and generates join-tree by increasing the binary number.By implementing and analyzing the two algorithm we found that none of them shows high efficiency to all kinds of query graph,which motivates us to derive an new algorithm DPccp.This new algorithm generate the optimal join-tree more efficiently by enumerating all connected subgraphs of the query graph.The evaluation shows that DPccp is more superior by adopting to different kinds of query graph.