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ágina25/36
fecha de publicación02.02.2016
tamaño0.75 Mb.
tipoDocumentos
b.se-todo.com > Economía > Documentos
1   ...   21   22   23   24   25   26   27   28   ...   36

4.8.3 Optimización centralizada de consultas



En esta sección se revisa el proceso de optimización de consultas para ambientes centralizados. Esta presentación es un prerequisito para entender la optimización de consultas distribuidas por tres razones. Primero, una consulta distribuida se transforma a varias consultas locales cada una de las cuales se procesa en forma centralizada. Segundo, las técnicas para optimización distribuida son, por lo general, extensiones de técnicas para optimización centralizada. Finalmente, el problema de optimización centralizada es mucho más simple que el problema distribuido.
Las técnicas de optimización más populares se deben a dos sistemas de bases de datos relacionales: INGRES y System R. Ambos sistemas tienen versiones para sistemas distribuidos pero sus técnicas difieren sustancialmente. Por un lado, INGRES utiliza una técnica dinámica la cual es ejecutada por un intérprete. Por otra parte, System R utiliza un algoritmo estático basado en búsqueda exhaustiva. Los sistemas más comerciales utilizan variantes de la búsqueda exhaustiva por su eficiencia y compatibilidad con la compilación de consultas.
Por brevedad, en esta sección se revisará brevemente el esquema de optimización de INGRES. Posteriormente, se revisará con mayor detenimiento el esquema de System R.

Algoritmo de INGRES



INGRES usa un algoritmo de optimización dinámico que recursivamente divide una consulta en el cálculo relacional en piezas más pequeñas. Combina dos fases de la descomposición cálculo-álgebra relacional y optimización. No requiere información estadística de la base de datos. Las dos fases generales del algoritmo son:


  1. Descompone cada consulta con múltiples variables en una secuencia de consultas con una sola variable común.

  2. Procesa cada consulta mono-variable mediante un procesador de consultas de una variable el cual elige, de acuerdo a algunas heurísticas, un plan de ejecución inicial. Posteriormente, ordena las operaciones de la consulta considerando los tamaños de las relaciones intermedias.


La primera parte se hace en tres pasos como se indica a continuación:


  • Reemplaza una consulta q con n variables en una seria de consultas

q1q2  ...  qn

donde qi usa el resultado de qi-1.

  • La consulta q se descompone en q’  q’’, donde q’ y q’’ tienen una variable en común la cual es el resultado de q’.

  • Se reemplaza el valor de cada tuplo con los valores actuales y se simplifica la consulta

q( V1, V2, ..., Vn)  (q’( t1, V2, ..., Vn), t1R)
Ejemplo 4.17. Para ilustrar el paso de desacoplamiento del algoritmo de INGRES considere la siguiente consulta:
"Encuentre los nombres de los empleados que trabajan en el proyecto CAD/CAM"
Esta consulta se puede expresar en SQL de la siguiente forma:
q1: SELECT E.ENOMBRE

FROM E, G, J

WHERE E.ENO = G.ENO AND G.JNO = J.JNO AND JNAME = "CAD/CAM"
q1 es reemplazada por q11 seguida de q’ en donde JVAR es una relación intermedia.
q11: SELECT J.JNO INTO JVAR

FROM J

WHERE JNAME = "CAD/CAM"

q: SELECT E.ENOMBRE

FROM E, G, JVAR

WHERE E.ENO = G.ENO AND G.JNO = JVAR.JNO
La aplicación sucesiva de este paso a q’ puede generar
q12: SELECT G.ENO INTO GVAR

FROM G, JVAR

WHERE G.JNO = JVAR.JNO
q13: SELECT E.ENOMBRE

FROM G, GVAR

WHERE E.ENO = GVAR.ENO
Así, q1 ha sido reducido a la secuencia de consultas q11q12q13. La consulta q11 es monovariable. Sin embargo, las consultas q12 y q13 no son monovariables. Veamos como transformar q13. La relación definida por la variable GVAR es sobre un solo atributo (ENO). Supongamos que contiene únicamente dos tuplos: y . La sustitución de GVAR genera dos consultas de una sola variable:
q131: SELECT E.ENOMBRE

FROM E

WHERE E.ENO = "E1"
q132: SELECT E.ENOMBRE

FROM E

