Bases de Datos
Práctico 6: Optimización en el Plan Lógico de Consultas

G. Saiz - N. Wolovick

  1. Para las siguientes relaciones

    \begin{eqnarray*}
r(AB) & = & \{ (0,1), (2,3), (0,1), (2,4), (3,4) \} \\
s(AB) & = & \{ (0,1), (2,4), (2,5), (3,4), (0,2), (3,4) \}
\end{eqnarray*}



    computar
    1. $r \cap_{B} s$
    2. $r -_{B} s$
    3. $\Pi_{a+b,b^{2}}(r)$
    4. $r \Join_{R.b<S.b} s$
    5. $\gamma_{a,SUM(b)}(r)$
    6. $\delta(r)$
    7. $\tau_{b,a}(r)$

    Operadores Join-Like

    Existen varios operadores del estilo del join que son provistos por bases de datos comerciales.

  2. Dar expresiones para los cinco operadores definidos en el párrafo anterior usando solamente los operadores standard del álgebra relacional. Para las variantes ``outerjoin'' puede usar una relación nula $n(A_{1}, \ldots, A_{i})$ que consiste de una única tupla con $\bot$ en cada componente.

  3. Un operador unario $f$ es idempotente si, $\forall r f^{2}(r)=f(r)$. Para cada uno de los operadores $\delta, \Pi_{L}, \sigma_{C},$ $\gamma_{L}, \tau$, explique por que son idempotentes o muestre un contraejemplo.

  4. Cuando es posible empujar una selección en los dos argumentos de un operador binario, es necesario decidir si hacerlo o no. ¿Cómo afectaría la existencia de índices en uno de los argumentos?. Considere, por ejemplo, una expresión $\sigma_{C}(r \cap s)$, donde se tiene un índice sobre $s$.

  5. Dar ejemplos donde se muestre que la eliminación de duplicados no puede ser empujada por debajo de la unión o diferencia de multiconjuntos.

  6. Los operadores similares al join del ejercicio 2 obedecen algunas reglas comunes y otras no. Para cada caso pruebe o de un contraejemplo para las siguientes leyes.

  7. Reemplace los join naturales en las expresiones siguientes por theta-joins y proyecciones. Diga cuando los theta-join resultantes forman un grupo asociativo y conmutativo.
    1. $(r(AB) \Join s(BC)) \Join_{S.c>T.c} t(CD)$
    2. $(r(AB) \Join s(BC)) \Join (t(CD) \Join u(DE))$
    3. $(r(AB) \Join s(BC)) \Join (t(CD) \Join u(AD))$

  8. Dar reglas para convertir cada una de las siguientes formas de condición en álgebra relacional. Asuma que las condiciones se aplican a una relación $r(R)$ y no están correlacionadas a ella. Tenga especial cuidado para no introducir o eliminar duplicados respecto a la definicion formal de SQL.

  9. Transforme la siguiente query en un plan lógico y trate de mejorarlo aplicando leyes algebraicas.
    
    	SELECT starName
    	FROM Actor1996
    	WHERE studioName="Paramount";
    
    donde hay dos vistas definidas
    
    	CREATE VIEW Actor1996 AS
    		SELECT starName, studioName
    		FROM MoviesOf1996 NATURAL JOIN starsIn;
    
    CREATE VIEW MovieOf1996 AS SELECT * FROM Movie WHERE year=1996;
    y los esquemas son

    Movie(title,year,length,inColor,studioName,producerC#)
    StarsIn(title,year,starName)



bdd@hal.famaf.unc.edu.ar