Algoritmo de cierre de atributos y su utilización

Cierre de un conjunto F de FDs es el conjunto F ⁺ de todos los FDs que se pueden inferir de F. También se le conoce como conjunto completo de Dependencia Funcional . Se denota por F ⁺ .

Algoritmo: conjunto de cierre de atributo

Algorithm to compute a+, the closure of a under F
Result:= a;
while (changes to Result) do  
    for each B → Y in F do
        Begin
            if B ⊆  Result  then  Result := Result ∪  Y  
        End

Utilización del Cierre de Atributos –

• Para probar el(los) atributo(s) dado(s) es superclave/clave candidata o no.
• Podemos verificar si FD X → Y se cumple.
• Una forma alternativa de averiguar F ⁺ .

1. Pruebe si el atributo es superclave o no.

   Ejemplo:
   Sea R = (A, B, C, G, H, I) y el conjunto de FD son F = { A → B, A → C, CG → H, CG → I, B → H}

   Averiguar (AG) ⁺ .

   Resultado = {A, G}

   Primer bucle:

   A → B includes B in the Result as A⊆ Result (which is AG), so Result := Result ∪ B. 
   Hence Result = {A, G, B}
   A → C causes Result to become ABCG.
   CG → H causes the Result to become ABCGH.
   CG → I causes the Result to become ABCGHI.
   B → H causes Result to become ABCGHI.

   Segundo bucle:

   A → B causes the Result to be unchanged i.e. ABCGHI (B is already part of the Result).
   A → C causes Result to be unchanged.
   CG → H causes the Result to be unchanged.
   CG → I causes the Result to be unchanged.
   B → H causes Result to be unchanged.

   Al final del segundo bucle, el resultado no cambia, así que salga del bucle.

   (AG) ⁺ = {A, B, C, G, H, I}

   Conclusión: AG es una súper clave ya que todos los demás atributos pueden ser determinados por ella.

2. Compruebe si Fd existe:

   Ejemplo:
   Sea R = (A, B, C, G, H, I) y el conjunto de FD son F = { A →B, A → C, CG → H, CG → I, B → H}

   Marque HB → I aguanta o no

   Resultado = {H, B}

   Primer bucle:

   In A → B as A ⊆ Result (which is HB) so nothing will be added.
   In A → C nothing added.
   CG → H (CG ⊆ Result (which is HB) so nothing added)
   CG → I nothing added.
   B → H nothing added.

   Al final del primer bucle, el resultado no cambia, así que salga del bucle.

   Conclusión: HB → I no se sostiene.

3. Una forma alternativa de encontrar el Cierre de FD (F ⁺ ).

   Ejemplo:
   dada una relación R (A, B, C, D, E, F) y un conjunto de FD F: {A → BC, E → CF, B → E, CD → EF}

   Averiguar el cierre de {A, B} ⁺

   Paso-1: Resultado = AB

   Paso 2: primer ciclo

   Result = ABC for A → BC, A ⊆ Result so Result = Result ∪ BC.
   Result = ABC for E→ CF, E ∉ Result so Result = Result.
   Result = ABCE for B → E, B ⊆Result so Result = Result ∪ E.
   Result = ABCE for CD → EF, CD ∉ Result so Result = Result.

   El resultado antes del paso 2 es AB y después del paso 2 es ABCE, que es diferente, así que repita lo mismo que el paso 2.

   Paso 3: segundo ciclo

   Result = ABCE for A → BC, A ⊆ Result so Result = Result ∪ BC.
   Result = ABCEF for E → CF, E ⊆ Result so Result = Result ∪ CF.
   Result = ABCEF for B → E, B ⊆ Result so Result = Result ∪ E.
   Result = ABCEF for CD → EF, CD ∉ Result so Result = Result.

   El resultado antes del paso 3 es ABCE y después del paso 3 es ABCEF, que es diferente, así que repita lo mismo que en el paso 3.

   Paso 4: Tercer ciclo

   Result = ABCEF for A → BC, A ⊆ Result so Result = Result ∪ BC.
   Result = ABCEF for E → CF, E ⊆ Result so Result = Result ∪ CF.
   Result = ABCEF for B → E, B ⊆ Result so Result = Result ∪ E.
   Result = ABCEF for CD → EF, CD ∉ Result so Result = Result.

   El resultado antes del paso 4 es ABCEF y después del paso 3 es ABCEF, que es lo mismo, así que deténgase.

   Entonces el Cierre de {A, B} ⁺ es {A, B, C, E, F}.

   Conclusión: para cada atributo/conjunto de atributos podemos encontrar un cierre. Esto da como resultado F ⁺ .