BBDD – Optimización de Consultas – Parte I

Una vez resuelta una consulta en álgebra relacional, debería buscar una consulta o expresión equivalente que sea lo mas óptima posible, es decir en la que se mejore el rendimiento (por ejemplo disminución en el volumen de datos para operar). Esta expresión equivalente será la FORMA CANÓNICA de dicha consulta.

Una consulta puede ser expresada en forma de árbol. Un árbol de consultas es una estructura de árbol que corresponde a la expresión en el álgebra relacional de una consulta; donde las hojas del árbol, representan los esquemas que intervienen en la consulta y los nodos internos son operadores del álgebra. La ejecución de una consulta consiste en la ejecución de un nodo interno cada vez que sus operandos están disponibles y reemplazar
ese nodo interno por el resultado de la operación. La ejecución termina cuando se ejecuta el nodo raíz.

El árbol que expresa a una consulta en forma canónica, se denomina ÁRBOL CANÓNICO.


Reglas de transformación de consultas en álgebra relacional

Para obtener la forma canónica de una consulta, se aplican reglas de transformación de operaciones del álgebra relacional, esto se basa en el hecho de que se pueden expresar consultas equivalentes.

Para definir las reglas de transformación, usaremos los siguientes esquemas:

  • EMPLEADO (#Emp, nYAp, dir, #DeptoTrab)
  • DEPARTAMENTO (#Depto, nombre, fechaCreación, #EmpDir)
  • PROYECTO (#Proy, nomProy, ubicación, #DeptoRespons)

Tenga en cuenta que por cada departamento existe un único director (#EmpDir)


Regla 1 – Cascada de selecciones: Una selección con una condición compuesta puede ser descompuesta en una secuencia de selecciones individuales.

Importante: en caso de que la condición de selección tuviese conectores lógicos or, no es válida esta regla.


Regla 2 – Conmutatividad de la selección: La operación de selección es conmutativa.


Regla 3 – Cascada de proyecciones: En una cascada de proyecciones todas, excepto la última pueden ser ignoradas.


Regla 4 – Conmutatividad de la selección con la proyección: Si una condición c de una selección involucra sólo atributos A1,…,An en la lista de la proyección, las dos operaciones pueden conmutarse.

Nota: el orden en el que se conmutan las proyecciones y las selecciones dependerá de la naturaleza de los datos, ya que en el caso de tablas con muchos atributos, es aconsejable bajar las proyecciones mientras que en el caso de tablas con miles de tuplas insertadas es aconsejable bajar la selección, es decir hacerla lo antes posible.


Regla 5 – Conmutatividad del producto natural: el producto natural es conmutativo


Regla 6 – Conmutatividad de la selección con el producto cartesiano: Si todos los atributos de la condición de la selección involucran sólo atributos de una de las relaciones del producto cartesiano (por ejemplo R) las dos operaciones pueden conmutarse como sigue.

Alternativamente, si la condición c de la selección pude escribirse como c1 and c2 donde c1 involucra sólo atributos de R y c2 sólo de S las operaciones se conmutan como:

La misma regla se aplica si la operación es un producto natural.


Regla 7 – Conmutatividad de la proyección con el producto natural (ver limitante con el producto cartesiano) : Si la lista de la proyección es L= {A1,…,An, B1, …, Bm} donde A1,…,An son atributos de R y B1,…, Bm son atributos de S. Si la condición del producto natural involucra sólo atributos de L, las dos operaciones pueden conmutarse como:

Nota: en este caso en el producto natural se indica explícitamente cual es el atributo por el cual se hace el producto. Esto se debe a que su nombre en las tablas no es el mismo. Este mismo recurso se usa a lo largo del documento.

Si la condición c del producto natural contiene atributos adicionales a L, estos pueden ser agregados a la lista y entonces una proyección al final será necesaria. Por ejemplo si los atributos C1,…Ck de R y D1,…Dj de S están involucrados en la condición c pero no en la lista de la proyección las operaciones se conmutan como:

En el caso del producto cartesiano, al no haber condición se aplica la primera parte de la regla.


Regla 8 – Conmutatividad de operaciones de conjunto: Las operaciones de Unión e Intersección son conmutativas. La resta no lo es.


Regla 9 – Asociatividad del producto natural, producto cartesiano, unión e intersección: Estas cuatro operaciones son individualmente asociativas. Esto es si θ es cualquiera de ellas:


Regla 10 – Conmutatividad de la selección con las operaciones de conjunto: La selección conmuta con la unión, la intersección y la diferencia. Si θ es una de las tres operaciones de conjuntos :


Regla 11 – La proyección conmuta con la Unión:

Nota: Tener en cuenta que R y S deben ser de unión compatible para que la parte de la regla (πL (R)) ∪ (πL (S)) -> πL (R ∪ S) valga.


Regla 12 – Otras transformaciones: una condición c se puede convertir a una condición equivalente usando las leyes de DeMorgan:


Continúa en unos días 😀😁😁😀😀😀

1 pensamiento en “BBDD – Optimización de Consultas – Parte I”

  1. Pingback: BBDD – Optimización de Consultas – Parte II – La Compu Del Vecino

Dejá un comentario