WHERE E.ENO = "E2"
Algoritmo de System R
System R ejecuta una optimización de consultas estática basada en búsqueda exhaustiva del espacio solución. La entrada del optimizador es un árbol del álgebra relacional que resulta de una consulta en SQL. La salida es un plan de ejecución que implementa el árbol del álgebra relacional "óptimo".
El optimizador asigna un costo a cada árbol candidato y obtiene aquel con costo menor. Los árboles candidatos se obtienen permutando el orden de las juntas de las n relaciones de una consulta usando las reglas de conmutatividad y asociatividad. Para limitar el costo de optimización, el número de alternativas se reduce utilizando programación dinámica. El conjunto de estrategias alternativas se construye de forma dinámica, de manera que, cuando dos juntas son equivalentes por conmutatividad, se queda solo con la de costo más bajo. Más aún, cada vez que aparecen productos Cartesianos se trata de eliminar la estrategia correspondiente.
El costo de una estrategia candidato es una combinación pesada de costos de I/O y CPU. La estimación de tales costos (en tiempo de compilación) se basa en un modelo de costo que proporciona una fórmula de costo para cada operación de bajo nivel. Para la mayoría de las operaciones, esas fórmulas de costo se basan en las cardinalidades de los operandos. La información de las cardinalidades se obtiene del mismo System R. La cardinalidad de las relaciones intermedias se estima de acuerdo a los factores de selectividad de las operaciones.
El algoritmo de optimización consiste de dos grandes pasos:


  1. Las consultas simples se ejecutan de acuerdo al mejor camino de acceso (basada en un predicado de selección).

  2. Para cada relación R, se estima el mejor ordenamiento de juntas, en donde R se accesa primero usando el mejor método de acceso a una sola relación. Así, se determinan todos los posibles ordenamientos de juntas, se determina el costo de cada ordenamiento y se elige aquel con el costo mínimo.


Para la junta de dos relaciones, la relación cuyos tuplos se leen primero se llama externa, mientras que la otra, cuyos tuplos se encuentran de acuerdo a los valores obtenidos de la relación externa, se llama relación interna. Una decisión importante es determinar el camino de acceso menos costoso a la relación interna.
Al considerar las juntas, hay dos algoritmos disponibles. El primero, llamado de ciclos anidados, compone el producto de las dos relaciones y se puede observar mediante el siguiente pseudocódigo.
Para cada tuplo de la relación externa (con cardinalidad n1)

Para cada tuplo de la relación interna (con cardinalidad n2)

junta los dos tuplos si el predicado de la junta es verdadero

end

end
Claramente, este método tiene complejidad n1*n2.
El segundo método, llamado junta-mezcla, consiste en mezclar dos relaciones ordenadas sobre el atributo de la junta. Los índices del atributo de la junta se pueden usar como caminos de acceso. Si el criterio de junta es igualdad, el costo de juntar dos relaciones de n1 y n2 páginas, respectivamente, es proporcional a n1 + n2.
Ejemplo 4.18. Considere la consulta q1 del Ejemplo 4.17. La gráfica de juntas de se muestra en la Figura 4.17. Suponga que se tienen los siguientes índices:
E tiene un índice en ENO

G tiene un índice en GNO

J tiene un índice en JNO y un índice en JNOMBRE
Supongamos que se seleccionan los siguientes caminos de acceso mejores para cada relación:
E: recorrido secuencial (ya que no hay selección sobre E)

G: recorrido secuencial (ya que no hay selección sobre G)

J: índice sobre JNOMBRE (ya que hay una selección en J basada en JNOMBRE)
La construcción dinámica del árbol de estrategias alternativas se presenta en la Figura 4.18. Note que el número de ordenamientos posibles de juntas es 3! los cuales son:
E  G  J

G J E

J  E G

J  G E

G E J

E  J  G

J  E  G
La operación marcadas como "podadas" se eliminan en forma dinámica. El primer nivel del árbol indica los mejores caminos de acceso a una sola relación. El segundo nivel indica, el mejor método de junta con cualquier otra relación. Las estrategias que utilizan el pruducto Cartesiano son inmediatamente podadas. Suponga que (E  G) y (G J) tienen un costo más alto que (G  E) y (J G), respectivamente. Así ellas pueden ser podadas ya que existe un orden equivalente con costo menor. Las dos posibilidades restantes están dadas en el tercer nivel del árbol. El mejor orden de las juntas es el de costo menor entre ((G  E)  J) y ((J  G)  E). El último es el único que tienen un índice útil en el atributo de selección y acceso directo a los tuplos de junta entre G y E. Por lo tanto, éste es elegido con el siguiente método de acceso:
Selecciona J usando el índice sobre JNOMBRE

Junta con G usando el índice sobre JNO

Junta con E usando el índice sobre ENO


Figura 4.17. Gráfica de juntas.

 
1   ...   21   22   23   24   25   26   27   28   ...   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