Reglas sobre dependencias funcionales.

el

Supongamos que tenemos un conjunto de dependencias funcionales que satisfacen una relación. A veces, podemos deducir que la relación puede satisfacer otras dependencias funcionales. Esta habilidad para descubrir dependencias funcionales es esencial cuando se analiza el diseño de los esquemas de las relaciones.

1. Conjuntos de dependencias funcionales equivalentes.

A veces las dependencias funcionales pueden ser presentadas de diferentes maneras, sin cambiar el conjunto de instancias legales de la relación. Se dice que:

  • Dos conjuntos de dependencias funcionales S y T son equivalentes si el conjunto de instancias de relación que satisface S es exactamente el mismo que el conjunto de instancias de relación que satisface T.
  • Más general, un conjunto de dependencias funcionales S que resulta de un conjunto de dependencias funcionales T ; si cada instancia de relación que satisface todas las dependencias funcionales en T también satisface todas las dependencias funcionales en S.

Entonces se nota que dos conjuntos de dependencias funcionales S y T son equivalentes si y solo si S resulta de T, y T resulta de S.

En los siguientes apartados se muestran las diferentes reglas sobre dependencias funcionales. Estas reglas nos dejan remplazar un conjunto de dependencias funcionales por un conjunto equivalente, o agregar a un conjunto de dependencias funcionales otras que resultan del conjunto original.

2. La regla de división/combinación.

La regla de división nos dice que dado una dependencia funcional A1, A2, …, An →  B1, B2, …, Bm podemos remplazarla por un conjunto de dependencias funcionales A1, A2, …, An →  B1, A1, A2, …, An →  B2, A1, … A2, …, An →  Bm.

La regla de unión nos dice que dado un conjunto de dependencias funcionales A1, A2, …, An →  B1, A1, A2, …, An →  B2, A1, … A2, …, An →  Bm puede ser remplazado por la dependencia funcional A1, A2, …, An →  B1, B2, …, Bm.

3. Dependencias funcionales triviales.

Se dice que una restricción de cualquier tipo en una relación es trivial si se cumple para cada instancia de la relación, independientemente de qué otras restricciones se supongan. Cuando las restricciones son dependencias funcionales, es fácil decir cuando una dependencia funcional es trivial.

Una dependencia funcional A1, A2, …, An →  B1, B2, …, Bm es trivial si {B1, B2, …, Bm} ⊆ {A1, A2, …, An}. Es decir, tiene del lado derecho un subconjunto que esta en el lado izquierdo.

Cada dependencia funcional trivial se mantiene en cada relación, ya que se dice que “dos tuplas que coinciden en cada uno de A1, A2, …, An coincide en un subconjunto de ellos”. Por lo tanto, se puede asumir cualquier dependencia trivial, sin tener que justificarla en las bases de que dependencias funcionales son verdaderas para la relación.

La regla de la dependencia-trivial dice que una dependencia A1, A2, …, An →  B1, B2, …, Bm es equivalente A1, A2, …, An →  C1, C2, …, Ck donde las C’s son todas estas B’s que no son también A.

Figura 1.0. Regla de la dependencia-trivial.

4. Calcular la cerradura de atributos.

Antes de mencionar las demás reglas, se dará el principio general del cual las siguientes reglas resultan verdaderas. Supongamos {A1, A2, …, An} es un conjunto de atributos y S es un conjunto de dependencias funcionales. La cerradura de {A1, A2, …, An} bajo las dependencias funcionales en S es el conjunto de los atributos de B tal que cada relación que satisface todas las dependencias funcionales en el conjunto S también satisface A1, A2, …, An → B. Esto es, A1, A2, …, An →  B resulta de las dependencias funcionales de S. Denotamos la cerradura de un conjunto de atributos A1, A2, …, An como {A1, A2, …, An}+. Notamos que A1, A2, …, An esta siempre en {A1, A2, …, An}+ porque la dependencia funcional A1, A2, …, An →  Ai es trivial cuando i es 1, 2, …, n.

Notamos que {A1, A2, …, An}+ es el conjunto de todos los atributos de una relación si y solo si A1, A2, …, An es una super llave para la relación. Solo entonces A1, A2, …, An determina funcionalmente todos los otros atributos. Se puede probar si A1, A2, …, An es una llave para una relación revisando primero que {A1, A2, …, An}+ se encuentran todos los atributo, y entonces revisar que, para ningún conjunto X formado removiendo un atributo de {A1, A2, …, An}, es X+ el conjunto de todos los atributos.

Algoritmo 1.0. Cerradura de un conjunto de atributos.

Entrada: Un conjunto de atributos {A1, A2, …, An} y un conjunto de dependencias funcionales S.

