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

CC BY-SA 3.0
2012-07-07T01:35:10.877Z
2012-07-07T01:35:10.877Z
Xodarap
<p>Suppose we want to join two relations on a predicate. Is this in NC?</p>

<p>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.</p>

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

<p>Some specifics:</p>

<ul>
<li>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</li>
<li>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)$.</li>
</ul>

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

<p>(Reposted from <a href="https://cs.stackexchange.com/questions/2235/can-joins-be-parallelized">here</a> as per <a href="https://cstheory.meta.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231">site policy</a>.)</p>

CC BY-SA 3.0
2012-07-06T18:25:15.550Z
@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](http://en.wikipedia.org/wiki/Join_(relational_algebra)#Joins_and_join-like_operators) and [practice](http://en.wikipedia.org/wiki/Join_(SQL))
Xodarap
CC BY-SA 3.0
2012-07-07T06:22:36.540Z
I wonder why you reposed the question here if you knew that answer?
Kaveh
CC BY-SA 3.0
2012-07-07T14:12:22.637Z
@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
CC BY-SA 3.0
2012-07-08T04:14:45.487Z
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
CC BY-SA 3.0
2012-07-08T15:04:11.150Z
@Suresh: Sounds good :-) SE prevents you from accepting your own answer right away, but when it's possible I'll accept.
Xodarap
<time-complexity><dc.parallel-comp><db.databases>
Can we do joins in NC?
Xodarap
# Can we do joins in NC?

(Asked by: username_0 on 2012-07-06)

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](https://cs.stackexchange.com/questions/2235/can-joins-be-parallelized) as per [site policy](https://cstheory.meta.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231).)

**Tags:** time-complexity, dc.parallel-comp, db.databases

> **Comments:**
> **username_0**: @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](http://en.wikipedia.org/wiki/Join_(relational_algebra)#Joins_and_join-like_operators) and [practice](http://en.wikipedia.org/wiki/Join_(SQL))  
> **username_1**: I wonder why you reposed the question here if you knew that answer?  
> **username_0**: @username_1: 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.  
> **username_2**: 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.  
> **username_0**: @Suresh: Sounds good :-) SE prevents you from accepting your own answer right away, but when it's possible I'll accept.  

---

## 1 answers

### Answer by username_0 on 2012-07-07. Score: 6 | Accepted answer

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


---

