On the complexity of generating optimal plans with cross products (extended abstract)
Wolfgang Scheufele, Guido Moerkotte · 1997
In modern advanced database systems the optimizer is often faced with the problem of finding optimal evaluation strategies for queries involving alarge number of joins.Examples are queries generated by deductive database systems and path expressions in object-oriented database systems.The best plan can be found in the very large search space of bushy trees where plans are allowed to contain cross products.A general question arises: For which (sub-) problems can we expect to find polynomial algorithms generating the best plan?We attack this question from both ends of the spectrum.First, we show that we cannot expect to find any polynomial algorithm for any subproblem as long as optimal bushy trees are to be generated.More specifically, we show that the problem is NP-hard independent of the query graph.Second, for the restricted cIass of chain queries, we present two efficient algorithms for the problem of generating left-deep trees possibly containing cross products.