Traduccioon

6.2 join queries

En esta sección, el análisis se restringe a consultas de unión, es decir, consultas cuya gráfica optimización incluye sólo une. Los algoritmos que se presentan en esta sección no tienen en cuenta explícitamente la fragmentación de la relación. Por lo tanto, en esta sección no utilizamos la noción de fragmentación, y se utiliza el término genérico de "relación" para denotar cualquiera de fragmentos o relaciones no fragmentada que aparecen como nodos de los grafos de optimización. Algoritmos de optimización se pueden clasificar en dos clases:

1 -. Algoritmos que utilizan semi-joins para la reducción de las relaciones antes de transmitirlos.

2.-Algoritmos que no consideran semi-joins.

En primer lugar, presentamos las bases generales de los algoritmos que utilizan semi-joins, y luego nos muestran dos enfoques específicos para la optimización, que los utilizan. Ambos enfoques consideran sólo los costos de transmisión como la función objetivo. Por último, se muestra un enfoque para la optimización de consultas que no utiliza semi-joins, y que tiene en cuenta también los costes de transformación locales.

El gráfico de optimización de una consulta de unión se compone sólo de los nodos, que representan las relaciones, y los bordes, que representan une; este tipo si la representación que ya se introdujo en el capítulo 4 y llama une gráfico. Como nos permitimos más de una unión especificación entre dos relaciones, una gráfica de unión es, de hecho, una multígrafo.

6.2.1. El uso de programas Semi-Joins para consultas de unión.

Empecemos por considerar un ejemplo sencillo de un programa semi-join y su costo de transmisión. Recordemos de la sección 5.2.7 que un programa semi-join entre dos relación R y S sobre dos atributos A y B se define como (RSJA=BS)JNA=BS , y es equivalente a RJNA=BS. Supongamos que R y S re asignó en sitios r y s, respectivamente. Entonces, realizando el programa de semi-.join corresponden a:

1.- Enviar PJS(S) al sitio r, a un costo:

2.- El cálculo de la r semi-join en r, a un costo nulo; dejar:

3.-Enviar R’ a s , a un costo:

4.- Calcular la unión en s, a un costo nulo.

El coste global es:

Semi-combinación no es simétrica, y claramente el otro programa semi-join (SSJR) JNR tiene un costo diferente. La comparación de los dos costos resuelve el problema de determinar el programa de semi-join óptima para la combinación de R y S. Tenga en cuenta que los dos

Comparando CJN y CSJ, el programa semi-join es rentable.

En muchos casos la desigualdad anterior se mantiene, porque el tamaño (B) y Val (B [S]) son pequeñas mientras que la tarjeta (R) es más grande que la tarjeta de (R '). Por lo tanto, los algoritmos que se presentan en la sección 6.2.2 y 6.2.3 simplemente ignoran el uso de combinaciones como táctica de procesamiento de consultas.

6.2.1.1 Reducción de relación utilizando semi-joind.

Semi-joins puede considerarse como reductores, es decir, las operaciones que se pueden aplicar, de manera similar a las operaciones unitarios, para reducir la cardinalidad de sus operandos. Es evidente que para cualquier R y S que puede ser semi-joins, tenemos (R). La extensión de esta propiedad para el caso de una consulta con tres relaciones que permiten semi-join entre cada par posible, tenemos, para cualquier. R, S y T.

pero también:

Vamos a llamar a programas de R reductor de una cadena de semi-joins, como R 'y

...