Reglas de Equivalencia

Para poder probar las combinaciones posibles que puede utilizar un gestor, se basaran en las reglas de equivalencia.

• Selección:
  • Cascada: ${\sigma }_{c_1\wedge c_2\wedge \cdots \wedge c_n}(R)={\sigma }_{c_1}({\sigma }_{c_2}(\dots ({\sigma }_{c_n}(R))\dots )$
  • Unión: ${\sigma }_{c_1\vee c_2\vee \cdots \vee c_n}(R)={\sigma }_{c_1}(R)\cup {\sigma }_{c_2}(R)\cup \cdots \cup {\sigma }_{c_n}(R)$
  • Conmutatividad: ${\sigma }_{c_1}({\sigma }_{c_2}(R))={\sigma }_{c_2}({\sigma }_{c_1}(R))$
• Proyección:
  • Cascada: ${\pi }_{X_1}({\pi }_{X_2}(\dots ({\pi }_{X_n}(R))\dots ))={\pi }_{X_1}(R)$. Siempre y cuando las proyecciones sean subconjuntos de sus proyecciones siguientes.
  • Conmutatividad con $\sigma$: ${\pi }_X({\sigma }_c(R))={\sigma }_c({\pi }_X(R))$. Siempre y cuando entre los atributos que proyecto se mantengan los atributos sobre los cuales condiciono.
• Producto Cartesiano y Junta:
  • Conmutatividad:
    • $R\times S=S\times R$
    • $R\ast S=S\ast R$
  • Asociatividad:
    • $(R\times S)\times T=R\times (S\times T)$
    • $(R\ast S)\ast T=R\ast (S\ast T)$
• Operaciones de Conjuntos:
  • Conmutatividad:
    • $R\cup S=S\cup R$
    • $R\cap S=S\cap R$
  • Asociatividad:
    • $(R\cup S)\cup T=R\cup (S\cup T)$
    • $(R\cap S)\cap T=R\cap (S\cap T)$
• Mixtas:
  • Distribución de la selección en la junta: ${\sigma }_c(R\ast S)={\sigma }_{C_r}(R)\ast {\sigma }_{C_s}(S)\ast$. Solo si $c$ puede escribirse como $c_R\wedge c_S$. Donde involucran solo y respectivamente atributos de $R$ y $S$.
  • Distribución de la proyección en la junta: ${\pi }_X(R\ast S)={\pi }_{X_R}(R)\ast {\pi }_{X_S}(S)$. Solo si todos los atributos de junta están incluidos en $X$. Entonces llamaremos $X_R,X_S$ a los atributos de $R,S$ respectivamente.

Heurísticas de Optimización

La aplicación de las reglas de equivalencia a una expresión algebraica para obtener otra de menor costo se conoce como optimización algebraica.

Las siguientes son algunas reglas generales utilizadas para optimizar algebraicamente una consulta:

• Realizar las selecciones lo más temprano posible
• Reemplazar productos cartesianos por juntas siempre que sea posible
• Proyectar para descartar los atributos no utilizados lo antes posible. Entre la selección y la proyección, priorizar la selección.
• En caso de que haya varias juntas, realizar aquella más restrictiva primero. Se puede optar por árboles left-deep o right-deep para acotar las posibilidades.