====== Examen Final - 75.15. Base de Datos - 12/08/2009 ======

**Cátedra:** Ale (catedra unica)\\ 
**Fecha:** 2° Oportunidad - (2° Cuatrimestre) 2008\\ 
**Día:** 19/08/2009

<note important>
Esta página está incompleta; podés ayudar completando el material.
</note>

===== Enunciado =====
==== Ejercicio I ====

Sea <tex>R=(A,B,C,D,E,I)</tex> y <tex>M=\{A \rightarrow \rightarrow BCD, B \rightarrow AC, C \rightarrow D \}</tex>. \\
Esta en 4FN?. Justifique su respuesta. Si la respuesta es NO, normalizar R a 4FN.

==== Ejercicio II ====
Estimar el tamaño de la junta <tex>R(A,B) |x| S(B,C)</tex> usando histogramas para R.B y S.B. Asumir <tex>V(B,R)=20, V(B,S)=21</tex> y los siguientes histogramas, donde se dan las frecuencias para los 4 valores más comunes. \\
^    ^  0  ^  1  ^  2  ^  3  ^  4  ^  otros  ^
^  RB  |  5  |  6  |  4  |  5  |    |  32  |
^  SB  |  10  |  8  |  5  |    |  7  |  51  |

==== Ejercicio III ====

Dada la siguiente consulta sobre la tabla <tex>R(A,B,C,D)</tex>:

    SELECT [...]
    FROM R
    GROUP BY A,B

Asumir que ABCD toman valores enteros. \\
Cual de las siguientes puede aparecer en la posición marcada como [...]
  - <tex>Min(C+D)</tex>
  - <tex>A,B</tex>
  - <tex>C,D</tex>

  - 2 solamente.
  - 1 y 2 solamente.
  - 1, 2 y 3.
  - Ninguna de las anteriores.

==== Ejercicio IV ====

La siguiente es una secuencia de registros de un log **redo** grabado para las transacciones //T, U y V.// \\

    (T, START); (T,A,10); (U, START); (U,B,20); (T,C,30); (START CKPT [T, U]); (U,D,40);
    (U, Commit); (T,E,50); (V, START); (V,C,45); (END CKPT); (V, Commit); (T,D,45)

Describir brevemente las acciones del recovery manager (**cambios a disco solamente**), si el sistema bootea después de una caída y descubre este log.

===== Respuesta =====
==== Ejercicio I ====

<!--
Sea <tex>R=(A,B,C,D,E,I)</tex> y <tex>M=\{A \rightarrow \rightarrow BCD, B \rightarrow AC, C \rightarrow D \}</tex>. \\
Esta en 4FN?. Justifique su respuesta. Si la respuesta es NO, normalizar R a 4FN.
-->

R esta en 4FN si: \\
<tex>\left. \begin{array}{ll} 
\forall X \rightarrow \rightarrow Y \\
Y \notin X \\
XY \not= R \\
\end{array} \right\} \Longrightarrow X \in Superclave</tex>

Lo primero que tenemos que buscar es la clave de R, y encontramos que es <tex>BEI</tex>, ya que <tex>BEI^+ = ABCDEI</tex> \\
Ahora, haciendo uso del cuarto axioma y reglas de inferencia para dependencias multivaluadas que dice: <tex>X \rightarrow Y \Longrightarrow X \rightarrow \rightarrow Y</tex>, por lo que nos quedaría <tex>M'=\{A \rightarrow \rightarrow BCD, B \rightarrow \rightarrow AC, C \rightarrow \rightarrow D \}</tex>. \\
Vemos que ninguna de las dependencias multivaluadas cumple las restricciones de 4FN, por lo que tenemos que dividirlo usando el algoritmo 8 del libro (pag 133) nos queda en 4FN.

==== Ejercicio II ====
<!--
Estimar el tamaño de la junta <tex>R(A,B) |x| S(B,C)</tex> usando histogramas para R.B y S.B. Asumir <tex>V(B,S)=20, V(B,S)=21</tex> y los siguientes histogramas, donde se dan las frecuencias para los 4 valores más comunes. \\
^    ^  0  ^  1  ^  2  ^  3  ^  4  ^  otros  ^
^  RB  |  5  |  6  |  4  |  5  |    |  32  |
^  SB  |  10  |  8  |  5  |    |  7  |  51  |
-->

Primero tenemos que estimar los números que faltan:
  - <tex>RB(4) = \frac{otros}{V(B,R) - ValoresDefinidos} = \frac{32}{20-4} = 2</tex>
  - <tex>SB(3) = \frac{otros}{V(B,S) - ValoresDefinidos} = \frac{51}{21-4} = 3</tex>
Por lo que ahora la tabla nos queda:
^    ^  0  ^  1  ^  2  ^  3  ^  4  ^  otros  ^
^  RB  |   5  |  6  |  4  |  5  |  2  |  32  |
^  SB  |  10  |  8  |  5  |  3  |  7  |  51  |

Para 0: <tex>5*10 = 50</tex> \\
Para 1: <tex>6*8 = 48</tex> \\
Para 2: <tex>4*5 = 20</tex> \\
Para 3: <tex>5*3 = 15</tex> \\
Para 4: <tex>2*7 = 14</tex> \\
Para otros: Primero tengo que calcular la cantidad de valores que tengo que juntar: <tex>cant = Min[V(B,R)-ValoresDefinidosDeR; V(B,S)-ValoresDefinidosDeS] </tex>. Y ahora con ese valor: <tex> cant*avg(otros,R)*avg(otros,S)</tex><tex> = 15*\frac{32}{16}*\frac{51}{17} = 90</tex> \\
Por lo que el resultado me queda como la suma de cada valor: <tex>50 + 48 + 20 + 15 + 14 + 90 = 237 tuplas</tex>


==== Ejercicio III ====

<!--
Dada la siguiente consulta sobre la tabla <tex>R(A,B,C,D)</tex>:

    SELECT [...]
    FROM R
    GROUP BY A,B

Asumir que ABCD toman valores enteros. \\
Cual de las siguientes puede aparecer en la posición marcada como [...]
  - <tex>Min(C+D)</tex>
  - <tex>A,B</tex>
  - <tex>C,D</tex>

  - 2 solamente.
  - 1 y 2 solamente.
  - 1, 2 y 3.
  - Ninguna de las anteriores.
-->

La respuesta correcta es la 2, es decir, solamente <tex>A,B</tex>, ya que para el resto de las opciones tendríamos varios resultados
??Discusión: para mi son validas las 3, pueden aparecer todas; el problema es que si ponés la 1 y la 3, no se van a agrupar



==== Ejercicio IV ====

<!--
La siguiente es una secuencia de registros de un log **redo** grabado para las transacciones //T, U y V.// \\

    (T, START); (T,A,10); (U, START); (U,B,20); (T,C,30); (START CKPT [T, U]); (U,D,40);
    (U, Commit); (T,E,50); (V, START); (V,C,45); (END CKPT); (V, Commit); (T,D,45)

Describir brevemente las acciones del recovery manager (**cambios a disco solamente**), si el sistema bootea después de una caída y descubre este log.
-->
U=40
T=50
V=45
Flush