Normalizacion - Base de Datos

Ctedra de Base de Datos Universidad Nacional de La Matanza

Documento elaborado por Guillermo Giannotti Pgina 1 de 10

Apunte Terico de Dependencias Funcionales y Normalizacin

El presente apunte es un resumen de algunos conceptos dados en las Unidades de Dependencias Funcionales y Normalizacin, para mayor informacin consulten la bibliografa recomendada por la ctedra. DEFINICION DE DEPENDENCIA FUNCIONAL Una dependencia funcional es una restriccin entre dos conjuntos de atributos de una relacin.

Sea R un esquema de relacin, y X e Y dos subconjuntos de R.

La dependencia funcional X Y se cumple en R si en ninguna instancia de R pueden

existir dos tuplas t1 y t2 tales que:

t1[X] = t2[X] y t1[Y] t2[Y]

Es decir, si dos tuplas cualesquiera tienen igual valor en el atributo X, deben tener igual valor en el atributo Y, para que se cumpla la dependencia funcional. A fin de comprender mejor el concepto, podemos trazar un paralelismo entre las dependencias funcionales y el concepto de una funcin matemtica del tipo f(x)=y. Recordemos que segn la definicin de funcin para un valor determinado de X la funcin debe retornar un nico valor de Y. Puede darse el caso que un mismo valor de Y pueda ser obtenido con distintos valores de X, pero no se admite que ocurra a la inversa. Ejemplo: Examen (TipoDoc, NroDoc, Nombre, Apellido, CodMateria, NombreMateria, FechaExamen, Nota) Se cumplen las siguientes dependencias funcionales: F= { TipoDoc, NroDoc Nombre, Apellido ; CodMateria NombreMateria ; TipoDoc, NroDoc, CodMateria, FechaExamen Nota } Dependencia Funcional Trivial Decimos que una Dependencia es Trivial cuando es obvia, por ejemplo X X.

f(2) = 3 f(5) = 3

Esto es admitido en una funcin.

f(2) = 3 f(2) = 5

Esto NO es admitido en una funcin.

f(x) = y X Y

X Y 2 3 5 3

X Y 2 3 2 5

Esto es admitido en la dependencia funcional dada.

Esto NO es admitido en la dependencia funcional dada.



CLAVE Y SUPERCLAVE Dado un esquema R( A1, A2, ... An ) y un conjunto de dependencias funcionales F asociado, se dice que X c R es un CLAVE para el esquema R si se cumplen las dos condiciones siguientes:

1) X determina a todos los atributos de R, X A1, A2, An

2) No existe ningn Z (subconjunto de X) que determine a todos los atributos de R (condicin de minimalidad).

Por otra parte, decimos que Y es superclave de R si cumple la condicin 1. Se cumple, que toda clave es superclave, pero no a la inversa. Ejemplo: Empleado (Legajo, Nombre, DNI) Claves Candidatas = { Legajo ;

DNI } Superclaves = { Legajo, Nombre ;

DNI, Nombre ; Legajo, DNI ; Legajo, Nombre, DNI }.

AXIOMAS DE ARMSTRONG Reflexividad Si Y C X => se cumple XY Aumento Dada XY se puede inferir XZYZ Transitividad Dadas XY y YZ se puede inferir XZ REGLAS ADICIONALES/DERIVADAS Descomposicin Dada XYZ se pueden inferir XY y XZ Unin Dadas XY y XZ se puede inferir XYZ Pseudotransitividad Dadas XY y WYZ se puede inferir WXZ



