Normalização de BD: Dependência Funcional

Vista previa del material en texto

Clase 3: Normalización
BASE DE DATOS
FAC.DE INGENIERIA – UNJu
2.018
3.- DEPENDENCIA FUNCIONAL
“1 dependencia funcional es 1restricción entre dos conjuntos de atributos de 1 BD.”
Dado el esquema de 1 BD relacional R={A1,A2,...,An}, una dependencia funcional X <== Y 
( Y depende funcionalmente de X ) entre dos conjuntos de atributos X e Y que son 
subconjuntos de R, implica que existe 1dependencia entre las posibles tuplas t1 y t2 q 
pueden pertenecer a la relación r(R). 
Esta dependencia conlleva a q p/ toda tupla t1 y t2 pertenecientes a la relación r, siempre 
que t1[X] = t2[X] se verifica que t1[Y] = t2[Y]
Es decir, Y es funcionalmente dependiente de X si y solo si, p/toda tupla de la relación en la 
q X toma un valor, le corresponde un mismo valor p/Y (tal como se muestra a continuación)
Relación (R) = BD de Alumnos
3.- DEPENDENCIA FUNCIONAL
Un esquema relacional R(A,F) está 
constituido por un conjunto de atributos 
A={A1,A2,...An} y un conj.de
dependencias funcionales F existentes 
entre dichos atributos. 
X ej. en la relación EMPLEADO_PROYECTO, se pueden establecer las sig.dependencias fcionales: 
Numb_P  ( (Nomb_P, Situ_P): esta dependencia indica q x el nro de un proyecto (Num_P) 
queda determinado su nombre (Nomb_P) y su situación (Situ_P).
(CUIL, Num_P)  (Horas) : conj.formado por el nro.de la seguridad social de 1empleado y 
el nro de un proyecto q determinan funcionalmente las horas q un empleado trabaja en el. 
Depend.Fcionales de la relación EMPLEADO_PROYECTO:
CUIL  (Nombre_E): esta dependencia funcional indica q el 
nro.de cuil (CUIL) de 1empleado determina el nombre del 
mismo (Nomb_E). Igualmente podemos decir q Nomb_E está 
funcionalmente determinado por NSS ya q dado un 
determinado valor de CUIL conocemos el valor de Nomb_E. 
REGLAS DE INFERENCIA LÓGICAS PARA DEPENDENCIAS FUNCIONALES
Sea F 1conj.de dependencia fcionales.especificadas en 1esquema relacional R, 
y sea ƒ una depend.fcional.definida sobre el conj.de atributos del esquema relacional, se 
dice q F implica o infiere lógicamente a ƒ, (F = f), si c/relación r(R) q satisface las 
dependencias fcionales en F también satisface ƒ. X ej., p/el siguiente conj.de
dependencias fcionales:
F = { CUIL  { Nomb_E, Fech_na, Dirección, Num_D }, 
Num_D { Nomb_D, CUIL_jefeD} } 
De F se pueden derivar las siguientes dependencias: 
CUIL  { Nomb_E, CUIL_jefe } ƒ1 
CUIL  CUIL ƒ2 
Num_D Nomb_D ƒ3 
Las dependencias funcionales q se infieren de 1conj.de dependencias F están
determinadas x las denominadas REGLAS DE INFERENCIA
REGLAS DE INFERENCIA
a) Reflexiva: 1 conj.de atrib.siempre se determina a si mismo y a 1subconj.propio. 
Si Y “está incluido en” X, X ⊆ Y entonces X  Y 
Ej.: {CUIL, Nomb_E}  Nomb_E
{CUIL, Nomb_E}  CUIL 
b) Aumentación: Si se suma 1conj.de atributos a ambos lados de 1dependencia 
fcional se obtiene otra dependencia fcional igualmente válida. 
Si X  Y entonces XZ  YZ 
Ej: {CUIL, Nomb_E}  Dirección 
{CUIL, Nomb_E,Fech_na}  {Dirección, Fech_na} 
c) Transitiva: Si Y depende funcionalmente de X, y Z depende funcionalmente de Y, 
entonces se verifica que Z depende funcionalmente de X.
Si { X  Y, Y  Z } entonces X  Z 
Ej. {CUIL}  {Num_D} 
{Num_D}  { Nomb_D} 
{CUIL}  {Nomb_D} 
Estas 3 propiedades se conocen con el nombre de Axiomas de Armstrong y a partir de 
ellas se pueden deducir: 
REGLAS DE INFERENCIA
d) Proyección: Si el conj.de atributos Y depende fcionalmente de X y se verifica q los 
valores del conj.de atributos Z están incluidos en los valores de Y, entonces se tiene q 
cumplir que Z depende funcionalmente de X. 
Si X  Y ⊆ Z { X  Y, X  Z} 
Esta propiedad se puede demostrar a través de los axiomas de Armstrong: 
Aplicando la propiedad reflexiva: YZ  Y 
YZ  Z
Mediante la propiedad transitiva: X  Y 
X  Z 
De esta propiedad se desprende que se puede descomponer una dependencia 
funcional X  { A1, A2,..., An } en un conj.de dependencias { X  A1, X  A2, ... , X  An} 
REGLAS DE INFERENCIA
e) Unión: Si Y depende funcionalmente de X y se cumple q Z está fcionalmente
determinada por X, entonces se verifica q Y y Z dependen funcionalmente de X. 
Si { X  Y, X  Z } X  YZ 
Demostración: 
Por aumentación: X  Y ==> X ⊆ X  Y ⊆ X X  YX 
X  Z ==> YX  YZ 
Con las nuevas dependencias por transitividad ==> X  Y
Esta propiedad es la contraria a la proyección, permite combinar un conj. de 
dependencias funcionales { XA1, XA2,..., XAn } en 1única dependencia funcional 
X  { A1, A2,..., An }
f) Pseudotransitiva: Si { X  Y, WY  Z } WX  Z
Demostración: Por aumentación X  Y ==> WX  WY 
Como WY  Z, aplicando propiedad transitiva ==> WX  Z 
X desaparece ya que está 
Incluida en sí misma
REGLAS DE INFERENCIA
CLAUSURA DE X BAJO F: Sea X 1conj.de atributos y F un conj.de dependencias 
fcionales con X a la izquierda. La clausura de X bajo F, X* es el conj.de atributos fcionalmente
dependientes d X bajo F más las depend.inferidas de F. Algorit.d la clausura de X bajo F, X* o X+:
El valor inicial q toma X* está formado x todos los atributos de X, a continuación, a través de las 
reglas de inferencia transitiva, proyección y unión se van añadiendo nuevos atributos a X* 
apoyándose en las dependencias funcionales de F. 
X*:=X 
Repeat
Antiguo X*:=X*; 
Por cada dependencia funcional Y  Z do 
If Y ⊆ X*:then X*:=X* Z (ó X*:=X* U Z)
Until ( antiguo X* = X*); 
X+ := X 
repetir 
viejoX+ := X+; 
para cada df Y -> Z en F hacer 
si Y ⊆ X+ entonces X+ := X+ U Z; 
hasta que (viejoX+ = X+); 
SUPERCLAVE
Se dice q 1conj.de atrib.de 1relación es superclave si y solo si ese conj.de atributos 
determina a todos lo demás, es decir, si dicho conj. de atrib.determina unívocamente 
c/tupla de la relación. Una superclave de R = {A1, …, An} es un conj.de atributos S ⊆ R tal q 
no existen 2 tuplas t1 y t2 en ningún r tal que t1[S] = t2[S].
CLAVE O CLAVE CANDIDATA
Dada 1relación R = { A1, A2,..., An }, se dice q 1superclave de la relación es clave o clave 
candidata si es superclave mínima, es decir, si no existe ningún subconj.de atributos de 
dicha superclave del cual dependan fcionalmente todos los demás atributos de la relación. 
Cuando existen varias claves candidatas, se elige 1de ellas como clave primaria de la 
relación, denominándose al resto claves secundarias. 
ATRIBUTO PRIMARIO
Se dice q 1atrib.es primario si pertenece a alguna de las claves candidatas de la relac.tipo.
Ej: AE determinan a todos los demás atributos de la relación, por lo tanto es superclave, 
además es superclave mínima ya q ni A ni E determinan a todos los atributos, de ahí q tanto 
D como AE son claves candidatas
NORMALIZACIÓN 
Es un proceso reversible mediante el q se realiza 1descomposición progresiva de 
1conj.de relaciones dado en sucesivos conj.caracterizados x presentar relaciones c/vez 
+sencillas y regulares, alcanzando la estructura óptima p/su implementación, gestión y 
explotación desde diferentes futuras aplicaciones. 
“El objetivo de la normalización es eliminar las anomalías detectadas en 1 esquema 
relacional de 1BD cuando éste presenta una estructura no satisfactoria.” 
Los principales problemas que se pueden presentar en un esquema relacional son: 
- Existencia de Réplicas: Cierta información puede aparecer duplicada innecesariamente, 
con el consiguiente desaprovechamiento del espacio de almacenamiento. 
- Anomalías de actualización: Como consecuencia de la existencia de información 
redundante, 1operación de actualización puede llevar a un estado inconsistente de la BD. 
- Anomalías de Inserción: Puede resultar imposible añadir nueva información en la BD. 
- Anomalía de Borrado: Eliminar información puede desencadenarla pérdida no deseada de 
otro tipo de información. 
NORMALIZACIÓN 
El proceso de normalización parte de 1esquema relacional q contiene todos los 
atributos (y probablemente anomalías ) y de forma interactiva se va descomponiendo en 2 o 
+ relaciones q se encuentran en una Forma Normal (FN) superior. “Se dice que 1relación está 
en una FN cuando satisface el conj. de restricciones impuestas p/dicha forma.” 
Las ventajas de la Normalización de datos: 
- Facilidad de uso: Los datos se encuentran agrupados en tablas que identifican claramente 
un objeto o una relación. 
- Facilidad de gestión: Los lenguajes manipulan la información de forma sencilla mediante 
operaciones de álgebra y cálculo relacional aplicadas sobre las tablas. 
- Integridad: Las interrelaciones establecidas entre elementos de diferentes tablas permiten 
asegurar la integridad de la información almacenada. 
- Mínima redundancia: La información no aparece duplicada innecesariamente dentro de 
las diferentes estructuras constituyentes de la Base de Datos. 
- Máximo rendimiento de las aplicaciones: Cada aplicación únicamente “ve” aquella parte 
de la información que le sirve de utilidad.
NORMALIZACIÓN 
La descomposición de 1esquema relacional R(A,F), donde A es el conj.de atrib.q lo 
constituyen y F el conj.de depend.fcionales definidas sobre dichos atrib., es la sustitución de 
dicho esquema x 1colección p ={R1,R2 ,...,Rn } subconj.de R, de forma q se verifica: R= R1, R2, 
R3, ..., Rn. P/q1relación r(R) se pueda descomponer en 1conj. de p relaciones se deben cumplir:
1) Preservar el contenido de la relación
Toda información q aparezca en R, debe aparecer en p. Esta propiedad puede obtenerse 
imponiendo las sig. condiciones: 
- La unión de todos los atrib.de las p relaciones da el conj.de atributos de la relación R. 
R(A,F) ==> p= { R1 (A ,F ), R2 (A ,F ),...,R3 (A ,F ),}
A = A1, A2, ... An
- En c/relación Rn, p debe ser 1proyección de R de tal forma q R pueda crearse uniendo 
todos los Rn. 
NORMALIZACIÓN 
2) Preservar el conjunto de dependencias 
Las depend.fcionales F son prop.inherentes al esquema relacional R(A,F). Imponer q éstas se 
mantengan, equivale a desear q todas las depend.fcionales q s verifican en R, se cumplan en p. 
“Estas restricciones se pueden englobar diciendo q, al hacer la descomposición no se debe 
perder ningún atributo ni ninguna dependencia.” 
3) Carácter normal de las relaciones 
La 3ra.prop.q se desea cumplir es q cuando se construye un esquema relacional éste debe estar 
en FN. “Las FN son 1conj.de prop.deseables p/los esquemas relacionales. Al proceso de 
descompos.de 1relación tipo R en esquemas p={R} q estén en FN se denomina Normalización”. 
En 1970 Codd definió la 1ra., 2da. y 3ra. FN (INF, IINF, IIINF respectivamente). Boyce y Codd en 
1974 definieron 1versión mejorada de la IIINF, conocida como BCNF ( Boyce-Codd Normal 
Form), ésta fue depurada con la definición de la 4ta, IVNF, (Fagin 1977) y 5ta, VNF, (Fagin 1979). 
“El proceso de descomposición de 1relación en otras no estriba únicamente en 1
normalización, sino además se debe preservar en todo momento el contenido de la BD y sus 
dependencias fcionales.” En ocasiones la optimización del esquema conceptual p/determinar 
la forma de almacenamiento de los datos puede dar lugar a una des-normalización. 
PRIMERA FORMA NORMAL: INF 
1 relación está es INF si no contiene atributos compuestos, ni multivaluados, ni 
relaciones anidadas. Es decir, 1relación está en INF si y solo sí los valores q componen c/u de los 
atributos de 1tupla son atómicos. Si 1relación no cumple estas restricc.se debe normalizar xq: 
- Falta 1espacio en el campo p/los valores q se desean almacenar (desaprovechando espacio 
cuando existen pocos valores). Esto sucede xq p/c/u de los atributos no atómicos se reserva el 
espacio necesario p/almacenar el máximo nro de valores q se estima q puede tomar un atributo 
- Dificultad de tratamiento p/operaciones de inserción, actualización y borrado. 
a) ELIMINACIÓN DE ATRIBUTOS MULTIVALUADOS: P/eliminar 1atributo multivaluado se puede:
 El atributo multivaluado pasa a ser monovaluado y forma parte de la clave: esta postura no es 
