The weight is an expression containing optimization required parameters, such as relation size, tuple size, join selectivity factors. All possible execution plans are representable in this graph and each spanning tree of the graph becomes an execution plan. It is a general model which can be used in the optimizer of a DBMS for interal query representation. On the basis of this model, we devise an algorithm that finds a near optimal execution plan using only polynomial time. The algorithm is compared with a few other popular optimization methods.
Experiments show that the proposed algorithm is superior to the others under most circumstances.
Large join query, graph theory, join cost, query tree, query optimization. IEEE Transactions on Knowledge and Data Engineering , Vol. Inc. All rights reserved.