ninguno

Ejemplo 6.1
Considere el problema de optimización definido en la figura 6.5ª, el cual muestra la grafica de unión, los perfiles de la relación, y otras suposiciones básicas en los valores de los atributos.
Suponga que los perfiles de la figura 6.5 cuida el efecto de los reductores locales.
Ejemplo : Los reductores consisten en operaciones unarias de modo que podemos considerarlas como elpunto de partida para el algoritmo de optimización SSD-1.
Hay cuatro posibles semi-joins, que son mostrados en la difura 6.5b pero solo dos de ellos son rentables, aquellos que reducen la relación SUPPLY. La figura 6.5c muestra el desarrollo del calculo de cardinalidades, tamaños y valores distintos de las relaciones después de la selección de un nuevo semi-join en cada iteración. Y por consiguientela modificación de los costos y beneficios para otros semi-joins. Por el bien de la simplicidad la supocision es hecha tal que todos los valores de SNUM en SUPPLIER y/o DEPTNUM en DEPT están presentes en SUPPLY esto simplifica la evaluación de las selectividades.
Cuando un semi join es seleccionado, este es elminado del set de semi-joins que son considerados para la siguiente iteración.
Elalgoritmo básico incluye como resultado de sus dos primeros semi-joins rentables de la figura 6.5b en el reductor de SUPPLY. Como consecuencia de la reducción de la relación SUPPLY, un tercer semi join SUPPLIER SJ SUPPLY se vuelve rentable, este es seleccionado en la tercera iteracion.
Finalmente, un sitio debe ser seleccionado para ejecutar la consulta. El costo de transmicion asociado a cadaselección es mostrado en la figura 6.5c; el sitio 1 es seleccionado ya que el costo es minimo.
6.2.2.2 postoptimizacion
El algoritmo SDD1 aplica una heurística avariciosa, por que esta busca en cada una de las iteraciones por la mejor mejora sin tomar en cuenta las consecuencias en las futuras iteraciones.
Para mejorar la solución obtenida una postoptimizacion puede ser hecha, la postoptimizacion siguedos criterios.
1. Eliminando los semi-joins cuyo efecto es solo reducir las relaciones que ya se encuentran en el sitio seleccionado para ejecutar la consulta.
2. Retrasando los semi-joins costosos R SJ S después de la reducción de S por medio de otros semi-joins, esto requiere cambiar el orden de la aplicación de las operaciones de semi-joins.
La primera postoptimizacion puede ser aplicada alejemplo 6.1
Ejemplo 6.1(continuado)
El semi-join SUPPLIER SJ SUPPLY esta caido, desde que la relacion SUPPLIER la cual fue reducida por el semi-join, esta almacenada en el sitio 1, donde todas las relaciones se recogen. El resultado final de la optimización completa de la consulta Q1 es mostrada en la figura 6.5d
Los nodos representan relaciones. Los bordes operandos de operaciones semi-join.( el primer operando es conectado al resultado por un borde vertical.
Programa semi-join antes de aplicar el criterio 2 de la postoptimizacion.





La segunda postoptimizacion se realiza mediante la construcción, durante la iteraciones principales del algoritmo básico , un grafico de flujo que muestra el orden en el cual los semijoins son seleccionados; progresivamente las relacionesreducidas corresponden a nodos, y los semi-joins corresponden a los bordes del grafico de flujo.
El algoritmo postoptimization consiste en seleccionar en el flujo de la gráfica los semi-joins mas caros y retrasarlos si es posible.
Mas formalmente, las dejemos(T,S) ser un arco de la grafica de flujo describiendo que un semijoin T SJ S toma el lugar, y dejemos S´ser cualquier nodo que representa lareducción S; la postoptimizacion consiste en reemplazar (T,S) por (T,S´), previniendo que no introduzca los ciclos en el gráfico (un grafico con ciclos corresponde a un programa no ejecutable).
Esta simplificación es mostrada en la figura 6.6. La ventaja de esta simplificación son las dos siguientes:
1.- Menos tuplas son enviadas de S a T ya que S se reduce a S ' .
2.- La selectividad del...