DEMOSTRACIONES Cada uno de los Axiomas de Armstrong puede ser demostrado en base a la definicin de dependencia funcional: Demostracin de la Reflexividad: Supongamos que Y C X y que existen dos tuplas t1 y t2 en algn ejemplar de la relacin r de R tales que t1[X]=t2[X]. Entonces t1[Y]=t2[Y] porque Y C X; por lo tanto, debe cumplirse XY en r. Demostracin del Aumento (por contradiccin): Supongamos que XY se cumple en algn ejemplar r de R, pero que XZYZ no se cumple. En tal caso, deben existir dos tuplas t1 y t2 en r tales que (1) t1[X]=t2[X], (2) t1[Y]=t2[Y], (3) t1[XZ]=t2[XZ] y (4) t1[YZ]t2[YZ]. Esto no es posible porque a partir de (1) y (3) se deduce (5) t1[Z]=t2[Z], y a partir de (2) y (5) se deduce (6) t1[YZ]=t2[YZ], lo que contradice (4). Demostracin de la Transitividad: Supongamos que se cumplen (1) XY y (2) YZ en una relacin r. Entonces, para cualesquier dos tuplas t1 y t2 en r tales que t1[X]=t2[X], debemos tener (3) t1[Y]=t2[Y] (por la suposicin de (1)), y por tanto tambin debemos tener (4) t1[Z]=t2[Z], (por (3) y a partir de la suposicin (2)); por lo tanto, se debe cumplir XZ en r. Cada una de las reglas adicionales puede ser demostrada a partir de los Axiomas de Armstrong: Demostracin de la Descomposicin:

1) XYZ Dada 2) YZY por Reflexividad (donde Y C YZ) 3) XY Transitividad entre 1 y 2

Demostracin de la Unin:

1) XY Dada 2) XZ Dada 3) XXY Aumento con X en 1 (XX=X) 4) XYYZ Aumento con Y en 2 5) XYZ Transitividad entre 3 y 4

Demostracin de la Pseudotransitividad:

1) XY Dada 2) WXWY Aumento con W en 1 3) WYZ Dada 4) WXZ Transitividad entre 3 y 2



CLAUSURA DE UN CONJUNTO DE DEPENDENCIAS Dado un conjunto de DF llamado F, denominamos clausura de F (F+) al conjunto de todas las dependencias posibles que se pueden inferir de F. Por ejemplo:

R(A, B, C) F={ AB, BCA } F+={ AA,

BB, CC, ABAB, ABA, ABB, ACAC, ACA, ACC, BCBC, BCB, BCC, ABCABC, ABCAB, ABCAC, ABCBC, ABCA, ABCB, ABCC, AB, AAB, ACB, ACAB, ACBC, ACABC, BCA, BCAB, BCAC, BCABC }

Nota: Las DF son relaciones del tipo {conjunto de atributos}{conjunto de atributos}, por lo tanto, el orden de los atributos no importa (ABA es lo mismo que BAA). CLAUSURA DE UN CONJUNTO DE ATRIBUTOS Sea X un conjunto de atributos de R, y F un conjunto de DF que se cumplen en R, llamamos Clausura de X en F (X+F) al conjunto de todos los atributos determinados funcionalmente por X. Ejemplo:

R(A, B, C) F = { AB, BCA } A+F = AB B+F = B C+F = C AB+F = AB AC+F = ABC BC+F = ABC ABC+F = ABC Algoritmo para calcular X+ X+ : = X; viejoX+ := {}; Mientras X+viejoX+ hacer viejoX+ := X+; Para cada dependencia YZ en F hacer Si Y C X+ entonces X+ := X+ U Z Fin Mientras

Inferidas

Triviales (obvias)

Con esto podemos calcular fcilmente el conjunto F+ (haciendo todas las combinaciones)



EQUIVALENCIA ENTRE DOS CONJUNTOS DE DEPENDENCIAS FUNCIONALES Dos conjuntos de dependencias funcionales F y G son equivalentes cuando sus clausuras son iguales:

F G (F es equivalente a G) F+ = G+ Para probar que dos conjuntos F y G son equivalentes, sin necesidad de calcular F+ ni G+, se debera probar que toda dependencia de F puede inferirse en G (F C G+), y recprocamente, toda dependencia de G se puede inferir en F (G C F+).

