Algoritmo De Descompocicion

ALGORITMO DE DESCOMPOSICIÓN EN FNBC

Este algoritmo tiene como entrada R(Â), Fc y R que no está en FNBC, y obtiene como salida rr / "Ri Î rR están en FNBC y rR es sin pérdida:

1-Tomamos una dependencia funcional X->Y Î F tal que X no es superclave.

2- Construimos dos relaciones R1=PX,Y(R)=R1(X,Y) y R2=PÂ-Y(R)=R2(Â-Y). Todos los atributos de R1 menos el consecuente.

3- Sialguna de las dos relaciones no está en FNBC se vuelve a aplicar el algoritmo.



El algoritmo garantiza que la descomposición es reversible pero no garantiza que preserve las dependenciasfuncionales. La salida del algoritmo no es única, y algunas de ellas no preservan las dependencias funcionales.



Ejemplo:

R(ABCDE) F={A->B,AC->D,BD->E} que está canonizado.Busquemos las claves: sólo hay una AC (AC)+=ABCDE

1- Tomamos A->B

2- R1(AB) R2(ACDE)

3- F1={A->B} clave A => está en FNBCF2={AC->D,AD->E} A->B y BD->E => AD->E Clave AC => no está en FNBC

Aplicamos el algoritmo sobre R2 y F2:

1- Tomamos AD->E

2- R3(ADE) y R4(ACD)3 F3={AD->E} clave (AD) -> FNBC F4={AC->D} clave (AC) -> FNBC

Fin del algoritmo: rr={R1(AB),R3(ADE),R4(ACD)}



Veamos ahora si preserva las dependenciasfuncionales:

Tenemos que ver si F1 È F3 È F4 º Fc

Como AC->D Ì Fc y A->B Ì Fc solo hay que ver si F1 È F3 È F4 ╞ BD->E

(BD)+ F1 È F3 È F4 = BD , E no pertenece => nopreserva las Dfs

Como rR no es única y depende del antecedenete tomado, obtendremos otro rR.

BD->E

R1(BDE) F1={BD->E} (BD) FNBCR’(ABCD) F´={A->B,AC->D} (AC) no FNBC

A->B

R2(AB) F2={A->B} (A) FNBC

R3(ACD) F3={AC->D}...