Joining tables with minimum number of joins
I believe that your problem is NP-complete.

Showing that it's in NP is easy. To show that it's NP-hard, take any instance of the set cover problem. Add a new unique element to the universe, and add it to each set. Interpreting each set as a table, a solution to the minimum join problem is a solution to the original set cover problem.