# Can we do joins in NC?

Suppose we want to join two relations on a predicate. Is this in NC?

I realize that a proof of it not being in NC would amount to a proof that $P\not=NC$, so I'd accept evidence of it being an open problem as an answer.

I'm interested in the general case as well as specific cases (e.g. perhaps with some specific data structure it can be parallelized).

Some specifics:

• We could consider an equijoin $A.x = B.y$. On a single processor, a hash-based algorithm runs in $O(|A|+|B|)$ and this is the best we can do since we have to read each relation
• If the predicate is a "black box" where we have to check each pair, there are $|A|\cdot|B|$ pairs, and each one could be in or not, so $2^{ab}$ possibilities. Checking each pair divides the possibilities in half, so the best we can do is $O(ab)$.

Could either of these (or some third type of join) be improved to $\log^k n$ on multiple processors?

(Reposted from here as per site policy.)

• What does "join two relations on a predicate" mean? $\:$ – user6973 Jul 6 '12 at 17:19
• @Ricky: Given a predicate (i.e. boolean-valued function) $P$ and two relations (sets) $R, S$, we wish to find $\{(r,s)|r\in R \wedge s\in S \wedge P(r,s)\}$. See wikipedia for theory and practice – Xodarap Jul 6 '12 at 18:25
• I wonder why you reposed the question here if you knew that answer? – Kaveh Jul 7 '12 at 6:22
• @Kaveh: I didn't figure out the answer until ~10 hours after I posted the question. (And in retrospect it seems so trivial...) If you prefer, I can delete it. – Xodarap Jul 7 '12 at 14:12
• No that's fine. It often happens that the OP answers their own question - there's even a badge for it :). If the answer came quickly, well that's just how it happens sometimes. Do accept the answer though, so it doesn't get flagged by the Community user repeatedly. – Suresh Venkat Jul 8 '12 at 4:14

$n^2$ processors can compare all ${n \choose 2}$ possibilities in constant depth, so yes it's in NC.