En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos




descargar 0.75 Mb.
títuloEn años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos
página26/36
fecha de publicación02.02.2016
tamaño0.75 Mb.
tipoDocumentos
b.se-todo.com > Economía > Documentos
1   ...   22   23   24   25   26   27   28   29   ...   36

4.8.4 Ordenamiento de juntas para consultas fragmentadas



Como se puede apreciar en la sección anterior, el ordenamiento de juntas es un aspecto importante para la optimización de consultas centralizadas. El ordenamiento de las juntas en ambientes distribuidos es aún más importante ya que las juntas entre fragmentos pueden incrementar los costos de comunicación.
Consideremos inicialmente el caso más simple de transferencia de operandos en una junta simple. La consulta es R S en donde R y S son relaciones almacenadas en nodos diferentes. La elección obvia es transferir la relación más pequeña al nodo con la relación más grande como se ilustra en la Figura 4.19.


Figura 4.18. Alternativas para el ordenamiento de juntas.
Consideremos ahora el caso en donde hay más de dos relaciones en la junta. El objetivo sigue siendo transferir los operandos más pequeños. La dificultad aparece del hecho de que las operaciones de juntas pueden reducir o incrementar el tamaño de los resultados intermedios. Así, estimar el tamaño de los resultados de las juntas es obligatorio pero difícil. Una solución es estimar el costo de comunicación de todas las estrategias posibles y elegir la de costo menor. Sin embargo, el número de estrategias crece rápidamente con el número de relaciones. Este enfoque, utilizado por System R*, hace que la optimización sea costosa pero se puede amortizar si la consulta se ejecuta con frecuencia.


Figura 4.19. Transferencia de operandos en una operación binaria.

 

Ejemplo 4.19. Considere la siguiente consulta expresada en el álgebra relacional:
J  JNO E  ENO G
cuya gráfica de juntas se presenta en la Figura 4.20. Note que se han hecho suposiciones acerca de la ubicación de cada relación. Esta consulta se puede ejecutar en al menos cinco estrategias diferentes. R  nodo j denota que la relación R se transfiere al nodo j.


  1. E  nodo 2

Nodo 2 calcula E’ = E  G

E’  nodo 3

Nodo 3 calcula E’ J

  1. G  nodo 1

Nodo 1 calcula E’ = E  G

E’  nodo 3

Nodo 3 calcula E’  J

  1. G  nodo 3

Nodo 3 calcula G’ = G J

G’  nodo 1

Nodo 1 calcula G’  E

  1. J nodo 2

Nodo 2 calcula J’ = J  G

J’  nodo 1

Nodo 1 calcula J’  E

  1. E  nodo 2

J  nodo 2

Nodo 2 calcula E  J  G


Figura 4.20. Gráfica de juntas distribuida.

 

4.8.5 Optimización de consultas distribuidas



En esta sección se ilustrará brevemente el uso de las técnicas presentadas previamente en las extensiones distribuidas de INGRES y System R.

Algoritmo Distribuido de INGRES



El algoritmo de optimización de consultas para INGRES distribuido se deriva del algoritmo usado en INGRES centralizado. La función objetivo del algoritmo pretende minimizar la combinación del costo de comunicación junto con el tiempo de respuesta. Dado que estos criterios pueden presentar conflictos entre sí se considera una combinación pesada de ambos factores. Este algoritmo ignora el costo de transmisión de los datos al nodo de resultados. El algoritmo también toma ventaja de la fragmentación, pero únicamente considera fragmentación horizontal. El algoritmo utiliza mensajes de tipo broadcast, de uno a todos.
Ejemplo 4.21. Considere la consulta
E  G  J
y suponga que la relación E esta fragmentada donde la ubicación de cada fragmento se muestra a continuación:


Nodo 1

Nodo 2

E1

E2

G

J


Existen varias estrategias posibles de ejecución. Dos de ellas son las siguientes:


  1. Ejecutar la consulta completa E G  J transmitiendo E1 y G al nodo 2.

  2. Ejecutar (E  G)  J transfiriendo E1  G y G al nodo 2.

La elección entre las dos posibilidades requiere de una estimación del tamaño de los resultados intermedios. Por ejemplo, si size(E1  G) > size(E1), la estrategia 1 es mejor.



Algoritmo R*



