Capitulo 5 – Teoria de las Dependencias Funcionales

Repaso de la teoría

Vamos a repasar los puntos principales de la teoría de dependencias funcionales.

Dependencia funcional

Una dependencia funcional es una restricción sobre el conjunto de tuplas que pueden aparecer en una relación [1].

En un esquema de relación R, X e Y son subconjuntos de R. La dependencia funcional X→Y (“X determina Y”) se verifica en R si en ninguna instancia aceptable de R pueden existir 2 tuplas t1 y t2 tales que:

t1[X]=t2[X]
t1[Y]<>t2[Y]

O sea, dos tuplas con los mismos valores en las columnas X tienen necesariamente que tener los mismos valores de las columnas Y.

Superclave

Una superclave del esquema R es aquella donde X→R, o sea, los datos de la columnas X determinan el contenido de las demás columnas.

Clave

Dado un esquema R y un conjunto de dependencias funcionales F asociado, se dice que X→R es clave si se cumplen las siguientes 2 condiciones:

  1. F implica X→A1, A2, …, An, o sea X→R
  2. No existe ningún Z⊆X tal que F implica Z→R (condición de minimalidad).

Esto quiere decir que la clave de un esquema es aquella cuyos atributos determinan el valor del resto de los atributos, y ese conjunto de atributos es mínimo. La diferencia entre una superclave y una clave, es que la clave es mínima en cantidad de atributos, mientras que la superclave podría tener atributos que determinan a los otros pero podrían obviarse, ya que los atributos determinados por estos ya están determinados por otros atributos.

Axiomas de Armstrong

  1. Reflexividad. Si Y⊆X, inferir X→Y.
  2. Aumento. Para cualquier conjunto W, de X→Y inferir XW→YW.
  3. Transitividad. De X→Y y Y→Z, inferir X→Z.

Reglas de inferencia adicionales

Estas reglas pueden deducirse de las anteriores, pero son útiles en algunos casos.

  1. Unión. De X→Y y X→Z, inferir X→YZ.
  2. Pseudotransitividad. Para cualquier W, de X→Y y YW→Z, inferir XW→Z.
  3. Descomposición. De X→YZ, inferir X→Y y X→Z.

Clausura de un conjunto de atributos

Dado un esquema de relación R, un conjunto de dependencias funcionales F, y un conjunto de atributos X incluidos en R, se define clausura de X con respecto a F , como el conjunto de todos los atributos A perteneciente a R tal que X→A puede ser derivado de F usando los axiomas de Armstrong y las reglas adicionales de todas las formas posibles.

