I have read that checking if tuple belongs to join of two tables is NP-complete.
I had computional-complexity activities during my studies, I remember basics, however I have forgotten details. Nevertheless I don't understand why it is NP-complete, it seems to me that I can solve it in polynomial time.

Let's consider specific example:
We have two tables, $T_1$ and $T_2$, where $|T_1|=m$ and $|T_2|=n$.
Now, let $t$ will be a tuple $t=(a,b,c)$. Then I can easily give polynomial algorithm for checking if join of $T_1$ and $T_2$ containg tuple $t$.

Is is sufficient to get $T_1\times T_2$ and in linear time check if this tuple is contained in result. Please note that size of $|T_1\times T_2|=n\times m$ is polynomial.

Where am I wrong?

  • 4
    $\begingroup$ I'd recommend posting a link to the actual claim. The obvious possibilities: The claim is wrong, or the actual claim is something much different from what you understood. $\endgroup$ – gnasher729 Sep 22 '18 at 15:55
  • 2
    $\begingroup$ Perhaps the claim was about the join of an arbitrary number of tables? $\endgroup$ – Yuval Filmus Sep 22 '18 at 16:07
  • $\begingroup$ for instance, given a join query $Q$ and a relational database $D$, checking if $Q(D)$ returns a tuple is NP-complete as well. However, my question is update even in case of arbitrary number of joins. $\endgroup$ – Developer Sep 22 '18 at 19:15
  • $\begingroup$ According to the formulation of the claim, it seems to me that the NP-completness is about the fact that the join contains at least a tuple, not about checking if a particular tuple is contained in the join. $\endgroup$ – Renzo Sep 22 '18 at 20:38
  • $\begingroup$ Could you explain it me in answer with more details? $\endgroup$ – Developer Sep 22 '18 at 20:39

If the claim is:

for instance, given a join query $Q$ and a relational database $D$, checking if $Q(D)$ returns a tuple is NP-complete as well

the NP-completness is about the decision if that join operation returns an empty set or not (for instance because the join condition is not satisfied by any pair of tuples).

So, if this hypothesis is true, the claim is not, as you are asserting, about the fact that a certain tuple belongs to the result or not (for instance this could be checked by verifying that the tuple satisfies the join condition).


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.