El algoritmo de optimización de consultas distribuidas R* es una extensión sustancial a las técnicas desarrolladas para el optimizador de System R. La función de costo considera el costo de procesamiento local así como el costo de comunicación. Sin embargo, no utiliza fragmentos sino relaciones completas como unidades de distribución. La compilación de la consulta es una tarea distribuida en R*, la cual es coordinada por un nodo maestro. El optimizador del maestro hace todas las decisiones entre nodos, tales como la selección de los nodos de ejecución así como el método de transferencia de datos. Los nodos aprendices que son todos los otros nodos involucrados en la consulta hacen únicamente decisiones locales, tales como, el orden de las juntas en la consulta local y generan planes de acceso local para la consulta.
Para juntar dos relaciones existen tres nodos candidatos: el nodo de la primera relación, el nodo de la segunda relación o un tercer nodo (por ejemplo, el nodo donde se hará una junta con una tercera relación). En R*, se utilizan dos métodos para las transferencias de datos entre nodos.


  1. Transfiere todo. La relación completa es transferida al nodo donde se realiza la junta y almacenada en una relación temporal antes de hacer la junta. Si el algoritmo de la junta es por medio de una mezcla, la relación no necesita ser almacenada y el nodo que ejecuta la junta puede procesar los tuplos conforme llegan. Este método requiere de grandes transferencias de datos, pero utiliza pocos mensajes. Es adecuado si las relaciones son relativamente pequeñas.

  2. Lee conforme lo necesita. La relación externa es recorrida secuencialmente y, para cada tuplo, el valor de la junta se envía al nodo de la relación interna, el cual selecciona los tuplos internos que satisfacen el predicado de la junta y envía los tuplos seleccionados al nodo con la relación externa. La cantidad de mensajes es proporcional al tamaño de la relación externa. Este método es adecuado si las relaciones son grandes y la selectividad de la junta es buena.


Dada la junta de una relación externa R con una relación interna S en el atributo A, existen cuatro estrategias para realizar la junta. A continuación se describirá cada estrategia en detalle y se proporcionará en cada caso una versión simplificada de la fórmula de costo. LC denota el costo de procesamiento local (I/O + CPU) y CC denota el costo de comunicación.
Estrategia 1. Se transfiere la relación externa completa al nodo con la relación interna. En este caso los tuplos externos se pueden juntar con S conforme llegan. Así se tiene
Costo total = LC( recuperar card(R) tuplos de R)

+ CC(size(R))

+ LC( recuperar s tuplos de S)*card(R)
Estrategia 2. Se transfiere la relación interna completa al nodo con la relación externa. En este caso los tuplos internos no se pueden juntar conforme llegan y se tienen que almacenar en una relación temporal T.
Costo total = LC( recuperar card(S) tuplos de S)

+ CC(size(S))

+ LC( almacenar card(S) tuplos en T)

+ LC( recuperar card(R) tuplos de R)

+ LC( recuperar s tuplos de T)*card(R)
Estrategia 3. Se obtienen los tuplos de la relación interna conforme se necesitan para cada tuplo de la relación externa. En este caso, para cada tuplo de R, el atributo de junta se envía al nodo de S. Luego s tuplos de S que satisfacen el atributo son recuperados y enviados al nodo de R para ser juntados conforme llegan.
Costo total = LC( recuperar card(R) tuplos de R)

+ CC(length(A)) * card(R)

+ LC( recuperar s tuplos de S)*card(R)

+ CC(s * length(S)) * card(R)
Estrategia 4. Se mueven las relaciones a un tercer nodo y se calcula la junta ahí. En este caso la relación interna se mueve al tercer nodo y se almacena en una relación temporal T. Luego la relación externa se mueve al tercer nodo y sus tuplos se juntan con T conforme llegan.
Costo total = LC( recuperar card(S) tuplos de S)

+ CC(size(S))

+ LC( almacenar card(S) tuplos en T)

+ LC( recuperar card(R) tuplos de R)

+ CC(size(R))

+ LC( recuperar s tuplos de T)*card(R)

 
1   ...   22   23   24   25   26   27   28   29   ...   36

similar:

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconBases de datos de secuencias de adn y proteínas

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconUna red de comunicaciones es la combinación de hardware, software...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconResumen a lo largo de los años, la agricultura se ha mantenido como...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconResumen El presente trabajo de investigación bibliográfica trata...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconCientífico británico que sentó las bases de la moderna teoría evolutiva,...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconRecibimos de las distintas sucursales de la empresa los datos correspondientes a las ventas en

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconEntre las herramientas utilizadas en la minería de datos (Data Mining)...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconMinería de Datos aplicados a las ventas con Tarjeta de Crédito realizados...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconBases moleculares de las acciones de la insulina

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconBases moleculares de las acciones de la insulina




Todos los derechos reservados. Copyright © 2019
contactos
b.se-todo.com