Paper Info
Title
On the Complexity of Generating Optimal Left-Deep Processing Trees with Cross Products
Abstract
Producing optimal left-deep trees is known to be NP-complete for general join graphs and a quite complex cost function counting disk accesses for a special block-wise nested-loop join [2]. Independent of any cost function is the dynamic programming approach to join ordering. The number of alternatives this approach generates is known as well [5]. Further, it is known that for some cost functions - those fulfilling the ASI property [4] - the problem can be solved in polynomial time for acyclic query graph, i.e., tree queries [2, 3].Unfortunately, some cost functions like sort merge could not be treated so far. We do so by a slight detour showing that this cost function (and others too) are optimized if and only if the sum of the intermediate result sizes is minimized. This validates the database folklore that minimizing intermediate result sizes is a good heuristic. Then we show that summarizing the intermediate result sizes has the ASI property. It further motivates us to restrict the subsequent investigations to this cost function called C-out for which we show that the problem remains NP-complete in the general case.Then, we concentrate on the main topic of the paper: the complexity of producing left-deep processing trees possibly containing cross products. Considering cross products is known to possibly result in cheaper plans [5]. More specifically, we show that the problem (LD-X-Star) of generating optimal left-deep processing trees possibly containing cross products is NP-complete for star queries. Further, we give an algorithm for treating star queries which is more efficient than dynamic programming. The NP-completeness of LD-X-Star immediately implies the NP-completeness for the more general tree queries.
Year
Venue
Keywords
1995
ICDT
cross products,generating optimal left-deep processing,polynomial time,nested loops,cost function
Field
DocType
Volume
Dynamic programming,Discrete mathematics,Graph,Cross product,Computer science,Theoretical computer science,Time complexity
Conference
893
ISSN
ISBN
Citations 
0302-9743
3-540-58907-4
24
PageRank 
References 
Authors
4.56
8
2
Name
Order
Citations
PageRank
Sophie Cluet11602636.58
Guido Moerkotte22136649.11