Bases de Datos
Práctico 4: Dependencias Funcionales y Cubrimientos

G. Saiz - N. Wolovick

1. Probar, sin utilizar los aximas de Amstrong, las reglas de inferencia adicionales sobre dependencias funcionales:
   1. Unión.
   2. Descomposición.
   3. Pseudotransitividad.

2. Dado el siguiente conjunto de dependencias funcionales
   
   $$F=\{A \rightarrow DC, BC \rightarrow F, F \rightarrow CH, AF \rightarrow B\}$$
   
   
   encontrar, si es posible, una secuencia de derivación aplicando los axiomas de Amstrong para las siguientes dependencias:
   1. $AC \rightarrow H$
   2. $BA \rightarrow FC$
   3. $AF \rightarrow HB$
   4. $A \rightarrow F$

3. Pruebe o niegue con un contraejemplo que las siguientes reglas de inferencia son válidas para una relación $r(R)$, con $W,X,Y,Z \subseteq R$.
   1. $\frac{X \rightarrow Y , Z \rightarrow W}{XZ \rightarrow YW}$
   2. $\frac{XY \rightarrow Z , Z \rightarrow X}{Z \rightarrow Y}$
   3. $\frac{X \rightarrow Y , Y \rightarrow Z}{X \rightarrow YZ}$
   4. $\frac{X \rightarrow Y , W \rightarrow Z, W\subseteq Y}{X \rightarrow Z}$
   5. $\frac{X \rightarrow YZ}{X \rightarrow Y}$

4. Sea $r(R)$ una relación. Probar que $r$ satisface $X \rightarrow Y$ sii $X$ es una clave de $\Pi_{XY}(r)$.

5. Probar que los axiomas de Amstrong son independientes, es decir, no hay un subconjunto propio del cual se puedan probar los restantes.

6. Sea $r(R)$ una relación. Probar que si $\Pi_{X}(r)$ tiene la misma cantidad de tuplas que $r$, entonces $r$ satisface $X \rightarrow Y$ para todo $Y$ incluido en $R$.

7. Sea $R$ un esquema de relación y $F$ un conjunto de dependencias funcionales. Dar una cota del número de dependencias funcionales en $F^{+}$ en base al número de atributos de $R$.

8. Dados los siguientes conjuntos de dependencias funcionales $F$ y $G$, decidir si son equivalentes.
   $$\begin{eqnarray*} F &=& \{ AC \rightarrow B, BC \rightarrow DE, DC \rightarrow ... ...rrow BE, BC \rightarrow D, DC \rightarrow B, BC \rightarrow A\} \end{eqnarray*}$$
   
   
   
   
   

9. Encuentre un cubrimiento no redundante para
   
   $$F=\{A \rightarrow CD, A \rightarrow E, E \rightarrow CG, A \rightarrow G, E \rightarrow A, E \rightarrow D\}$$
   
   

10. Dado
    
    $$F=\{A \rightarrow BC, B \rightarrow A, BD \rightarrow I, AD \rightarrow E, BDA \rightarrow E\}$$
    
    
    1. Encuentre un conjunto de dependencias equivalente no redundate y reducido.
    2. ¿Es $F$ minimal? Si no lo es, encuentre un minimal equivalente.

11. ¿Es correcto el siguiente algoritmo?
    
    

12. Para los siguientes conjuntos de dependencias funcionales, encuentre un conjunto equivalente minimal reducido y un cubrimiento canónico.
    $$\begin{eqnarray*} F_{1} &=& \{ A \rightarrow C, AB \rightarrow DE, AB \rightarr... ...ow CF, B \rightarrow CA, CF \rightarrow B, CBF \rightarrow DH\} \end{eqnarray*}$$
    
    
    
    
    

13. Dar conjuntos de dependencias funcionales que cumplan:
    1. No redundate, pero que no sea reducido.
    2. No redundante, pero no mínimo.
    3. Reducido no mínimo.
    4. Mínimo pero no reducido.
    5. Mínimo y reducido, pero hay algún cubrimiento equivalente que usa menor cantidad de símbolos.