F+ = G+ F C G+ y G C F+ Si se cumple que F C G+ decimos que G cubre a F y si se cumple que G C F+ decimos que F cubre a G. Podemos determinar si F cubre a G calculando X+F para cada dependencia XY de G, y comprobando que Y C X+F Veamos un ejemplo: R (A, B, C, D) F = { AB, AC, BA, DA } G = { DABC, BA, BC, AB } Son F y G equivalentes?

? F G

? F+ = G+

Respuesta: S, F y G son equivalentes.

? F C G+

A+F = ABC B+F = BAC D+F = DABC

? G C F+

D+E = DABC B+E = BAC A+E = ABC



Conjunto Mnimo de Dependencias Funcionales (Fmin) Un conjunto de dependencias funcionales es Mnimo si cumple las siguientes condiciones:

1) Todas sus dependencias funcionales tienen un solo atributo en su parte derecha (determinado).

2) No podemos reemplazar ninguna dependencia funcional XA por otra YA, donde Y C X, y seguir teniendo un conjunto equivalente.

3) No podemos quitarle ninguna dependencia funcional y seguir teniendo un conjunto equivalente.

A Fmin, tambin se lo llama Cobertura minimal y es un conjunto de dependencias funcionales sin redundancias. Un conjunto F puede tener varias coberturas minimales. Algoritmo para el Clculo de Fmin Dado un conjunto F, realizar los siguientes tres pasos: Paso 1) Descomponer parte derecha

Reemplazar cada DF XA1, A2, ..,, AN por N dependencias del tipo XA1, XA2, .., XAN Llamaremos F1 al conjunto resultante luego de aplicar este primer paso.

Paso 2) Eliminar redundancia en parte izquierda

Tomar las DF con ms de un atributo en la parte izquierda y hacer: Por cada dependencia WY,

para cada subconjunto A que est incluido W, calcular (W-A)+ en F1 si (W-A)+F1 contiene a Y => reemplazar WY por (W-A) Y

Llamaremos F2 al conjunto resultante luego de aplicar este segundo paso.

Paso 3) Eliminar dependencias redundantes

Definir F3=F2 Por cada dependencia XY de F3

Calcular X+ en F3 {XY}, Si X+ contiene a Y => eliminar XY de F3

El conjunto obtenido luego de aplicar los tres pasos ser Fmin. Veamos un ejemplo: R(ABCDE) F={ABCD, ABDE, BEAC} Paso 1) F1 = { AB, AC, AD, ABD, ABE, BEA, BEC }



Paso 2) A+F1 = ABCDE ABD => reemplazar por AD B+F1 = B A+F1 = ABCDE ABE => reemplazar por AE B+F1 = B B+F1 = B BEA E+F1 = E B+F1 = B BEC E+F1 = E F2 = { AB, AC, AD, AE, BEA, BEC } Paso 3) AB A+F2 {AB} = ACDE no es redundante AC A+F2 {AC} = ABCDE AC es Redundante AD A+F2 {AC} { AD} = ABEC no es redundante AE A+F2 {AC} { AE} = ABD no es redundante BEA BE+F2 {AC} { BEA} = BEC no es redundante BEC BE+F2 {AC} { BEC} = BEAD no es redundante F3 = { AB, AD, AE, BEA, BEC }

Fmin = F3

Fmin = { AB, AD, AE, BEA, BEC }



FORMAS NORMALES Las siguientes son definiciones prcticas creadas como simplificaciones de las definiciones tericas que aparecen en la bibliografa. Si bien son equivalentes, se recomienda consultar la bibliografa para conocer las definiciones formales de cada forma normal. Primera Forma Normal

Atributos con valores atmicos (o indivisibles). Esta Forma Normal no admite los atributos multivaluados, los atributos compuestos y sus combinaciones.

Segunda Forma Normal V X Y, X no debe ser un subconjunto de alguna CC (*) o Y es primo

(*) Decir que X no debe ser primo, no sera estrictamente correcto, porque primos son los atributos, no los subconjuntos. Adems, si la clave es 1 solo atributo, ese atributo es primo y en ese caso no viola 2FN.

