0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is there some optimized approximate solution to it? $\endgroup$ – ayush nigam Oct 4 '16 at 7:11
  • $\begingroup$ Well... yes, but it depends how good the solution has to be, and whether or not you ever have to deal with a difficult case. There is a lot of literature on approximation algorithms (e.g. greedy algorithms) for set cover and graph cover. That's where I'd start looking for ideas. $\endgroup$ – Pseudonym Oct 4 '16 at 7:43
  • $\begingroup$ Can you please suggest me how to convert the given problem to a set cover problem? $\endgroup$ – ayush nigam Oct 4 '16 at 8:38
  • 1
    $\begingroup$ No, I'd just mine that research for ideas. If you want to try representing your problem so you can throw an out-of-the-box solver at it, try expressing it as an integer linear program. And for hints on that, try looking up how to represent a graph cover or set cover problem as an ILP. That shouldn't be too hard to find. $\endgroup$ – Pseudonym Oct 4 '16 at 10:15
  • $\begingroup$ I agree it is a form of set cover.Not exactly set cover as joining key also comes into picture here. $\endgroup$ – ayush nigam Oct 4 '16 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.