0
$\begingroup$

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?

$\endgroup$
6
  • 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
    Commented Sep 22, 2018 at 15:55
  • 2
    $\begingroup$ Perhaps the claim was about the join of an arbitrary number of tables? $\endgroup$ Commented Sep 22, 2018 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
    Commented Sep 22, 2018 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
    Commented Sep 22, 2018 at 20:38
  • $\begingroup$ Could you explain it me in answer with more details? $\endgroup$
    – Developer
    Commented Sep 22, 2018 at 20:39

1 Answer 1

3
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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