BBDD – Optimización de Consultas – Parte II

Del día anterior seguimos con  la aplicación de las reglas. por cualquier duda, pasá por acá y repasalas.

Algoritmo de transformación de consultas en álgebra relacional:

Una vez definidas las reglas de transformación para optimizar una consulta en álgebra relacional, describiremos los pasos de un algoritmo de transformación de consultas en álgebra relacional que usa las reglas de transformación. Tener en cuenta que este algoritmo no es secuencial. Puede ser que al agregar nuevas proyecciones, se deban rever las reglas propuestas.

  1. Usando la regla 1- separar las condiciones compuestas de la selección en una cascada de selecciones
  2. Usando las reglas 2, 4, 6, y 10 mover cada operación de selección lo más abajo posible en el árbol de acuerdo con los atributos involucrados en la selección.
  3. Usando la regla 9 reacomodar las hojas del árbol de manera que las relaciones con selecciones mas restrictivas sean ejecutadas primero; por más restrictivas se entiende aquellas que produzcan la relación más chica en cantidad de tuplas o en tamaño absoluto.
  4. Transformar los productos naturales en productos cartesianos con selecciones cuyas condiciones representan la condición del producto natural. Es decir si tengo A|X|cond B ≡ σcond (A |X| B) ≡ σcond (σc (A X B)) donde c representa la condición del producto natural y cond es alguna condición adicional que haya puesto en el producto natural. Tener en cuenta que cond, podría no existir.

Usar las reglas 3, 4, 7, y 11 para mover las proyecciones lo más abajo posible en el árbol y crear nuevas proyecciones cuando sea posible (nota: agregar proyecciones ayuda a reducir la cantidad de datos que se manipula en las consultas)


Proceso de optimización de consultas en álgebra relacional:

Las etapas principales del proceso de optimización, dada una consulta escrita en álgebra relacional, serán las siguientes:

  1. Escribir el árbol de la consulta.
  2. Aplicar el algoritmo de optimización, indicando reglas de optimización usadas y pasos del algoritmo realizados para hallar el árbol canónico de la consulta.
  3. Explicitar cual es el árbol canónico y escribir la consulta resultante del proceso de optimización (consulta canónica).

Ejemplos

Una vez introducidos los conceptos de optimización, veremos ejemplos de aplicación del
proceso propuesto anteriormente.

Ejemplo 1:

Sea el siguiente esquema que modela una biblioteca.

LIBRO( titulo, autor, eNom, nroInv) EDITORIAL(eNom,eDir,eCiudad) SOCIO(nom, dir, ciudad, nroSocio) PRESTAMO(nroSocio, nroInv, fecha)

Supongamos que tenemos una consulta que genera la información completa sobre cada uno de los préstamos (datos del socio y del libro).

Donde

F = PRESTAMO.nroSocio=SOCIO.nroSocio and PRESTAMO.nroInv=LIBRO.nroInv

S = título, autor, eNom,nroInv, nom, dir, ciudad, nroSocio, fecha

Ahora queremos refinar esa consulta, de modo de obtener una lista de títulos de libros prestados antes del 1/4/95

El árbol de consulta es el siguiente:

Una vez escrito el árbol de la consulta, debemos hallar el árbol canónico equivalente.

Realizamos las selecciones lo antes posible. Se aplican las siguientes reglas:

  • Regla 1: Cascada de Selecciones (transformo F en F1 y F2),
  • Regla 2: Conmutatividad de la Selección (primero selecciono con F2 y luego con F1)
  • Regla 6: Conmutatividad de la selección con el producto cartesiano ( la selección con F1 conmuto con el producto cartesiano)

F1= PRESTAMO.nroSocio=SOCIO.nroSocio

F2= PRESTAMO.nroInv=LIBRO.nroInv

Para llevar lo más abajo posible la selección con la fecha, se aplican las siguientes reglas:

  • Regla 4: Conmutatividad de la selección con la proyección
  • Regla 2: Conmutatividad de la selección
  • Regla 6: Conmutatividad de la selección con el producto cartesiano
  • Regla 2: Conmutatividad de la selección
  • Regla 6: Conmutatividad de la selección con el producto cartesiano

Ahora se desean eliminar proyecciones innecesarias, entonces se aplica la Regla 3:

Cascada de proyecciones

Supongamos que se decide agregar una proyección y no se hace lo más restrictivamente posible, sino que se va a agregar en un lugar de la consulta que requerirá realizar pasos de optimización adicionales.

Por el paso e del algoritmo propuesto se agregan proyecciones:

Para reducir el espacio de búsqueda de la consulta, se aplica la Regla 7: Conmutatividad de la proyección con el producto cartesiano.

Supongamos que se decide agregar una proyección y no se hace lo más restrictivamente posible, sino que se va a agregar en un lugar de la consulta que requerirá realizar pasos de optimización adicionales.

Por el paso e del algoritmo propuesto se agregan proyecciones

Para reducir el espacio de búsqueda de la consulta, se aplica la Regla 7: Conmutatividad de la proyección con el producto cartesiano

Luego de aplicar todas las reglas descriptas y pasos del algoritmo, se obtiene el árbol canónico.

La consulta canónica es la siguiente:

F1= PRESTAMO.nroSocio=SOCIO.nroSocio

F2= PRESTAMO.nroInv=LIBRO.nroInv

Mientras que el árbol canónico es el siguiente:

De esta manera, se finaliza con el proceso propuesto.



Ejemplo 2:

Suponga que tiene el siguiente esquema que representa un conjunto de departamentos con sus respectivos proyectos.

  • DEPARTAMENTO (#Depto, nombre, fechaCreación)
  • PROYECTO (#Proy, nomProy, ubicación, #Depto)

La consulta que analizaremos será: Obtener el nombre y el número de los departamentos que poseen proyectos ubicados en la ciudad de La Plata.Proponemos la siguiente expresión en álgebra relacional:

El árbol de la consulta es el siguiente:

Una vez escrito el árbol de la consulta, debemos hallar el árbol canónico equivalente. Por las características del árbol de la consulta, lo que podemos hacer es aplicar el paso d del algoritmo propuesto. Transformar los productos naturales en productos cartesianos con selecciones cuyas condiciones representan la condición del producto natural. Se aplica además el paso e, es decir se agregan nuevas proyecciones.

Nota: Al momento de realizar la operación de selección se debe desambigüar la tabla de origen del atributo #Depto.

Luego de aplicar todos los pasos del algoritmo descripto, se obtiene el árbol canónico.

La consulta canónica es la siguiente:

Mientras que el árbol canónico es el siguiente:

De esta manera, se finaliza con el proceso propuesto.


 

 

Dejá un comentario