Listado de ejercicios

  1. (resuelto) Dado R(H,I,K,L,M,O) y el conjunto de dependencias funcionales F={H→IO, O→HO, KM→L,
    L→MK, M→K, HK→M}, hallar todas las claves candidatas.Ver solución
  2. (resuelto) Dado R(A,B,C,D,E) y el siguiente conjunto de dfs F={A → BC, CD → E, B →D, E→A},
    probar utilizando los axiomas que las siguientes dependencias pertenecen a F+:

     

    1. E → B
    2. EA → CA
    3. AD → E
    4. AC → E

    Ver solución

  3. (resuelto) Probar el axioma de transitividad mediante la definiciónn de dependencia funcional.

    Ver solución

  4. (resuelto) Probar utilizando los axiomas para dependencias funcionales las siguientes reglas:
      • De X→Y, X⊆V, YZ inferir V→Z

     

      • De X→Y, W⊆Y, W→Z, inferir X→Z

     

      • De X→Y, X⊆V, W⊆Y, W→Z inferir V→Z

     

    Ver solución

  5. (resuelto) Dado R(A,B,C,D,E,F,G) y el siguiente conjunto de dependencias funcionales:
    F={AB→C, C→A, BC→D, ACD→B, D→EG, BE→C, CG→BD,
    CE→AG}, hallar un cubrimiento minimal FM.Ver solución
  6. (resuelto) Sea R un esquema relacional, F un conjunto de dependencias funcionales y FM
    un cubrimiento minimal de F.
    Probar que:

     

    1. Si X→A ∈ FM, X⊆R, A∈R, no puede ser X
      superclave de R sin ser, a su vez, clave de dicho esquema.
    2. Si X→A ∈F, X⊆R, A∈R, y F|=X1→
      X2, con X1⊂X, X2⊂X, X2
      ⊄X1, entonces X→A ∉FM
  7. (resuelto) Dado el esquema de relación R(A,B,C,D,E) y las siguientes instancias:
    A B C D E   A B C D E   A B C D E
    a1 b1 c1

     

    		 d1 e1   a1 b2 c1 d2 e1   a1 b1 c2 d2 e2
    a1 b2 c2 d1 e1   a2 b2 c1 d2 e2   a2 b1 c2 d2 e2
    a2 b1 c2 d1 e1   a2 b2 c2 d2 e2   a1 b2 c1 d1 e1
    1. Analizar si cada instancia cumple con las siguientes dependencias:

       

      1. A→BC
      2. D→E
      3. BC→D
    2. Analizar para cada caso las anomal&
      iacute;as existentes en R tomando como
      conjunto de dependencias al formado por las dependencias de i a iii que se hayan verificado sobre la instancia.
  1. Dado R(H,I,K,L,M,O) y el conjunto de dependencias funcionales F={H→IO, O→HO, KM→L,
    L→MK, M→K, HK→M}, hallar todas las claves candidatas.

     

    Solución. Recordemos que una clave candidata es el conjunto de atributos tales que la clausura de este es igual a toda la relación, o sea, con todas las dependencias funcionales, es posible escoger un conjunto desde el cual se deriven todos los atributos, y además este conjunto debe ser mínimo.

    Primero de todo tratamos de descomponer algunas de las dependencias funcionales, empezando la búsqueda de un “cubrimiento minimal” de dependencias. H→IO se convierte en H→I y H→O, O→HO se convierte en O→H (la relación O→
    O es ” obvia” ya que es uno de los axiomas de Armstrong).

    Para encontrar las claves candidatas, tenemos que calcular la clausura del conjunto de atributos que escojamos, y esa clausura tiene que abarcar a todos los atributos de la relación. La clausura del conjunto de atributos son los atributos que se pueden deducir utilizando el conjunto de dependencias funcionales. Pero que la clausura sea todos los atributos es solamente uno de los requisitos. El otro, es que el conjunto de atibutos que se toma tiene que ser mínimo. Empezamos entonces con {H} para empezar a buscar conjuntos de atributos que sean claves candidatas. Vemos que solamente con H no alcanza para encontrar todos los atributos de la relación. Entonces tomamos {HI}, pero con eso tampoco alcanza. {HK} ya tiene mejor pinta: calculamos la clausura.

    1. Buscamos dependencias que en el lado izquierdo tengan atributos de nuestro conjunto y del derecho tengan nuevos atributos: p/ej. H→O.
      Agregamos los nuevos atributos al conjunto y queda {HKO}.
    2. HK→M: {HKMO}.
    3. KM→L: {HKLMO}
    4. H→I: {HIKLMO}. Logramos deducir todos los atributos de la relación, luego {HK} es clave candidata.

    Comienzo de vuelta con otro conjunto: {HL}. Se observa que no alcanza porque no hay dependencias funcionales que tengan esos atributos a la izquierda.

    Otro conjunto: {HM}.

    1. M→K: {HKM}.
    2. KM→L: {HKLM}.
    3. H→I: {HIKLM}.
    4. H→O: {HIKLMO}. Logré deducir todos los atributos, luego {HM} es clave candidata.

    Partimos de otro conjunto: {HO}. Con ese conjunto de atributos no alcanza, vemos que no hay ninguna dependencia que nos permita deducir más atributos.

    Tomamos otro conjunto: {I}. Pero vemos que no alcanza para deducir nada. Creo que no vale la pena probar conjuntos que incluyan a I, ya que I se puede deducir de otro atributo, me parece
    que si logramos encontrar un conjunto de atributos que logre tener una clausura igual a todos los atributos de la relación, este conjunto no va a ser mínimo y por lo tanto no sería clave candidata.

    Probamos {L}. Vemos que no alcanza porque aunque se pueden obtener K y M, la H, I y O están fuera de nuestro alcance. Probemos {LO}:

    1. O→H: {HLO}
    2. H→I: {HILO}
    3. L→M: {HILMO}
    4. L→K: {HIKLMO}. Logramos deducir todos los atributos, luego es clave candidata.

    Probemos otro conjunto de atributos: {LM}. No alcanza. {LK} tampoco alncanza. {LI} tampoco. Faltan unas pocas combinaciones para probar, como por ejemplo {KO}:

    1. O→H: {HKO}
    2. H→I: {HIKO}
    3. HK→M: {HIKMO}
    4. KM→L: {HIKLMO}. Logramos deducir todos los atributos, luego es clave candidata.

    Falta que probemos {MO}:

    1. O→H: {HMO}.
    2. H→I: {HIMO}.
    3. M→K: {HIKMO}.
    4. KM→L: {HIKLMO}. Logramos deducir todos los atributos, luego es clave candidata.

    Faltaría empezar a buscar combinaciones de 3 atributos, pero me parece que no vale la pena porque todas las combinaciones de 2 atributos ya están tomadas, y cualquier conjunto de 3 va a incluir alguno de los pares que ya probamos, por lo tanto ya sería una superclave y no una clave candidata.

    Como conclusión, las claves candidatas que encontramos son: {HK}, {HM}, {KO}, {LO}, {MO}

  2. Dado R(A,B,C,D,E) y el siguiente conjunto de dfs F={A → BC, CD → E, B →D, E→A}, probar utilizando los axiomas que las siguientes dependencias pertenecen a F+:
    1. E → B
    2. EA → CA
    3. AD → E
    4. AC → E

    Solución. Aquí piden decir si las dependencias que se muestran pertenecen al conjunto F+, o sea, a la clausura del conjunto de dependencias, formado por todas las dependencias que se pueden formar con las dependencias de F aplicando sobre ellas los axiomas de Armstrong.

    Pasamos a demostrar entonces las dependencias:

    1. E→B:

       

        • E→A (dada)
        • E→BC (transitividad entre A→BC y E→A)
        • E→B (descomposición de E→BC en E→B y E→C)

       

    2. EA→CA:
        • A→BC (dada)
        • A→C (descomposición de A→BC en A→B y A→C)
        • E→C (transitividad entre E→A y A→C)
        • EA→CA (aumento entre E→C y A)

       

    3. AD→E:
        • A→BC (dada)
        • A→C (descomposición de A→BC en A→B y A→C)
        • AD→CD (aumento entre A→C y D)
        • CD→E (dada)
        • AD→E (transitividad entre AD→CD y CD→E)

       

    4. AC→E:
        • A→BC (dada)
        • A→B (descomposición de A→BC en A→B y A→C)
        • B→D (dada)
        • A→D (transitividad entre A→B y B→D)
        • AC→CD (aumento entre A→D y C)
        • CD→E (dada)
        • AC→E (transitividad entre AC→CD y CD→E)

       

  3. Probar el axioma de transitividad mediante la definición de dependencia funcional.

    Solución. Un ejercicio de lógica bastante inusual, pero no imposible, ya que después de todo la
    teoría del modelo relacional encuentra sus bases en la lógica de predicados y la teoría de conjuntos.

    Recordemos el axioma de transitividad: Si A→B y B→C, entonces A→C. Recordemos también la definición de dependencia funcional, que dice que si A→B, entonces en ninguna tupla aceptable de R(A,B) pueden existir dos tuplas t1 y t2 tales que t1[A] = t2[A] y t1[B] ≠ t2[B]. Ya que estamos hablando de lógica, pasemos esa afirmación a lógica de primer orden:

    Si A→B entonces ∀ t1,t2:
    t1[A] = t2[A] ?
    t1[B] = t2[B].

    Para demostrar el axioma de la transitividad, propongo negar su
    conclusión y derivar
    de ello una contradicción con nuestra hipótesis, la definición de dependencia
    funcional.

    Entonces negamos que A→C. Esto es plantear, en lógica de primer orden:

    ∃ t1, t2: t1[A] = t2[A] ? t1[C] ≠ t2[C].

    Ahora bien: por hipótesis sabemos que:

    ∀ t1,t2:
    t1[A] = t2[A] ?
    t1[B] = t2[B]

    ∀ t1,t2:
    t1[B] = t2[B] ?
    t1[C] = t2[C]

    Por transitividad de lógica proposicional, se
    deduce que:

    ∀ t1,t2:
    t1[A] = t2[A] ?
    t1[C] = t2[C]

    Esto es una contradicción con nuestro planteo de negar A→C. Por lo tanto ese planteo tiene que estar mal, y por lo tanto, el axioma de transitividad es verdadero.

  4. Probar utilizando los axiomas para dependencias funcionales las siguientes reglas:
      • De X→Y, X⊆V, YZ inferir V→Z

     

      • De X→Y, W⊆Y, W→Z, inferir X→Z

     

      • De X→Y, X⊆V, W⊆Y, W→Z inferir V→Z

     

     

      1. Solución. Otra vez vamos a usar la lógica para demostrar esto.

         

        n Para empezar, X⊆V quiere decir que V→X, y YZ→Z. Esas dependencias funcionales
        están ocultas en los datos. Ahora, empezamos a hacer la demostración mediante
        axiomas:
        X→Y (dada)
        V→X (reflexividad de X⊆V)
        V→Y (transitividad entre X→Y y V→X)
        VZ→YZ (aumento de V→Y con Z)

         

     

      1. Aquí también tenemos que extraer las dependencias implícitas en
        las relaciones entre conjuntos que nos están dando. W⊆Y implica que
        Y→W. Con eso demostramos:
        X→Y (dada)
        Y→W (reflexividad de W⊆Y)
        W→Z (dada)
        Y→Z (transitividad entre Y→W y W→Z)
        X→Z (transitividad entre Y→Z y X→Z)

     

      1. Este es más de lo mismo:
        X→Y (dada)
        V→X (
        reflexividad de X⊆V)
        Y→W (reflexividad de W⊆Y)
        W→Z (dada)
        Y→Z (transitividad de Y→W y W→Z)
        X→Z (transitividad entre Y→Z y X→Y)
        V→Z (transitividad entre X→Z y V→X)

     

  5. Dado R(A,B,C,D,E,F,G) y el siguiente conjunto de dependencias funcionales:
    F={AB→C, C→A, BC→D, ACD→B, D→EG, BE→C, CG→BD,
    CE→AG}, hallar un cubrimiento minimal FM.

     

    Solución. Para encontrar el cubrimiento minimal, tenemos que hacer 3 cosas:

    • Simplificar todas las dependencias funcionales de manera que a la derecha tengan solamente un elemento,
    • Simplificar todas las dependencias funcionales de manera que a la izquierda tengan la menor cantidad posible de elementos,
    • Averiguar si alguna de las dependencias es superflua.

    El cubrimiento
    minimal es un conjunto cuya clausura abarca la misma cantidad de atributos que el conjunto original. El primer paso de la lista lo podemos hacer aplicando la descomposición de los axiomas de Armstrong. Los otros dos requieren que calculemos la clausura del conjunto de atributos.

    Empecemos entonces por reducir la cantidad de atributos a la derecha en cada DF:

    • D→EG se convierte en D→E y D→G
    • CG→BD se convierte en CG→B y CG→D
    • CE→AG se convierte en CE→A y CE→G

    Ahora, seguimos por eliminar los atributos innecesarios en el lado izquierdo de las reglas. Por ejemplo, vemos que tenemos la dependencia C→A y CE→A. Observo que puedo construir la segunda regla con aumento y descomposición y por lo tanto es totalmente superflua. La elimino directamente.

  6. Sea R un esquema relacional, F un conjunto de dependencias funcionales y FM
    un cubrimiento minimal de F. Probar que:

     

    1. Si X→A ∈ FM, X⊆R, A∈R, no puede ser X
      superclave de R sin ser, a su vez, clave de dicho esquema.
    2. Si X→A ∈F, X⊆R, A∈R, y F|=X1→
      X2, con X1⊂X, X2⊂X, X2
      ⊄X1, entonces X→A ∉FM

    1. Solución. Empiezo con suponer que X es superclave y no clave. X superclave, quiere decir que todos los
      atributos de la relación pertenecen a la clausura de X, y si no es clave, entonces se viola la condición de que X no debe tener atributos redundantes. Dicho de otra manera, existe un subconjunto de X,
      digamos Z, cuya clausura es igual a todos los atributos de la relación.

      Pero X→A ∈ FM, luego, ∀ X→A ∈ FM,
      -∃ Z ∈ X tal que FM-{X→A} U {Z→A} ≡ FM*. O sea, si FM es el cubrimiento minimal entonces para cada una de las dependencias funcionales que pertenecen a él, no existe ningún subconjunto de atributos de X que sirvan para derivar A. Por lo tanto, al obligar que X no tenga ningún subconjunto que permita que se deriven atributos de él, estoy obligando que sea clave, pero yo había empezado diciendo que X era clave. Luego estoy en un absurdo que vino de suponer que X es superclave y no clave del esquema R, por lo tanto X no puede ser superclave sin ser clave del esquema R.

    2. Solución. ¿Qué
      quieren decir todos esos símbolos raros? Quiere decir que en X hay 2 conjuntos, X1 y X2, en donde uno se deriva a partir del otro. O sea, X1→X2. Consideremos la regla de Armstrong de pseudotransitividad. De X→Y e YW→Z, inferir XW→Z. ¿Qué tal si en esa regla sustituimos X por X1, Y por X2, W por X1 y Z por A? Entonces nos queda que de X1 →X2 y X2X1→A (esto es la definición de X→A), podemos deducir X1X1→A. Por lo tanto A se puede deducir solamente de una parte de X. Por lo tanto X→A no está en el conjunto minimal.

  7. Dado el esquema de relación R(A,B,C,D,E)
    y las siguientes instancias:

     

    A B C D E   A B C D E   A B C D E
    a1 b1 c1 d1 e1   a1 b2 c1 d2 e1   a1 b1 c2 d2 e2
    a1 b2 c2 d1 e1  

     

    		 a2 b2 c1 d2 e2   a2 b1 c2 d2 e2
    a2 b1 c2 d1 e1   a2 b2 c2 d2 e2   a1 b2 c1 d1 e1
    1. Analizar si cada instancia cumple con las siguientes dependencias:

       

      1. A→BC
      2. D→E
      3. BC→D
    2. Analizar para cada caso las anomalías existentes en R tomando como conjunto de dependencias al formado por las dependencias de i a iii que se hayan verificado sobre la instancia.

