Constructing Optimal Bushy Processing Trees for Join Queries is NP-hard
Guido Moerkotte, Wolfgang Scheufele · MADOC (University of Mannheim) · 1996
We show that constructing optimal bushy processing trees for join queriesis NP-hard. More specifically, we show that even the construction of optimal bushy trees for computing the cross product for a set of relations is NP-hard.