Salida: La cerradura {A1, A2, …, An}+

  1. Si es necesitado, dividir las dependencias funcionales de S. Así cada dependencia funcional en S tiene solo un atributo del lado derecho.
  2. Sea X un conjunto de atributos que eventualmente se convertirá en la cerradura. Iniciar X con {A1, A2, …, An}.
  3. Repetidamente buscar por alguna dependencia funcional B1, B2, …, Bm→  C tal que cada uno B1, B2, …, Bm están en el conjunto de atributos X, pero C no. Agregar C al conjunto X y repetir la búsqueda. Ya que X puede solo crecer, y el número de atributos de cualquier esquema de relación debe ser finito, eventualmente no se agregaran más a X, y este paso terminara.
  4. El conjunto X, después de no haber más atributos que puedan ser agregados, es el valor correcto de {A1, A2, …, An}+.

Ejemplos

Consideremos una relación con atributos A, B, C, D, E, y F. Supongamos que esta relación tiene las dependencias funcionales AB→C, BC→AD, D→E, y CF→B. ¿Cuál es la cerradura de {A, B}, que es {A, B}+?

  1. Dividimos BC→AD en BC→A y BC→D. Entonces empezamos con X = {A, B}. Primero notamos que ambos atributos del lado izquierdo de la dependencia funcional AB → C están en X, así que nosotros podemos agregar C, el cual esta del lado derecho de la dependencia funcional. Por lo tanto después de una iteración del paso 3, X se convierte en {A, B, C}.
  2. Vemos que el lado izquiero de BC → A y BC → D ahora estan contenidos en X, así que podemos agregar a X los atributos A y D, así que X se convierte en {A, B, C, D}. En este punto, podemos usar la dependencia funcional D → E para agregar E a X, el cual es ahora {A, B, C, D, E}. No hay más cambios posibles a X. En particular, la dependencia funcional CF→B no puede ser usada porque su lado izquierdo nunca esta contenido en X. Por lo tanto, {A, B}+= {A, B, C, D, E}.

A1, A2, …, An →  B1, B2, …, Bm resulta de un conjunto de dependencias funcionales S si y solo si todos los B1, B2, …, Bm están en {A1, A2, …, An}+.

Consideremos la relación y dependencias funcionales del ejemplo anterior. Supongamos que deseamos probar que AB → D resulta de estas dependencias funcionales. Entonces calculamos la cerradura de {A, B}+ la cual es {A, B, C, D, E}, cómo D es un miembro de la cerradura, concluimos que AB → D resulta de estas dependencias funcionales.

5. La regla de la transitividad

La regla de transitividad dice que si dos dependencias funcionales A1 A2 … An →  B1 B2 … Bm y B1 B2 … Bm →  C1 C2 … Ck en la relación R entonces A1 A2 … An →  C1 C2 … Ck también permanece en la relación. Si alguna de las C’s están entre las A’s se eliminan del lado derecho usando la regla de dependencia-trivial.

6. Conjuntos cerrados de dependencias funcionales.

A veces tenemos una opción de que dependencias funcionales usar para representar el conjunto completo de dependencias funcionar para una relación. Si estamos dando un conjunto de dependencias funcionales S (tal como las dependencias funcionales que permanecen en una relación dada), entonces cualquier conjunto de dependencias funcionales equivalente a S se dice ser una base para S. Para evitar algo de las posibles bases, nos limitaremos a considerar solo bases cuyas dependencias funcionales tienen lados derechos únicos. Si tenemos cualquier base, nosotros podemos aplicar la regla de división para hacer el lado derecho único. Una base minimal para una relación es una base B que satisface tres condiciones:

  1. Todas las dependencias funcionales en B tienen un lado derecho único.
  2. Si cualquier dependencia funcional es removida del lado B , el resultado no es una base.
  3. Si para cualquier dependencia funcional en B removemos uno o más atributos del lado izquierdo de F, el resultado no es una base.

Notar que las dependencias no triviales pueden ser una base minimal, porque podría ser removido por una regla.

7. Reglas de inferencia

Si queremos conocer si una dependencia funcional resulta de alguna de las dependencias funcionales dadas, el calculo de la cerradura siempre servirá. Sin embargo, es interesante conocer que hay un conjunto de reglas, llamadas axiomas de Armstrong, de las cuales es posible derivar cualquier dependencia funcional que resulte de un conjunto dado. Estos axiomas son:

  1. Reflexividad. Si {B1, B2, …, Bm}⊆ {A1, A2, …, An}, entonces A1 A2 … An →  B1 B2 … Bm. Nosotros lo hemos llamado dependencia funcional trivial.
  2. Aumento: Si A1 A2 … An →  B1 B2 … Bm entonces A1 A2 … An C1 C2 … Ck →  B1 B2 … Bm C1 C2 … Ck para cualquier conjunto de atributos C1 C2 … Ck. Ya que alguno de los C’s puede también ser A’s o B’s o ambos, se deberían eliminar del lado izquierdo atributos duplicados y hacer lo mismo para el lado derecho.
  3. Transitividad.

Referencia

Elmasri, R. and Navathe, S. B. Fundamentals of Database Systems. Addison-Wesley Publising Company, Sexta edición, 2011.

Comentarios

Publicar un comentario