¿Pueden las uniones ser paralelizadas?

9

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 PAGSnorteC , 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 | )UNA.X=si.yO(El |UNAEl |+El |siEl |)
  • 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 )El |UNAEl |El |siEl |2unasiO(unasi)

¿Se podría mejorar cualquiera de estos (o algún tercer tipo de combinación) para en múltiples procesadores?Iniciar sesiónknorte

Xodarap
fuente
Si esta pregunta está motivada por un problema práctico, tenga en cuenta que NC podría no ser la noción más adecuada de "paralelismo".
Raphael
@Raphael: no lo es, pero ¿podrías vincular a algo sobre por qué? Puedo hacer esto como una pregunta separada si es más apropiado.
Xodarap
No está claro para mí lo que estás preguntando. ¿Cuál es el lenguaje de consulta de base de datos relacional base al que le está agregando el operador de unión? ¿O está preguntando la complejidad de las consultas que solo contienen operadores de unión? ¿O su verdadera pregunta es si es posible ejecutar operadores de unión "en paralelo" para lograr una mejor complejidad temporal? (similar a la forma en que se dice Y se puede hacer en paralelo) También tenga en cuenta que las consultas SQL (seguras) corresponden a FOL (Count).
Kaveh
¿O está preguntando cuáles son los límites superiores e inferiores más conocidos (clases de complejidad) en la complejidad que computa la unión dadas dos bases de datos relacionales como entrada.
Kaveh
2
@ Xodarap: Puede encontrar las respuestas y comentarios sobre esta pregunta mía instructiva; Sé que lo hice. Kruskal y col. (1990) también es una buena lectura.
Raphael

Respuestas:

1

procesadores pueden comparar todos ( nnorte2 posibilidades en profundidad constante, así que sí, está en Carolina del Norte.(norte2)

Xodarap
fuente
Si vas a tomar OR, la profundidad será logarítmica.
sdcvvc
@sdcvvc: lo suficientemente justo. En el extremo, puede codificar 3SAT en el cálculo relacional, por lo que este resultado solo se cumple si sus selecciones son simples (es decir, tiempo constante).
Xodarap