Joining tables with minimum number of joins

Question

I am working on a generalized problem where I am given only schema definition of multiple tables that i have.

Now i have to retrieve certain columns by joining multiple tables such that number of joins are minimized.(i will consider where condition in sql clause later)

Example: Suppose i have 3 tables and here is the list of columns that they have.

Table 1:(1,2,3,4,5), Table 2:(5,6,7), Table 3:(5,6,7,8)

Now suppose I have a query in which i want all the columns 1,2,3,4,5,6,7,8.

Now i can join either table 1,table 2 and table 3 OR table 1 and table 3.I would get the required information in both the cases but joining table 1 and table 3 would require only 1 join rather than 2 join in other case.

What i was trying was a greedy algorithm in which first i would consider table that has maximum number of required columns then eliminate the common columns between the query and table(from both query and table) and then consider updated required columns and update tables and so on.But i guess it would be slow.

So is there a generalized algorithm or if anyone can give me any hint in this direction?

Answer 1

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.