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

Question

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?

Answer 1

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