¿Pueden las uniones ser paralelizadas?

Supongamos que queremos unir dos relaciones en un predicado. ¿Está esto en Carolina del Norte?

Me doy cuenta de que una prueba de que no está en Carolina del Norte equivaldría a una prueba de que $P\not=NC$ , por lo que aceptaría evidencia de que es un problema abierto como respuesta.

Estoy interesado en el caso general, así como en casos específicos (por ejemplo, tal vez con alguna estructura de datos específica se puede paralelizar).

EDITAR: para traer algunas aclaraciones de los comentarios a esta publicación:

• Podríamos considerar un equijoin . En un único procesador, un algoritmo basado en hash se ejecuta en y esto es lo mejor que podemos hacer, ya que tenemos que leer cada conjuntoO ( | A | + | B |$A.x = B.y$$O(|A|+|B|)$
• Si el predicado es un "recuadro negro" donde tenemos que verificar cada par, haypares, y cada uno podría estar en o no, entonces posibilidades. Verificar cada par divide las posibilidades a la mitad, por lo que lo mejor que podemos hacer es .2 a b O ( a b $|A|\cdot|B|$$2^{ab}$$O(ab)$

¿Se podría mejorar cualquiera de estos (o algún tercer tipo de combinación) para en múltiples procesadores?$\log^k n$

procesadores pueden comparar todos ($n^2$ posibilidades en profundidad constante, así que sí, está en Carolina del Norte.${n \choose 2}$