# Why checking if tuple belongs to join of two tables is NP-complete?

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?

• 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. – gnasher729 Sep 22 '18 at 15:55
• Perhaps the claim was about the join of an arbitrary number of tables? – Yuval Filmus Sep 22 '18 at 16:07
• 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. – Developer Sep 22 '18 at 19:15
• 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. – Renzo Sep 22 '18 at 20:38
• Could you explain it me in answer with more details? – Developer Sep 22 '18 at 20:39

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