Listado de ejercicios

  1. (resuelto) Dado R(H,I,K,L,M,O) y el conjunto de dependencias funcionales F={H→IO, O→HO, KM→L,
    L→MK, M→K, HK→M}, hallar todas las claves candidatas.Ver solución
  2. (resuelto) Dado R(A,B,C,D,E) y el siguiente conjunto de dfs F={A → BC, CD → E, B →D, E→A},
    probar utilizando los axiomas que las siguientes dependencias pertenecen a F+:

    1. E → B
    2. EA → CA
    3. AD → E
    4. AC → E

    Ver solución

  3. (resuelto) Probar el axioma de transitividad mediante la definiciónn de dependencia funcional.

    Ver solución

  4. (resuelto) Probar utilizando los axiomas para dependencias funcionales las siguientes reglas:
    • De X→Y, X⊆V, YZ inferir V→Z
    • De X→Y, W⊆Y, W→Z, inferir X→Z
    • De X→Y, X⊆V, W⊆Y, W→Z inferir V→Z

    Ver solución

  5. (resuelto) Dado R(A,B,C,D,E,F,G) y el siguiente conjunto de dependencias funcionales:
    F={AB→C, C→A, BC→D, ACD→B, D→EG, BE→C, CG→BD,
    CE→AG}, hallar un cubrimiento minimal FM.Ver solución
  6. (resuelto) Sea R un esquema relacional, F un conjunto de dependencias funcionales y FM
    un cubrimiento minimal de F.
    Probar que:

    1. Si X→A ∈ FM, X⊆R, A∈R, no puede ser X
      superclave de R sin ser, a su vez, clave de dicho esquema.
    2. Si X→A ∈F, X⊆R, A∈R, y F|=X1→
      X2, con X1⊂X, X2⊂X, X2
      ⊄X1, entonces X→A ∉FM
  7. (resuelto) Dado el esquema de relación R(A,B,C,D,E) y las siguientes instancias:
    A B C D E   A B C D E   A B C D E
    a1 b1 c1

    		d1 e1   a1 b2 c1 d2 e1   a1 b1 c2 d2 e2
    a1 b2 c2 d1 e1   a2 b2 c1 d2 e2   a2 b1 c2 d2 e2
    a2 b1 c2 d1 e1   a2 b2 c2 d2 e2   a1 b2 c1 d1 e1
    1. Analizar si cada instancia cumple con las siguientes dependencias:
      1. A→BC
      2. D→E
      3. BC→D
    2. Analizar para cada caso las anomal&
      iacute;as existentes en R tomando como
      conjunto de dependencias al formado por las dependencias de i a iii que se hayan verificado sobre la instancia.
  1. Dado R(H,I,K,L,M,O) y el conjunto de dependencias funcionales F={H→IO, O→HO, KM→L,
    L→MK, M→K, HK→M}, hallar todas las claves candidatas.

    Solución. Recordemos que una clave candidata es el conjunto de atributos tales que la clausura de este es igual a toda la relación, o sea, con todas las dependencias funcionales, es posible escoger un conjunto desde el cual se deriven todos los atributos, y además este conjunto debe ser mínimo.

    Primero de todo tratamos de descomponer algunas de las dependencias funcionales, empezando la búsqueda de un "cubrimiento minimal" de dependencias. H→IO se convierte en H→I y H→O, O→HO se convierte en O→H (la relación O→
    O es " obvia" ya que es uno de los axiomas de Armstrong).

    Para encontrar las claves candidatas, tenemos que calcular la clausura del conjunto de atributos que escojamos, y esa clausura tiene que abarcar a todos los atributos de la relación. La clausura del conjunto de atributos son los atributos que se pueden deducir utilizando el conjunto de dependencias funcionales. Pero que la clausura sea todos los atributos es solamente uno de los requisitos. El otro, es que el conjunto de atibutos que se toma tiene que ser mínimo. Empezamos entonces con {H} para empezar a buscar conjuntos de atributos que sean claves candidatas. Vemos que solamente con H no alcanza para encontrar todos los atributos de la relación. Entonces tomamos {HI}, pero con eso tampoco alcanza. {HK} ya tiene mejor pinta: calculamos la clausura.

    1. Buscamos dependencias que en el lado izquierdo tengan atributos de nuestro conjunto y del derecho tengan nuevos atributos: p/ej. H→O.
      Agregamos los nuevos atributos al conjunto y queda {HKO}.
    2. HK→M: {HKMO}.
    3. KM→L: {HKLMO}
    4. H→I: {HIKLMO}. Logramos deducir todos los atributos de la relación, luego {HK} es clave candidata.

    Comienzo de vuelta con otro conjunto: {HL}. Se observa que no alcanza porque no hay dependencias funcionales que tengan esos atributos a la izquierda.

    Otro conjunto: {HM}.

    1. M→K: {HKM}.
    2. KM→L: {HKLM}.
    3. H→I: {HIKLM}.
    4. H→O: {HIKLMO}. Logré deducir todos los atributos, luego {HM} es clave candidata.

    Partimos de otro conjunto: {HO}. Con ese conjunto de atributos no alcanza, vemos que no hay ninguna dependencia que nos permita deducir más atributos.

    Tomamos otro conjunto: {I}. Pero vemos que no alcanza para deducir nada. Creo que no vale la pena probar conjuntos que incluyan a I, ya que I se puede deducir de otro atributo, me parece
    que si logramos encontrar un conjunto de atributos que logre tener una clausura igual a todos los atributos de la relación, este conjunto no va a ser mínimo y por lo tanto no sería clave candidata.

    Probamos {L}. Vemos que no alcanza porque aunque se pueden obtener K y M, la H, I y O están fuera de nuestro alcance. Probemos {LO}:

    1. O→H: {HLO}
    2. H→I: {HILO}
    3. L→M: {HILMO}
    4. L→K: {HIKLMO}. Logramos deducir todos los atributos, luego es clave candidata.

    Probemos otro conjunto de atributos: {LM}. No alcanza. {LK} tampoco alncanza. {LI} tampoco. Faltan unas pocas combinaciones para probar, como por ejemplo {KO}:

    1. O→H: {HKO}
    2. H→I: {HIKO}
    3. HK→M: {HIKMO}
    4. KM→L: {HIKLMO}. Logramos deducir todos los atributos, luego es clave candidata.

    Falta que probemos {MO}:

    1. O→H: {HMO}.
    2. H→I: {HIMO}.
    3. M→K: {HIKMO}.
    4. KM→L: {HIKLMO}. Logramos deducir todos los atributos, luego es clave candidata.

    Faltaría empezar a buscar combinaciones de 3 atributos, pero me parece que no vale la pena porque todas las combinaciones de 2 atributos ya están tomadas, y cualquier conjunto de 3 va a incluir alguno de los pares que ya probamos, por lo tanto ya sería una superclave y no una clave candidata.

    Como conclusión, las claves candidatas que encontramos son: {HK}, {HM}, {KO}, {LO}, {MO}

  2. Dado R(A,B,C,D,E) y el siguiente conjunto de dfs F={A → BC, CD → E, B →D, E→A}, probar utilizando los axiomas que las siguientes dependencias pertenecen a F+:
    1. E → B
    2. EA → CA
    3. AD → E
    4. AC → E

    Solución. Aquí piden decir si las dependencias que se muestran pertenecen al conjunto F+, o sea, a la clausura del conjunto de dependencias, formado por todas las dependencias que se pueden formar con las dependencias de F aplicando sobre ellas los axiomas de Armstrong.

    Pasamos a demostrar entonces las dependencias:

    1. E→B:
      • E→A (dada)
      • E→BC (transitividad entre A→BC y E→A)
      • E→B (descomposición de E→BC en E→B y E→C)
    2. EA→CA:
      • A→BC (dada)
      • A→C (descomposición de A→BC en A→B y A→C)
      • E→C (transitividad entre E→A y A→C)
      • EA→CA (aumento entre E→C y A)
    3. AD→E:
      • A→BC (dada)
      • A→C (descomposición de A→BC en A→B y A→C)
      • AD→CD (aumento entre A→C y D)
      • CD→E (dada)
      • AD→E (transitividad entre AD→CD y CD→E)
    4. AC→E:
      • A→BC (dada)
      • A→B (descomposición de A→BC en A→B y A→C)
      • B→D (dada)
      • A→D (transitividad entre A→B y B→D)
      • AC→CD (aumento entre A→D y C)
      • CD→E (dada)
      • AC→E (transitividad entre AC→CD y CD→E)
  3. Probar el axioma de transitividad mediante la definición de dependencia funcional.

    Solución. Un ejercicio de lógica bastante inusual, pero no imposible, ya que después de todo la
    teoría del modelo relacional encuentra sus bases en la lógica de predicados y la teoría de conjuntos.

    Recordemos el axioma de transitividad: Si A→B y B→C, entonces A→C. Recordemos también la definición de dependencia funcional, que dice que si A→B, entonces en ninguna tupla aceptable de R(A,B) pueden existir dos tuplas t1 y t2 tales que t1[A] = t2[A] y t1[B] ≠ t2[B]. Ya que estamos hablando de lógica, pasemos esa afirmación a lógica de primer orden:

    Si A→B entonces ∀ t1,t2:
    t1[A] = t2[A] ⇒
    t1[B] = t2[B].

    Para demostrar el axioma de la transitividad, propongo negar su
    conclusión y derivar
    de ello una contradicción con nuestra hipótesis, la definición de dependencia
    funcional.

    Entonces negamos que A→C. Esto es plantear, en lógica de primer orden:

    ∃ t1, t2: t1[A] = t2[A] ∧ t1[C] ≠ t2[C].

    Ahora bien: por hipótesis sabemos que:

    ∀ t1,t2:
    t1[A] = t2[A] ⇒
    t1[B] = t2[B]

    ∀ t1,t2:
    t1[B] = t2[B] ⇒
    t1[C] = t2[C]

    Por transitividad de lógica proposicional, se
    deduce que:

    ∀ t1,t2:
    t1[A] = t2[A] ⇒
    t1[C] = t2[C]

    Esto es una contradicción con nuestro planteo de negar A→C. Por lo tanto ese planteo tiene que estar mal, y por lo tanto, el axioma de transitividad es verdadero.

  4. Probar utilizando los axiomas para dependencias funcionales las siguientes reglas:
    • De X→Y, X⊆V, YZ inferir V→Z
    • De X→Y, W⊆Y, W→Z, inferir X→Z
    • De X→Y, X⊆V, W⊆Y, W→Z inferir V→Z
    1. Solución. Otra vez vamos a usar la lógica para demostrar esto.

      n Para empezar, X⊆V quiere decir que V→X, y YZ→Z. Esas dependencias funcionales
      están ocultas en los datos. Ahora, empezamos a hacer la demostración mediante
      axiomas:
      X→Y (dada)
      V→X (reflexividad de X⊆V)
      V→Y (transitividad entre X→Y y V→X)
      VZ→YZ (aumento de V→Y con Z)

    2. Aquí también tenemos que extraer las dependencias implícitas en
      las relaciones entre conjuntos que nos están dando. W⊆Y implica que
      Y→W. Con eso demostramos:
      X→Y (dada)
      Y→W (reflexividad de W⊆Y)
      W→Z (dada)
      Y→Z (transitividad entre Y→W y W→Z)
      X→Z (transitividad entre Y→Z y X→Z)
    3. Este es más de lo mismo:
      X→Y (dada)
      V→X (
      reflexividad de X⊆V)
      Y→W (reflexividad de W⊆Y)
      W→Z (dada)
      Y→Z (transitividad de Y→W y W→Z)
      X→Z (transitividad entre Y→Z y X→Y)
      V→Z (transitividad entre X→Z y V→X)
  5. Dado R(A,B,C,D,E,F,G) y el siguiente conjunto de dependencias funcionales:
    F={AB→C, C→A, BC→D, ACD→B, D→EG, BE→C, CG→BD,
    CE→AG}, hallar un cubrimiento minimal FM.

    Solución. Para encontrar el cubrimiento minimal, tenemos que hacer 3 cosas:

    • Simplificar todas las dependencias funcionales de manera que a la derecha tengan solamente un elemento,
    • Simplificar todas las dependencias funcionales de manera que a la izquierda tengan la menor cantidad posible de elementos,
    • Averiguar si alguna de las dependencias es superflua.

    El cubrimiento
    minimal es un conjunto cuya clausura abarca la misma cantidad de atributos que el conjunto original. El primer paso de la lista lo podemos hacer aplicando la descomposición de los axiomas de Armstrong. Los otros dos requieren que calculemos la clausura del conjunto de atributos.

    Empecemos entonces por reducir la cantidad de atributos a la derecha en cada DF:

    • D→EG se convierte en D→E y D→G
    • CG→BD se convierte en CG→B y CG→D
    • CE→AG se convierte en CE→A y CE→G

    Ahora, seguimos por eliminar los atributos innecesarios en el lado izquierdo de las reglas. Por ejemplo, vemos que tenemos la dependencia C→A y CE→A. Observo que puedo construir la segunda regla con aumento y descomposición y por lo tanto es totalmente superflua. La elimino directamente.

  6. Sea R un esquema relacional, F un conjunto de dependencias funcionales y FM
    un cubrimiento minimal de F. Probar que:

    1. Si X→A ∈ FM, X⊆R, A∈R, no puede ser X
      superclave de R sin ser, a su vez, clave de dicho esquema.
    2. Si X→A ∈F, X⊆R, A∈R, y F|=X1→
      X2, con X1⊂X, X2⊂X, X2
      ⊄X1, entonces X→A ∉FM

    1. Solución. Empiezo con suponer que X es superclave y no clave. X superclave, quiere decir que todos los
      atributos de la relación pertenecen a la clausura de X, y si no es clave, entonces se viola la condición de que X no debe tener atributos redundantes. Dicho de otra manera, existe un subconjunto de X,
      digamos Z, cuya clausura es igual a todos los atributos de la relación.

      Pero X→A ∈ FM, luego, ∀ X→A ∈ FM,
      -∃ Z ∈ X tal que FM-{X→A} U {Z→A} ≡ FM*. O sea, si FM es el cubrimiento minimal entonces para cada una de las dependencias funcionales que pertenecen a él, no existe ningún subconjunto de atributos de X que sirvan para derivar A. Por lo tanto, al obligar que X no tenga ningún subconjunto que permita que se deriven atributos de él, estoy obligando que sea clave, pero yo había empezado diciendo que X era clave. Luego estoy en un absurdo que vino de suponer que X es superclave y no clave del esquema R, por lo tanto X no puede ser superclave sin ser clave del esquema R.

    2. Solución. ¿Qué
      quieren decir todos esos símbolos raros? Quiere decir que en X hay 2 conjuntos, X1 y X2, en donde uno se deriva a partir del otro. O sea, X1→X2. Consideremos la regla de Armstrong de pseudotransitividad. De X→Y e YW→Z, inferir XW→Z. ¿Qué tal si en esa regla sustituimos X por X1, Y por X2, W por X1 y Z por A? Entonces nos queda que de X1 →X2 y X2X1→A (esto es la definición de X→A), podemos deducir X1X1→A. Por lo tanto A se puede deducir solamente de una parte de X. Por lo tanto X→A no está en el conjunto minimal.

  7. Dado el esquema de relación R(A,B,C,D,E)
    y las siguientes instancias:

    A B C D E   A B C D E   A B C D E
    a1 b1 c1 d1 e1   a1 b2 c1 d2 e1   a1 b1 c2 d2 e2
    a1 b2 c2 d1 e1  

    		a2 b2 c1 d2 e2   a2 b1 c2 d2 e2
    a2 b1 c2 d1 e1   a2 b2 c2 d2 e2   a1 b2 c1 d1 e1
    1. Analizar si cada instancia cumple con las siguientes dependencias:
      1. A→BC
      2. D→E
      3. BC→D
    2. Analizar para cada caso las anomalías existentes en R tomando como conjunto de dependencias al formado por las dependencias de i a iii que se hayan verificado sobre la instancia.

Leave a Reply

Your email address will not be published.