9
$\begingroup$

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

EDIT: to bring some clarifications from the comments into this post:

  • 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 set
  • 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?

$\endgroup$
8
  • $\begingroup$ If this question is motivated by a practical problem, keep in mind that NC might not be the most suitable notion of "parallelisable". $\endgroup$
    – Raphael
    Jun 5, 2012 at 18:57
  • $\begingroup$ @Raphael: it's not, but could you link to something about why? I can ask this as a separate question if that's more appropriate. $\endgroup$
    – Xodarap
    Jun 5, 2012 at 19:28
  • $\begingroup$ It is not clear for me what you are asking. What is the base relational database query language that you are adding the join operator to it? Or are you asking the complexity of queries which only contain join operators? Or are your real question is whether it is possible to run join operators "in parallel" to achieve better time complexity? (similar to way that say AND can be done in parallel) Also note that (safe) SQL queries corresponds to FOL(Count). $\endgroup$
    – Kaveh
    Jun 5, 2012 at 20:35
  • $\begingroup$ Or are you asking what are the best known upper-bound and lower-bound (complexity classes) on the complexity computing the join given two relational databases as input. $\endgroup$
    – Kaveh
    Jun 5, 2012 at 20:40
  • 2
    $\begingroup$ @Xodarap: You might find the answers and comments on this question of mine instructive; I know I did. Kruskal et al. (1990) is also a good read. $\endgroup$
    – Raphael
    Jun 6, 2012 at 9:22

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ If you are going to take OR, the depth will be logarithmic. $\endgroup$
    – sdcvvc
    Jul 7, 2012 at 9:56
  • $\begingroup$ @sdcvvc: Fair enough. At the extreme you could encode 3SAT in the relational calculus, so this result really only holds if your selections are simple (i.e. constant time). $\endgroup$
    – Xodarap
    Jul 7, 2012 at 16:48

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.