Tercera Forma Normal V X Y, X es Superclave o Y es primo Forma Normal de Boyce - Codd V X Y, X es Superclave IMPORTANTE: Todas las Formas Normales aceptan DF XY donde Y C X (trivial). Por eso, lo mejor es usar Fmin al momento de evaluar en qu forma normal se encuentra un esquema dado, ya que Fmin no contiene DF triviales.

1FN

2FN

3FN

FNBC



TEOREMA DE HEATH (Pgina 434 del libro de Elmasri-Navathe) Una descomposicin D={R1, R2} de R es Sin Perdida de Informacin, si y solo si: - La DF (R1R2) (R1-R2) pertenece a F+

O bien,

- La DF (R1R2) (R2-R1) pertenece a F+ Nota: Este teorema solo es til para descomposiciones de dos subesquemas, a diferencia del mtodo del Tableaux que permite verificar la Prdida de Informacin de cualquier descomposicin. ALGORITMO PARA 3FN (Sin PI y sin PDF) Pasos: 1) Calcular Fmin 2) Para cada miembro izquierdo X que aparezca en Fmin, crear un esquema de relacin {X unin A1 unin A2 unin An} donde XA1, XA2, , XAn sean todas DF de Fmin. 3) Colocar los atributos restantes (no colocados por no formar parte de ninguna DF) en un solo esquema de relacin. 4) Si ninguno de los esquemas resultantes contiene una clave candidata de R, crear un esquema adicional que contenga una clave candidata de R. ALGORITMO PARA FNBC (Sin PI) Dado el esquema R y el conj. de DF F (no es necesario trabajar con Fmin, pero si es aconsejable): Para cada DF XY perteneciente a F que no sea trivial y que viole FNBC, hacer 2 subesquemas: R1=(X U Y) y R2=(R - Y) Si alguno de los dos subesquemas obtenidos sigue violando FNBC, aplicar nuevamente el punto anterior sobre dicho esquema. Repetir ese paso, e ir dividiendo en subesquemas, tantas veces como sea necesario, hasta lograr obtener todos subesquemas que cumplan FNBC. Divisin de las Dependencias Funcionales: Las dependencias de F debern repartirse a F1 o F2 segn corresponda (puede ser que alguna dependencia no pueda incluirse en ninguno de los dos subconjuntos y en ese caso la misma se perder, pero esa prdida puede salvarse intentando inferir alguna otra dependencia equivalente en base a ella, que si pueda ubicarse en F1 o F2). Veamos un ejemplo: Dado R(MNOPQS) y F={MON, NMO, ONM, MQSO, OPQ}



En primer lugar, calcularemos Fmin para simplificar el desarrollo: F1={ MO, MN, NM, NO, ON, OM, MQS, MQO, OPQ } F2={ MO, MN, NM, NO, ON, OM, MQS, OPQ} F3={ MN, NO, OM, MQS, OPQ } = Fmin En qu forma normal se encuentra R? Para responder a esa pregunta debemos calcular las Claves Candidatas y luego evaluar una a una las dependencias funcionales. CC = {PM, PN, PO} MN cumple 3FN NO cumple 3FN OM cumple 3FN MQS cumple 2FN OPQ cumple FNBC Repuesta: R se encuentra en 2FN Ahora aplicaremos el Algoritmo para obtener una descomposicin de R que cumpla FNBC. La descomposicin obtenida es:

R1, R3, R5 y R6 con F1, F3, F5 y F6 En este caso, al inferir las DF indicadas, se logra que no haya prdida de dependencias funcionales.

MN

R1(MN) F1={MN, NM}

DF inferida

R2(MOPQS) F2={OM, MQS, OPQ, MO} CC={PM, PO}

DF inferida

OM

R3(OM) F3={OM, MO}

R4(OPQS) F3={OPQ, OQS } CC={PO}

DF inferida

OQS

R5(OQS) F5={OQS}

R6(OPQ) F6={OPQ}

Documents

Normalizacion - Base de Datos