aceptada ya q aunque se elimine el atributo multivaluado, sigue existiendo redundancia.
 Se crea una relación auxiliar formada por la clave de la entidad y el atributo multivaluado:
esta es la postura acertada ya q se consigue eliminar información redundante. 
PRIMERA FORMA NORMAL: INF 
X Ej.en la sig.relación se encuentra diferentes tipos de materiales existentes en 1 
ferretería, c/material tiene 1código q lo identifica, distintas dimensiones y1pequeña descripción. 
Esta relación no se encuentra en INF ya q el atributo 
Dimensiones tiene varios valores en 1misma tupla. 
P/pasar a 1NF se deben realizar los sig.pasos:
1º Se localizan los atributos q construyen la Clave primaria de la relación: Cod_Mat. 
2º Se descompone la relación realizando una proyección:
a) Se crea 1relación con la clave y los atributos monovaluados y 
simples. Dicha relación permanece con el nombre q identifica a la 
relación a normalizar.
b) Se crea 1nueva relación x c/u de los atributos múltiples, estando 
formada x la clave de la relación y dicho atributo. La clave de esta 
nueva relación proyectada estará formada por ambos atributos
PRIMERA FORMA NORMAL: INF 
b) ELIMINACIÓN DE RELACIONES ANIDADAS: se crea 1relación auxiliar formada x la 
clave de la entidad dueña y la relación anidada
Si se define 1relación p/la información anterior, varios de los dominios serán no atómicos. 
• Autores: 1libro puede tener vs.autores. Si s desea hallar todos los docum.de los cuales su autor 
es Santos, hay interés en 1parte del elemento del dominio «conj.de autores» (Elemento indivisibl) 
• Palabras clave: si se guarda 1conj.de palabras clave de c/docum.se espera poder recuperar 
todos los docum.cuyas claves incluyan 1ó vs.de las palabras clave especificadas. El dominio 
de la lista de palabras clave no es atómico.(Elem.Multival., ya q incluye 1dominio tipo “conj”) 
• Editorial: a diferencia de palabras clave y autores, editorial no tiene un dominio de tipo conj. 
Editorial consta de los subcampos nombre y sucursal. Esta manera de considerarlo hace q el 
dominio de editorial no sea atómico (Elemento Multivaluado, incluye 1relación anidada). Se 
crea 1relación con la clave primaria (Cod) y los atributos q son parte de la relación anidada 
(nombre de la editorial y sucursal) 
X ej. Si p/c/libro de Biblioteca se 
almacena la siguiente información: 
SEGUNDA FORMA NORMAL: IINF
La IINF se encuentra basada en el concepto de dependencia funcional total. 
Dependencia funcional total: 1dependencia funcional XY es 1dependencia 
fcional total si al eliminar un subconj.de atributos A de X, deja de cumplirse la depend. fcional:
X Y: A X / X - {A} no determina Y 
Dependencia funcional parcial: 1dependencia funcional XY es 1dependencia 
funcional parcial si existe 1subconj.de X q determina a Y. 
X  Y : A X / X – {A}  Y 
1 relación está en 2NF si y solo sí está en INF y todo atributo que no pertenece a la clave 
primaria tiene una dependencia funcional total con respecto de la clave. 
“Esta FN únicamente se considera si la clave primaria está compuesta por 2ó+ atributos, 
Si la relación está en INF y la clave primaria está formada por 1único atributo se puede 
asegurar q la relación se encuentra en IINF”. 
SEGUNDA FORMA NORMAL: IINF Algorit.de transformación de INFIINF 
Para pasar de 1NF a 2NF se deben eliminar todas aquellas dependencias fcionales
parciales con respecto de la clave. P/ello se efectúan las sig.proyecciones: 
1º Se crea 1relac.formada x la clave primaria +todos los atrib.q dependen totalmente de ella. 
2º Se crea 1nueva relac.auxiliar formada x los atrib.determinantes d la clave primaria + los atrib. 
q dependen fcionalmente de ellos. La clave d la relac.esta formada x el conj.de atrib.determin.Por ej.dada la relación EMPL_PROY donde s tiene información sobre los empleados 
de1empresa. C/u de las tuplas de la relación contiene el nombre (Nomb_E) y nro de seguridad 
social (NSS) de 1empleado, número (Num_P) y nombre (Nomb_P) de 1proyecto en el q trabaja, 
así como el nro.de horas (Horas) que dicho empleado dedica c/semana al proyecto. 
SEGUNDA FORMA NORMAL: IINF Transformación de INF a IINF
Como se puede observar, existe un subconj.de
la clave q determina funcionalmente a otros 
atributos de la relación: 
{ NSS, Num_P }  Horas 
Num_P  { Nomb_P, Ciudad_P}
NSS  Nomb_E
{ Nomb_P,situ_P} y {Nomb_E} son conj.de atrib. q 
presentan 1dependencia fcional parcial con 
respecto de la clave, p/q la relación aparezca 
en 2NF, se deben eliminar estas dependencias 
parciales creando, x c/dependencia parcial, 
1nueva relación auxiliar formada x el atributo 
determinante y el conj. de atributos q dependen 
funcionalmente de él.
TERCERA FORMA NORMAL: IIINF 
La IIINF está basada en el concepto de dependencia transitiva. 
Depend.transitiva: Sea 1depend.fcional X  Y en 1relación R= {A1,A2,…,An}, se dice 
q es 1 depend.transitiva si existe 1conj.de atributos Z de la relación R no pertenecientes a la 
clave de forma q se verifica : X  Z, Z Y y además si Z no determina a X e Y no determina a X. 
“1 relación está en IIINF si y solo sí está en IINF y no existen atributos no primarios 
transitivamente dependientes de c/posible clave de la relación.” 
Esto significa q 1atributo no primario únicamente debe conocerse a través de la clave 
primaria o de 1clave candidata de la relación, pero nunca x medio de otro atrib.no primario. 
Algoritmos de transformación de IINF  IIINF 
1º Sea una dependencia funcional X Y, definida en R(A,F), donde X e Y son disjuntos y no 
son clave ni forma parte de ninguna clave candidata de R. 
2º Se obtienen las proyecciones: R1 = Proy ( X,Y ) 
R2 = Proy ( A – Y )
TERCERA FORMA NORMAL: IIINF Algorit.de transform.de IINF  IIINF 
Siendo A el conj.de atributos q constituyen la relación R. P/normalizar 1relación q 
está en IINF y en la q existen atributos transitivamente dependientes de la clave: 
- Se crea 1nueva relación R2 con la clave y aquellos atributos dependientes de la clave pero 
q no son transitivamente dependientes de ella ni de ninguna clave candidata. 
- Otra relación R1 con los atributos transitivos y los atributos q los determinan. 
Por ej. en la relación EMPLEADOS se observa 1dependencia transitiva, con respecto de la 
clave, del conj.de atributos formado por { Nom_D) NSS_Jef }. 
P/q la relación pase a IIINF se 
debe normalizar, descomponiéndola 
p/ello en 2relaciones, 1 formada x el 
atrib.determinante Num_D y aquello q 
dependen funcionalmente de él {Nomb_D, 
NSS_Jef}, y otra formada x la clave y 
aquellos atributos q no dependen de 
forma transitiva de ella. 
FORMA NORMAL DE BOYCE-CODD: BCNF 
“1relac.está en BCNF si y sólo si está en IIINF y todo determinante es clave candidata” 
Es decir, todo conj.de atrib.no contenidos en la clave q determinan a algún atributo, debe 
determinar a todos los demás. 
La definición de BCNF engloba la IIINF ya q las dependencias transitivas existen a través de 
atributos secundarios q no son clave. 
BCNF se creó p/evitar los casos anómalos q no se resolvían con la IIINF y q aparecen cuando 
a partir de 1atrib.no primario se conoce parte de la clave primaria o de 1clave candidata. 
“Si las claves están formadas por un solo atributo y la relación se encuentra en IIINF se 
puede asegurar que también está en BCNF.” 
FORMA NORMAL DE BOYCE-CODD: BCNF Algoritmo de paso de IIINF a BCNF
Si 1relación está en IIINF y s detecta algún atrib.determinante (del cual depende 
fcionalmente otro atrib) q no es clave candidata, s debe normalizar la relac.descomponiendo:
1. 1 relac.formada x el atributo determinante y aquellos q dependen funcionalmente de él. 
2. Otra formada x la clave y el resto de los atributos incluidos los determinantes. 
El algorit.de descomposición q se aplica a 1relación q no está en BCNF es el siguiente: 
1- Sea la dependencia funcional X  Y, definida en R(A,F), donde X e Y son disjuntos, X es un 
atributo no primario e Y forma parte de la clave primaria o de 1clave candidata. 
2- Se realizan las siguientes proyecciones: R1= Proy ( X,Y ) 
R2= Proy ( A – Y ) 
X ej.se dispone de 1relación con la información referente a un proveedor, del cual se conoce 
un código que lo identifica (Cod_Pro), tipo del material q suministra (Cod_Mate), nombre del 
almacén al q provee (Almacen) y Ciudad en la q se encuentra dicho almacén. 
FORMA NORMAL DE BOYCE-CODD: BCNF Algoritmo de paso de IIINF a BCNF
PROVEEDOR Cod_Pro, Cod_Mate, Almacen, Ciudad 
En esta relación se encuentra definidas las siguientes dependencias funcionales: 
{ Ciudad, Cod_Mate }  { Cod_Pro, Almacen } 
{ Almacen }  { Ciudad } 
{ Cod_Pro }  { Cod_Mate, Almacen } 
Calculando la clausura de c/u de los conj.de atributos determinantes se puede observar q 
tanto { Cod_Pro } como { Ciudad, Cod_Mate } son claves candidatas. 
Se puede asegurar q la relación se encuentra en IIINF ya q en la relación Almacen  Ciudad, 
el atributo (Almacen) forma parte de 1clave candidata(Cod_Pro). 
“Sin embargo, como Almacen (atributo determinante de Ciudad ) no forma parte de ninguna 
clave la relación no se encuentra en BCNF y es preciso normalizar.”