Normalizacion de Base de Datos

TEMA 6

NORMALIZACION

1. Teorıa de la Normalizacion . . . . . . . . . . . . . . . . . . . . 2

2. Dependencia funcional . . . . . . . . . . . . . . . . . . . . . . . . 7

3. Formas normales de Codd (1NF, 2NF, 3NF) . . 14

4. Forma Normal de Boyce-Codd (BCNF) . . . . . . . 38

5. Cuarta Forma Normal (4NF) . . . . . . . . . . . . . . . . . 51

6. Quinta Forma Normal (5NF) . . . . . . . . . . . . . . . . .69

7. Proces de Normalitzacio . . . . . . . . . . . . . . . . . . . . . 73

1

Teorıa de la Normalizacion

• Reglas de definicion de relaciones en una BD rela-cional.

• Importante tenerlas en cuenta en la etapa de disenode la BD.

Diseno de la BD:

– Interesan propiedades que siempre se cumplan

⇓CABECERA

– No interesan propiedades que solo sean ciertasen un momento determinado

⇓CUERPO

2

• Permite detectar ciertas propiedades no deseablesen las relaciones y define metodos para convertirestas relaciones en formas mas tratables.

Ejemplo: Base de Datos S, SP, P

Suposemos que sacamos el atributo CIUTAT de S y lo ponemosen SP (relacion SP2).

SP2: S# CIUTAT P# CANT

S1 Londres P1 300S1 Londres P2 200S1 Londres P3 400S1 Londres P4 200S1 Londres P5 100S1 Londres P6 100S2 Paris P1 300S2 Paris P2 400

Atributo CIUTAT relacionado a suministrador↓

Redundancia en SP2: Peligro de inconsistencia si se intro-duce S1 con CIUTAT=’Atenas’ en SP2

⇓

Atributos han de estar asociadossemanticamente en relaciones.

• Normalizacion: sucesivas reducciones (proyecciones)de un conjunto de relaciones hasta obtener un nuevoconjunto de relaciones que cumplen ciertas restric-ciones.

↓basada en

FORMAS NORMALES

3

FORMAS NORMALES

• Conjunto de restricciones sobre las relaciones.

• "Relacion esta en una Forma Normal"↓

Si relacion satisface restriccciones de la Forma Nor-mal

• Diferentes formas normales relacionadas por inclusion(nNF cumple (n− 1)NF . . . 1NF)

– CODD (1972): Definicion 1NF, 2NF y 3NF.

– BOYCE-CODD (1974): Definicion forma normal quemejora la 3NF de Codd

↓FORMA NORMAL DE BOYCE-CODD (BCNF)

– FAGIN: Definicion 4NF (1977) y 5NF (1979)

4

IMPORTANTE EN DISENO:

Inicialmente, intentar definir relaciones en 5NF, que ga-rantizaran una buena estructura del esquema conceptualen BD relacional.

⇓

• No obstante, puede ser que en la BD no sea recomendablellegar a la 5NF.

↓Dependera del entorno de la aplicacion(pero como a mınimo la 1NF).

• Disenador ha de conocer las formas normales y los mecanis-mos para normalizar las relaciones.

↓

Normalizacion: Formalizacion del sentido comun.

5

PROCEDIMIENTO DE NORMALIZACION:

Procedimento mediante el cual una relacion con unaforma normal (por ej. nNF) se puede convertir en unconjunto de relaciones en forma mas optima ((n+1)NF).

RelacionnNF

proyeccion−→ k relaciones(n + 1)NF

↓Reduccion sucesiva de un conjunto de rela-ciones a una forma normal mas deseada.

Procedimiento reversible: No se pierde informacionen el proceso de normalizacion.

RelacionnNF

join←− k relaciones(n + 1)NF

⇓FORMAS NORMALES DE PROYECCION/REUNION

Tres primeras formas normales (1NF, 2NF, 3NF) basadasen el concepto de DEPENDENCIA FUNCIONAL

6

Dependencia funcional

Definicion: Dada una relacion R, el atributo Y de Rdepende funcionalmente del atributo X de R (R.Xdetermina funcionalmente R.Y ) denotado com

R.X −→ R.Y

⇐⇒un solo valor Y en R esta asociado a cada valor X enR. (X, Y pueden ser compuestos)

Ejemplo: BD S, SP, P

S.S# → S.SNOMS.S# → S.ZONAS.S# → S.CIUTAT

}S.S# → S.(SNOM,ZONA,CIUTAT)

P .COLOR 6→ P .PES(

P1 roja → PES=12P6 roja → PES=19

)

7

Si el atributo X es clave candidata (o clave pri-maria) en R:

↓Atributos Y en R han de depender funcional-mente de forma OBLIGATORIA de X (pordefinicion de clave candidata).


S.S# → S.(SNOM,CIUTAT,ZONA)

P .P# → P .(PNOM,COLOR,PES,CIUTAT)

SP .(S#,P#) → SP .CANT

8

Por la definicion de dependencia funcional (DF),

• No se obliga a que X sea clave candidata.

• Puede aparecer un valor de X en diferentes tuplas dentro deR, pero si existe DF, han de tener el mismo valor de Y .

↓ otra definicion de DF

Definicion: Dada una relacion R, el atributo Y de Rdepende funcionalmente del atributo X de R (X −→Y )

⇐⇒siempre que dos tuplas de R concuerden con su valor deX, han de concordar por fuerza con su valor de Y

Ejemplo: BD SP2

SP2.S# no es clave candidata en SP2 (no tiene valorunico), y en cambio,

SP2.S# −→ SP2.CIUTAT

9

Definicion: Dada una relacion R, el atributo Y de Rdepende funcionalmente DE FORMA COMPLETAdel atributo X de R

⇐⇒depende funcionalmente de X y no depende funcional-mente de ningun subconjunto de X (X mınimo)

Ejemplo: BD SP2

SP2.(S#,P#) −→ SP2.CIUTAT : DF NO COMPLETA,

pues

SP2.(S#) −→ SP2.CIUTAT : DF COMPLETA

•Si Y depende funcionalmente, pero no

de forma completa de X ⇒ X es compuesto

• Por defecto, a partir de ahora

DF ≡ DF completa

10

DIAGRAMA DE DEPENDENCIAS FUNCIONALES:Representacion de las dependencias funcionales de unarelacion. Grafo dirigido.


Usualmente, en una relacion,

• DF aparecen de claves candidatas, por definicion de clavecandidata. No se pueden eliminar estas DF.

• Otras flechas (no sobre claves candidatas), pueden dar pro-blemas.

⇓

Normalizacion: Eliminar flechas que no salen de clavescandidatas.

11

Observaciones:

• DF: Concepto semantico. Crear DF significa en-tender que significan los atributos

↓ Ejemplo:

DF S.S# −→ S.CIUTAT implica

– Restriccion en el mundo real: cada proveedor esta situadoen una sola ciudad.

– Restriccion anterior ha de cumplirse en la BD.

– Para garantizar su cumplimiento, se ha de especificar enel esquema conceptual para que el DBMS controle quese cumpla.

– Para especificar restriccion en esquema conceptual⇓

declarar DF

• DF: Restriccion de integridad. Especificarlo enun lenguaje para el DBMS.

CREATE INTEGRITY RULE SCDFCHECK FORALL SX FORALL SY(IF SX.S# = SY.S# THEN SX.CIUTAT=SY.CIUTAT);

≡S.S# −→ S.CIUTAT

12

Observaciones:

• Restricciones referenciales tienen fuerte relacion conDF.

SPS#−→ S ⇒ SP.S# −→ S.S#

↓Atributos de clave externa tienen DF conatributos de la relacion referenciada.

↓DF entre atributos de diferentes relaciones

(RESTRICCIONES INTERRELACIONALES)

• DF representan interrelaciones de varios a uno.

SP.S# → S.CIUTAT

⇓{

Un proveedor en una ciudad: 1 → 1Muchos proveedores en una ciudad: n → 1

13

Formas normales de Codd

(1NF, 2NF, 3NF)

Suposicion para las formas normales de Codd: Todarelacion tiene una sola clave candidata.

Def. ATRIBUTO NO CLAVE: Cualquier atributo queno participa en la clave primaria de la relacion.

Def. ATRIB. MUTUAMENTE INDEPENDIENTES:Dos o mas atributos en que ninguno de ellos de-pende funcionalmente de los otros.

Puede actualizarse un atributo sin afectar a losotros.


P# −→PNOMCOLORPESCIUTAT

}* mutuamente independientes entre sı* dependientes de CP P#

14

1NF:

”Una relacion esta en PRIMERA FORMA NORMAL(1NF)

⇐⇒todos los dominios simples contienen valores

atomicos.”

Problemas con relaciones solo en 1NF:↓

Ejemplo: Relacion PRIMERA(S#,ZONA,CIUTAT,P#,CANT).

Diagrama Funcional:

• Atributos no clave NO son mutuamente independentes(CIUTAT → ZONA)

• Atributos no dependientes completamente de la clave primaria(CIUTAT,ZONA dependientes de S#, no de P#).

15

PRIMERA: S# CIUTAT ZONA P# CANT

S1 Londres 20 P1 300S1 Londres 20 P2 200S1 Londres 20 P3 400S1 Londres 20 P4 200S1 Londres 20 P5 100S1 Londres 20 P6 100S2 Paris 10 P1 300S2 Paris 10 P2 400S3 Paris 10 P3 200S4 Londres 20 P2 200S4 Londres 20 P4 300S4 Londres 20 P5 400

Redundancias (ciutat proveedor,zona proveedor) provo-can

ANOMALIAS DE ACTUALIZACION↓

Problemas con las tres operaciones:

INSERT: No podemos insertar datos de un proveedordeterminado hasta que no haga una entrega.

(S#,P#) clave primaria ⇒ P#=NULL si 6 ∃ entrega

DELETE: Si eliminamos la ultima tupla de un prove-edor, se elimina la entrega y perdemos los datos delproveedor.

UPDATE: Si cambiamos de ciudad a un proveedor,hemos de cambiar todos los valores de ciudad delas tuplas del proveedor.

Ejemplo: Modificar la ciudad del suministrador S1.

16

SOLUCION: Dividir la relacion PRIMERA en dos rela-ciones:

1. SEGONA(S#,CIUTAT,ZONA)

2. SP (S#,P#,CANT)

Diagrama Funcional:

17

PRIMERA: S# CIUTAT ZONA P# CANT

S1 Londres 20 P1 300S1 Londres 20 P2 200S1 Londres 20 P3 400S1 Londres 20 P4 200S1 Londres 20 P5 100S1 Londres 20 P6 100S2 Paris 10 P1 300S2 Paris 10 P2 400S3 Paris 10 P3 200S4 Londres 20 P2 200S4 Londres 20 P4 300S4 Londres 20 P5 400

SEGONA: S# CIUTAT ZONA

S1 Londres 20S2 Paris 10S3 Paris 10S4 Londres 20S5 Atenas 30S6 Londres 20

SP: S# P# CANT

S1 P1 300S1 P2 200S1 P3 400S1 P4 200S1 P5 100S1 P6 100S2 P1 300S2 P2 400S3 P3 200S4 P2 200S4 P4 300S4 P5 400

18

• Se eliminan los problemas anteriores (INSERT,DELETE, UPDATE).

• Solucion adoptada: Eliminar dependencias no com-pletas.

⇓

19

2NF:

”Una relacion esta en SEGUNDA FORMA NORMAL(2NF)

⇐⇒• Esta en 1NF.

• Todos los atributos no clave dependen fun-cionalmente (de forma completa) de laclave primaria.”

Observaciones:

• Relaciones SEGONA, SP estan en 2NF. PRIMERAno esta en 2NF.

↓Si relacion esta en 1NF, pero no en 2NF

⇓CLAVE COMPUESTA: Existe un atri-buto de la clave primaria no dependientede un atribut no clave.

20

• Toda relacion en 1NF puede REDUCIRSE a un con-junto equivalente de relaciones 2NF.

1NF → 2NF

REDUCCION:

– Sustituir 1NF por projecciones apropiadas en 2NF.

– PROCES REVERSIBLE: Relaciones 2NF unificadas en1NF mediante JOIN.

↓Descomposicion: PROYECCIONRecomposicion: JOIN

21

PRIMER PASO DE NORMALIZACION:

Realizar proyecciones para eliminar las dependencias fun-cionales no completas.

Sustituir relacion R por dos proyecciones R1, R2

R(A,B,C,D)PRIMARY KEY: (A,B)

R.A → R.D

⇒ NO en 2NF↓

Atributo D depende de A, node clave primaria (A,B).

⇓

R1(A,D)

PRIMARY KEY: (A)

D depende de clave primaria(A).

R2(A,B,C)

PRIMARY KEY: (A,B)FOREIGN KEY (A) REFERENCES R1

C depende declave primaria(A,B).

22

R = R1 JOIN R2

Descomposicion SIN PERDIDAS:

• No se pierde informacion en la proyeccion.

• Informacion en R → tambien en R1, R2

• Pero nueva estructura (R1, R2) puede contener in-formacion que no se podrıa representar en la original(R).

↓Ejemplo: Proveedor S5 de Atenas queno ha hecho ningun envio.

23

DEPENDENCIA FUNCIONAL TRANSITIVA

Siguiendo el ejemplo relaciones SEGONA y SP

Dependencia funcional transitiva:

a, b → c

S# → CIUTATCIUTAT → ZONA

}⇒ S# → ZONA

24

Dependencias funcionales transitivas pueden producirANOMALIAS DE ACTUALIZACION

INSERT: No podemos insertar informacion del tipo

"Ciudad C tiene un zona X"

hasta que no exista un subministrador situado en laciudad.

↓Mientras 6 ∃ proveedor → valor de clave primaria

S# a NULL

DELETE: Si eliminamos la unica tupla de una ciudaddeterminada, eliminamos la informacion de ciudady zona asociada a la ciudad.

Ejemplo: Si eliminamos la tupla S5 en relacion SEGONA, se

pierde la informacion que la zona de Atenas es 30.

UPDATE: La Zona de una ciudad dada aparece dife-rentes veces, uno por subministrador de la ciudad.

Si se cambia la zona de ciutat (Ejemplo: revisar lazona de Londres de 20 a 30),

• hay que revisar relacion SEGONA hasta encontrar todaslas tuplas de Londres y modificarlas, o bien

• se puede producir resultado inconsistente si DBMS nolocaliza inconsistencias.

25

Dependencias funcionales en la relacion SEGONA

Posibles descomposiciones:

1.a) S# → CIUTATb) CIUTAT → ZONA

2.a) S# → CIUTATc) S# → ZONA

3.b) CIUTAT → ZONAc) S# → ZONA

Cual ses la mejor descomposicion, y segun que crite-rios?.

↓BUENAS Y MALAS DESCOMPOSICIONES

26

BUENAS Y MALAS DECOMPOSICIONES

Proceso de reduccion: Diferentes formas de descom-poner una relacion.

Ejemplo: Relacion SEGONA con las dependencias fun-cionales


}⇒ DF transitiva

S# → ZONA

↓ 2 descomposiciones:

DESCOMP. A: SC(S#,CIUTAT)CZ(CIUTAT,ZONA)

DESCOMP. B: SC(S#,CIUTAT)SZ(S#,ZONA)

Proyecciones3NF sinperdidas

• Descomp. B menos satisfactoria que descomp. A.

• Inconveniente en descomp. B: No podemos insertar infor-macion de la zona de una ciudad determinada hasta que nohaya un proveeedor situado en la ciudad.

27

Descomp. A:

Proyecciones SC, CZ son INDEPENDENTES (es posibleactualizar una relacion sin tener que tocar la otra).



SC: S# CIUTAT

S1 LondresS2 ParisS3 ParisS4 LondresS5 AtenasS6 Londres

CZ: CIUTAT ZONA

Atenas 30Londres 20Paris 6 10 → 80Roma 50

↓SC JOIN CZ: S# CIUTAT ZONA

S1 Londres 20S2 Paris 80 ⇒ CIUTAT → ZONAS3 Paris 80 ⇒S4 Londres 20S5 Atenas 30S6 Londres 20

La reunion (JOIN) de las dos proyecciones despues de laactualizacion siempre dara la relacion SEGONA valida.

↓JOIN no podra incumplir las restricciones de DF derelacion SEGONA.

28

Descomp. B:

Proyecciones SC, SZ NO son INDEPENDENTES.



SC: S# CIUTAT

S1 LondresS2 ParisS3 ParisS4 LondresS5 AtenasS6 Londres

SZ: S# ZONA

S1 20S2 6 10 → 80S3 10S4 20S5 30S6 20

↓SC JOIN SZ: S# CIUTAT ZONA

S1 Londres 20S2 Paris 80 ⇒ CIUTAT 6→ ZONAS3 Paris 10 ⇒S4 Londres 20S5 Atenas 30S6 Londres 20

Es necesario controlar las actualizaciones de SC, SZ para garantizarla DF

SEGONA.CIUTAT → SEGONA.ZONA

↓Si dos proveedores tienen la misma ciudad, han detener la misma zona.

29

En la descomp. A, la RESTRICCION INTERRELA-CIONAL es la DF transitiva

S# → ZONA↓

y el cumplimiento de esta restriccion se consiguede forma automatica si se cumplen las RESTRIC-CIONES INTRARRELACIONALES


y el cumplimiento de estas restricciones intrarrelacio-nales se verifica segun la restriccion de unicidad de laclave primaria (S# para la relacion SC y ciudad paraCZ)


PROBLEMA: En la descomp. B, la DF

CIUTAT → ZONA

se ha convertido en una RESTRICCION INTERRELA-CIONAL

que no se puede garantizar a partir de las DF:

S# → CIUTATS# → ZONA

30

Substituir relacion SEGONA,

SEGONA[S#,CIUTAT]−→ SC(S#,CIUTAT)

SEGONA(S#,ZONA,CIUTAT) ←−

SC JOIN CZ

SEGONA[CIUTAT,ZONA]−→ CZ(CIUTAT,ZONA)

Eliminar dependencia funcional transitiva, quedando

31

3NF:

”Una relacion esta en TERCERA FORMA NORMAL(3NF)

⇐⇒• Esta en 2NF.

• Los atributos no clave dependen de manerano transitiva de la clave primaria.”

Observaciones:

• Falta de Atributos no clavedependencias transitivas ⇒ mutuamente independentes

• Relaciones CZ, SC estan en 3NF. SEGONA no estaen 3NF.

32

Mas informalmente,

3NF:

• ”Una relacion esta en TERCERA FORMA NOR-MAL (3NF)

⇐⇒

Atributos no clave son{

mutuamente independientesdependientes completamente de la CP”

• ”Una relacion esta en 3NF

⇐⇒En todo momento cada tupla esta formada por:

– Valor de clave primaria que identifica.

– Conjunto de cero o mas valores de atributos independien-tes entre sı.

33

SEGUNDO PAS DE NORMALIZACION:

Obtener proyecciones para eliminar dependencias tran-sitivas.

R(A,B,C)PRIMARY KEY (A)

R.B → R.C

=⇒

R1(A,B)

PRIMARY KEY (A)FOREIGN KEY (B)

REFERENCES R2

R2(B,C)

PRIMARY KEY (B)

⇐=R = R1 JOIN R2

Como saber si una descomposicion es buena (indepen-dente) o no?

↓NORMA PARA OBTENER

BUENAS DESCOMPOSICIONES

34

NORMA PER OBTENERBUENAS DESCOMPOSICIONES:

Obtener descomposiciones con proyecciones indepen-dientes.

Definicion: (demostrada por Risanen)

Las proyecciones R1, R2 de una relacion R son indepen-dientes

⇐⇒

1. ∀ DF en R se puede deducir logicamente de las DFen R1, R2.

2. Los atributos comunes de R1, R2 forman una claveprimaria de al menos una de las dos relaciones.

35

Ejemplo: Descomposicion A

SC(S#,CIUTAT) CP: S# S# → CIUTATCZ(CIUTAT,ZONA) CP: CIUTAT CIUTAT → ZONA

Relacions SC, CZ son INDEPENDIENTES:

1.

S# → CIUTAT : SC

CIUTAT → ZONA : CZ

S# → ZONA : DFtransitiva

∀ DF en SEGONAse puede deducir deR1 y R2

2. CIUTAT (atributo comun de CZ, SC) es clave pri-maria de al menos una de las dos relaciones (CZ).

36

Ejemplo: Descomposicion B

SC(S#,CIUTAT) CP: S# S# → CIUTATSZ(S#,ZONA) CP: S# S# → ZONA

Relaciones SC, SZ NO SON INDEPENDIENTES:

1.

S# → CIUTAT : SC

S# → ZONA : SZ

} DFCIUTAT → ZONA no

deducible apartir de estas DF

2. S# (atributo comun de SC, SZ) es clave primariade al menos una de las dos relaciones (SC).

⇓Descomposicion B NO ES CORRECTA

37

Forma Normal de Boyce-Codd(BCNF)

Aparece para resolver los problemas existentes en rela-ciones que estan en 3NF donde:

• Hay varias claves candidatas

• Claves candidatas son compuestas

• Claves candidatas se solapan (tienen atributos comunes)

↓Si no se verifican estas condiciones, BCNF ≡ 3NF

Definicion: Un conjunto de atributos X de R es undeterminante

⇐⇒∃ un conjunto de atributos Y de R t.q. X → Y

38

BCNF:

”Una relacion esta en la FORMA NORMAL DEBOYCE-CODD (BCNF)

⇐⇒

todo determinante es clave candidata”.

39

Observaciones:

• Unicos determinantes son las claves candidatas.

• Las unicas flechas en el diagrama de dependenciason las que salen de las claves candidatas (no solode las claves primarias-CP).

• BCNF no hace referencia a la 1NF, 2NF ni a la DFtransitiva.

• BCNF es una restriccion mas fuerte que la 3NF.

• Toda relacion puede descomponerse sin perdidas enun conjunto equivalente de relaciones BCNF.

40

Ejemplos:

Relacion PRIMERA(S#,ZONA,CIUTAT,P#,CANT)

• No esta en 2NF

Det:

S# S# → CIUTATCIUTAT CIUTAT → ZONAS#,P# S#,P# → CANT

S#,P# → CIUTATS#,P# → ZONA

CC: { S#,P#

No esta enBCNF

Relacion SEGONA(S#,ZONA,CIUTAT)

• No esta en 3NF

Det:{

S# S# → CIUTAT,ZONACIUTAT CIUTAT → ZONA

CC: { S#

No esta enBCNF

41

Ejemplos: Relacion SP (S#,P#,CANT)

Det: { S#,P# S#,P# → CANT

CC: { S#,P#

}Esta en BCNF

Relacion SC(S#,CIUTAT)

Det: { S# S# → CIUTAT

CC: { S#

}Esta en BCNF

Relacion CZ(CIUTAT,ZONA)

Det: { CIUTAT CIUTAT → ZONA

CC: { CIUTAT

}Esta en BCNF

42

Ejemplo: Relacion S(S#,SNOM,ZONA,CIUTAT)

Ejemplo de dos claves candidatas sin atributos comunes.

Condiciones:

• Nombre de proveedor unico

• Atributos ZONA, CIUTAT independientes

(CIUTAT 6→ ZONA)

DF:

Todas las flechas existentes salen de claves candidatas

Det:{

S# S# → SNOM,CIUTAT,ZONASNOM SNOM → S#,CIUTAT,ZONA

CC:{

S#SNOM

Esta enBCNF

Importante: Hay que especificar SNOM como clave candidata paraque DBMS considere este atributo como tal para que verifique laBCNF:

RELATION S (S#,SNOM,ZONA,CIUTAT)PRIMARY KEY (S#)ALTERNATE KEY (SNOM)

43

Ejemplo: Relacion SP (S#,SNOM,P#,CANT)

Ejemplo de claves candidatas solapadas.

Condicio:

• Nombre de proveedor unico

DF:

CC:{

S#,P#SNOM,P#

Det:

{ S#,P# S#,P# → SNOM,CANTSNOM,P# SNOM,P# → S#,CANTS# S# → SNOMSNOM SNOM → S#

No esta enBCNF

44

SP S# SNOM P# CANT

S1 Salazar P1 300S1 Salazar P2 200S1 Salazar P3 400S1 Salazar P4 200S1 Salazar P5 100S1 Salazar P6 100S2 Jaime P1 300S2 Jaime P2 400S3 Bernal P3 200S4 Corona P2 200S4 Corona P4 300S4 Corona P5 400

Tabla con redundancia → Anomalıas de actualizacion

SP esta en 3NF porque todo atributo no clave {CANT} dependefuncionalmente de forma no transitiva de la clave primaria

S#,P# → CANT↓

3NF no pide dependencia completa a la clave primariapara un atributo que sea componente de alguna clavecandidata de la relacion. ↓

SNOM no depende completamente de S#,P#

S#,P# → SNOM : DF NO COMPLETA, pues

S# → SNOM

Solucion: Descomponer la relacion SP en dos PROYECCIONES:

• S(S#,SNOM) y SP (S#,P#,CANT)

• S′(S#,SNOM) y SP ′(SNOM,P#,CANT)

45

Proyeccion: S(S#,SNOM) y SP (S#,P#,CANT)

S :

Det:{

S# S# → SNOMSNOM SNOM → S#

CC:{

S#SNOM

SP :

{Det: { S#,P# S#,P# → CANT

CC: { S#,P#

Estan en BCNF

Proyeccion: S′(S#,SNOM) y SP ′(SNOM,P#,CANT)

S′ :

Det:{

S# S# → SNOMSNOM SNOM → S#

CC:{

S#SNOM

SP ′ :

{Det: { SNOM,P# SNOM,P# → CANT

CC: { SNOM,P#

Estan enBCNF

46

Ejemplo: Relacion EPA (Estudiante/Profesor/Asignatura)

Ejemplo del claves candidatas solapadas.

Condiciones:

• Un estudiante de una asignatura solo tiene un profesor paraella (e,a → p).

• Cada profesor da una unica asignatura (p → a).

• Una asignatura puede ser dada por mas de un profesor

(a 6→ p).

EPA e p a

Godia Enric Bases de DatosGodia Juanjo GraficosLacruz Enric Bases de DatosLacruz Martı Graficos

DF:

47

Esta en 3NF (no existe ningun atributo no clave)

CC:{

e,ae,p

Det:

{e,a e,a → pp p → ae,p e,p → a

No esta en BCNF

Anomalıas de actualizacion: Si eliminamos ”Lacruzestudia Graficos”, eliminamos tambien el hecho ”Martıensena Graficos”.

Solucion: Descomponer la relacion EPA en dos PROYEC-CIONES:

• EP (e,p) y PA(p,a)

EP e p

Godia EnricGodia JuanjoLacruz EnricLacruz Martı

PA p a

Enric Bases de DatosJuanjo GraficosMartı Graficos

Det: ∅CC: {e,p

}Esta enBCNF

Det: {p p → a

CC: {p

}Esta enBCNF

48

PROBLEMA: Relaciones EP, PA NO SON INDEPEN-DIENTES

DF en Relacion EPA DF en relaciones EP, PA

p → a p → ae,p → ae,a → p

e,a → p no puede deducirse de p → a

⇓Relaciones EP ,PA no pueden modificarse independien-temente.

• Si cambiamos de profesor a EP (cambiar profesor a alumno),hemos de cambiar el profesor a PA (cambiar profesor de assig-natura).

• Ejemplo: No podemos insertar ”Godia-Martı” en la relacionEP , pues Martı ensena Graficos y Godia ya tiene profesor deGraficos (Juanjo). Para saber esto ultimo hemos de consultarla relacion PA.

No siempre es posible descomponer una relacion en com-ponentes BCNF y componentes independientes de formaque se satisfagan a la vez.

↓Diremos que la relacion EPA es ATOMICA:si no puede ser descompuesta en relacionesindependientes.

49

Ejemplo: Relacion EAR (Estudiante/Asignatura/Ranking)

Ejemplo del claves candidatas solapadas.

Condicio:

• Dos estudiantes no pueden tener el mismo ranking (posicion)en la misma asignatura (no hay empates – a,r → e).

• Un estudiante no puede tener dos posiciones en el ranking deuna misma asignatura (e,a → r).

DF:

Det:{

e,a e,a → ra,r a,r → e

CC:{

e,aa,r

Esta en BCNF

En conclusion, BCNF

• elimina problemas de la 3NF.

• mas sencilla que la 3NF al no hacer referencia a la 1NF, 2NF,CP ni a DF transitivas.

50

Cuarta Forma Normal (4NF)

• Formulada por Fagin (1977)

• Concepto introductorio: Dependencias MultiValo-radas (DMV).

51

Ejemplo: Relacion CPT (Cursos/Profesores/ Textos)

Relacion no normalizada.

Condiciones:

• Cada tupla de la relacion contiene el nombre del curso + ungrupo repetitivo de profesores, + un grup repetitivo de textos.

• Para cada curso, n profesores y m textos.

• Cada profesor → n cursos.

• Cada texto → n cursos.

• Para cada curso se siguen los mismos libros, sea quien sea elprofesor.

CPT0 c p t

Base de Datos {Enric}{

DateRogers

}

Graficos{

JuanjoEnric

} {Hearn-BakerFoley-Van DamRogers

}

↓ pasada a 1NF

CPT c p t

Base de Datos Enric DateBase de Datos Enric Rogers

Graficos Juanjo Hearn-BakerGraficos Juanjo Foley-Van DamGraficos Juanjo RogersGraficos Enric Hearn-BakerGraficos Enric Foley-Van DamGraficos Enric Rogers

52

Observaciones:

• ∃ redundancias ⇒ Anomalıas de actualizacion Ejemplo: Siqueremos anadir un nuevo profesor de BD, hay que anadirdos tuplas nuevas, una para cada libro de texto.

• CPT

Det: ∅CC: {c,p,t

}Esta en BCNF

• Tupla (c, p, t): curso c puede ser impartido por profesor putilizando el libro de texto t.

↓Dado un curso c, ha de aparecer una tupla para cada combi-nacion texto/profesor:

⇓

si hay las tuplas (c,p1,t1) y (c,p2,t2)entonces tambien han de existir (c,p1,t2) y (c,p2,t1)

⇓REDUNDANCIA

Problema: Independencia entre profesores y textos.

Solucion: Descomponer la relacion CPT en dos PROYEC-CIONES:

– CP (c,p) y CT (c,t)

53

Proyecciones CP (c,p) y CT (c,t)

CP c p

Base de Datos EnricGraficos JuanjoGraficos Enric

CT c t

Base de Datos DateBase de Datos Rogers

Graficos Hearn-BakerGraficos Foley-Van DamGraficos Rogers

Propiedades:

• Relacion CP :Det: ∅CC: {c,p

}Esta en BCNF

• Relacion CT :Det: ∅CC: {c,t

}Esta en BCNF

• Descomposicion de la relacion CPT en las relaciones CP ,CTen base aDEPENDENCIAS MULTIVALORADAS (DMV)

↓

Generalizacion de las DF

∀ DF→6← DMV

54

Definicion: Dada una relacion R, con los atributosA, B, C, la dependencia multivalorada (DMV) entreA y B denotada como

R.A −→>> R.B

se cumple⇐⇒

el conjunto de valores de B correspondiente a un pardado (a : A, c : C) en R solo depende del valor de Ay es independiente del valor de C (A, B, C pueden sercompuestos).

55

Observaciones:

• Las dependencias multivaloradas pueden existir solo si la relaciontiene un mınimo de tres atributos.

• Dada una relacion R(A, B, C)

A −→>> B ⇒ A −→>> C

↓A −→>> B | C

Ejemplo: Relacion CPT

c −→>> p ⇒ c −→>> t

↓c −→>> p | t

• DF: DMV donde el conjunto de valores dependientes es 1.

• Problema a la relacion CPT : Presencia de DMV que no sonDF

↓

Proyecciones CP, CT no tienen DMV

↓ Teorema de Fagin determinacomo hacer esta sustitucion

Teorema de Fagin:

La relacion R, con atributos A, B, C se puede descomponersin perdidas en sus dos proyecciones R1(A, B) y R2(A, C)

⇐⇒se cumplen en R las dependencias multivaloradas

A −→>> B | C

56

4NF:

”Una relacion esta en CUARTA FORMA NORMAL(4NF)

⇐⇒• Esta en BCNF.

• Todas las dependencias multivaloradas enR son DF.”

57

Consideraciones:

• CPT no esta en 4NF (tiene una DMV que no esDF).

• Proyecciones CP, CT estan en 4NF (no tienen DMV).

• 4NF elimina estructura no deseada: las DMV.

• Fagin demuestra que siempre es posible llegar a la4NF

↓pero en algunos casos podrıa no ser conveniente

hacer la descomposicion

• Teorema de Risanen sobre proposiciones indepen-dents y DF, aplicable tambien sobre DMV

Dada una relacionR(A, B, C) con DF

A → BB → C

=⇒Es conveniente

descomponer relacionen proyecciones (A,B) y

(B,C)

↓ sobre DMV

Dada una relacionR(A, B, C) con DMV

A −→>> BB −→>> C

=⇒Es conveniente

descomponer relacionen proyecciones (A,B) y

(B,C)

58

Quinta Forma Normal (5NF)

• Hasta ahora, toda relacion es descomponible sinperdidas en 2 proyecciones

↓no todas pueden ser descomponibles en 2 proyecciones.

• Existen relaciones que pueden descomponerse sinperdidas en 3 o mas proyecciones.

Definicion: Dada una relacion R, esta es n-descom-ponible

⇐⇒la relacion puede descomponerse sin perdidas en n proyec-ciones, siendo n el mınimo numero de proyecciones enque puede descomponerse R sin perdidas.

Si n = 2 → relacion 2-descomponible.

59

Ejemplo: Relacion SPJ(S#,P#,J#)

Esta en 4NF (no tiene DF ni DMV).

SPJ S# P# J#

S1 P1 J2S1 P2 J1S2 P1 J1S1 P1 J1

SP S# P#

S1 P1S1 P2S2 P1

PJ P# J#

P1 J2P2 J1P1 J1

JS J# S#

J2 S1J1 S1J1 S2

SP JOIN PJ S# P# J#

S1 P1 J2S1 P1 J1S1 P2 J1

espuria → S2 P1 J2S2 P1 J1

PJ JOIN JS S# P# J#

S1 P1 J2S1 P2 J1S1 P1 J1

espuria → S2 P2 J1S2 P1 J1

(SP JOIN PJ)JOIN JS S# P# J#

S1 P1 J2S1 P1 J1S1 P2 J1S2 P1 J1

(PJ JOIN JS)JOIN SP S# P# J#

S1 P1 J2S1 P2 J1S1 P1 J1S2 P1 J1

60

• Relacion SPJ: Relacion 3-descomponible, pues pre-cisamos de 3 relaciones para recuperar SPJ

SPJ = (SP JOIN PJ) JOIN JS

• Propiedad 3-descomponible,

– en funcion de los valores especıficos en la relacion.

– como RESTRICCION INDEPENDIENTE DELTIEMPO.

61

RESTRICCION INDEPENDIENTE DEL TIEMPO

La proposicion ”SPJ equivale a la reunion (join) deSP,PJ,JS” implica

SI la pareja (S1,P1) aparece en SPY la pareja (P1,J1) aparece en PJY la pareja (J1,S1) aparece en JS

ENTONCES (S1,P1,J1) aparecd en SPJ.

↓(S1,P1) ∧ (P1,J1) ∧ (J1,S1) → (S1,P1,J1)

(S1,P1) ∧ (P1,J2) ∧ (J2,S1) → (S1,P1,J2)(S2,P1) ∧ (P1,J1) ∧ (J1,S2) → (S2,P1,J1)(S1,P2) ∧ (P2,J1) ∧ (J1,S1) → (S1,P2,J1)

↓ restriccio sobre relacion SPJ

SI (S1,P1,J2), (S2,P1,J1), (S1,P2,J1) aparecen en SPJENTONCES (S1,P1,J1) aparece tambien en SPJ.

↓

Si la restriccio se verifica en todo momento,

↓

• RESTRICCION INDEPENDIENTE DELTIEMPO

• RESTRICCION 3-D (3-Descomponible)

• RESTRICCION CICLICA

62

Definicion: Una relacion R es n-descomponible (paraalguna n > 2)

⇐⇒

satisface una restriccion cıclica n-D independiente deltiempo

63

Si relacion SPJ satisface una restriccion 3-D indepen-diente del tiempo, SPJ representa un hecho como

(a) PEPE suministra LLAVES INGLESAS

(b) En el proyecto EUREKA se utilizan LLAVES INGLESAS

(c) PEPE suministra piezas al proyecto EUREKA

↓ luego

PEPE suministra LLAVES INGLESAS al proyecto EUREKA

Observaciones:

• En condiciones normales, (a),(b),(c) 6→ (d)

⇓TRAMPA DE CONEXION

• Pero es cierto en este caso si se cumple la restric-cion 3-D

↓Restriccion 3-Dse satisface

⇐⇒la reunion de susproyecciones da larelacion principal.

↓ DEPENDENCIA DE REUNION (DR)

64

Definicion: La relacion R satisface la dependencia dereunion (DR)

∗(X, Y . . . Z)

⇐⇒R es igual a la reunion de sus proyecciones segun X, Y . . . Z,donde X, Y . . . Z son subconjuntos del conjunto de atri-butos de R.

65

Ejemplo: Relacion SPJ(S#,P#,J#)

Satisface la DR *(SP,PJ,JS) ⇒ se puede descomponer.

Dependencias de reunion: PresentanAnomalias de actualizacion

↓

(1) Ejemplo: Relacion SPJ(S#,P#,J#)

SPJ S# P# J#

S1 P1 J2S1 P2 J1

1. Si insertamos (S2,P1,J1)→ hemos de insertar (S1,P1,J1)

(S1,P1,J2) → (S1,P1) ∧ (P1,J2) ∧ (J2,S1)(S1,P2,J1) → (S1,P2) ∧ (P2,J1) ∧ (J1,S1)(S2,P1,J1) → (S2,P1) ∧ (P1,J1) ∧ (J1,S2)

(S1,P1,J1) ← (S1,P1) ∧ (P1,J1) ∧ (J1,S1)

2. Si insertamos (S1,P1,J1) 6→ hemos de insertar (S2,P1,J1)


(S2,P1,J1) ← (S2,P1) ∧ (P1,J1) ∧ (J1,S2)

66

(2) Ejemplo: Relacion SPJ(S#,P#,J#)

SPJ S# P# J#

S1 P1 J2S1 P2 J1S2 P1 J1S1 P1 J1

1. Se puede eliminar (S2,P1,J1) sin problemas, puesno afecta a las otras tuplas.


(S2,P1,J1) ← (S2,P1) ∧ (P1,J1) ∧ (J1,S2)

2. Si eliminamos (S1,P1,J1), hay que eliminar otra tu-pla


(S1,P1,J1) ← (S1,P1) ∧ (P1,J1) ∧ (J1,S1)

↓Si se elimina (S1,P1,J1), hay que eliminar alguna de lastres tuplas existentes para evitar que el cumplimientode las tres implique (S1,P1,J1), tupla que queremoseliminar.

↓PROBLEMA: Cual de las tres eliminamos?

67

TEOREMA DE FAGIN (pag. 56) se puede expresarcomo

R(A,B,C) sat-isface la DR*(AB,AC)

⇐⇒satisfacelas DMVA −→>> B|C.

Observacions:

• DMV es un caso especial de DR → DF es un casoespecial de DR.

• DR es la forma mas general posible de dependenciasiempre que se trabaje a partir de proyecciones /reunions.

↓DR es la dependencia mas alta

• Problema en la relacion SPJ: Relacion que in-cluye una DR que no es ni DMV ni DF.

68

5NF:

”Una relacion esta en QUINTA FORMA NORMAL(5NF)

⇐⇒toda dependencia de reunion en R es consecuencia de

las claves candidatas de R.”

69

Dependencia de reunion consecuencia de claves can-didatas:

Claves candidatas son atributos comunes de las relaciones de-scompuestas en la DR.

↓Ejemplo: Relacion S(S#,SNOM,ZONA,CIUTAT)

• Satisface la DR *((S#,SNOM,ZONA),(S#,CIUTAT)), pues

S=(S#,SNOM,ZONA) JOIN (S#,CIUTAT)↓

S# es clave candidata

• Satisface la DR *((S#,SNOM),(S#,ZONA),(SNOM,CIUTAT)),doncs

S=(S#,SNOM) JOIN (S#,ZONA) JOIN (SNOM,CIUTAT)↓

S#,SNOM son claves candidatas

– Relacion SPJ NOesta en 5NF

→satisface DR que no es conse-cuencia de la clave candidata deSPJ que es S#,P#,J#.

–RelacionesSP, PJ, JS estanen 5NF

→ no contienen ninguna DR

70

Observaciones:

• Toda relacion en 5NF ⇒ esta tambien en 4NF

↓DMV es un caso especial de una DR

• Toda relacion se puede descomponer sin perdidasen un conjunto de relaciones 5NF.

• Dada una relacion R, podemos saber si esta en 5NFsi conocemos

– las claves candidatas de R.

– todas las dependencias de reunion en R: Hay queencontrar cuales son provocadas por claves candidatas ycuales no.

↓Problema: Detectar DR que no sean DMV niDF no es facil, pues el significado intuitivo deuna DR no es sencillo de deducir.

71

Una relacion en 5NF:

• Relacion llbre de anomalıas que pueden eliminarsecon proyecciones.

• Unicas DR existentes en la relacion son consecuen-cia de las claves candidatas.

• Unicas descomposiciones validas son las basadas enclaves candidatas.

↓

cada descomposicion estara formada por una o masclaves candidatas

↓

Ejemplo: Relacion S(S#,SNOM,ZONA,CIUTAT)

Puede descomponerse sin perdidas de diferentes formas, ytodas las proyecciones seguiran incluyendo la clave candidata.

– *((S#,SNOM,ZONA),(S#,CIUTAT))– *((S#,SNOM),(S#,ZONA),(SNOM,CIUTAT))

72

Proceso de Normalizacion

Diseno de la Base de Datos basada en la tecnica dedescomposicion sin perdidas.

Dada una relacion R en 1NF y una lista de restricciones(DF,DMV,DR) aplicables a R,

↓reducir R de manera sistematica en un conjuntode relaciones mas pequenas equivalentes a Ry mas convenientes, mediante proyecciones delas relaciones obtenidas en el paso anterior, te-niendo en cuenta las restricciones sobre R.

73

PASOS:

1. Proyecciones de la relacion 1NF para eliminar DFno completas.

↓Resultado: Conjunto de relaciones 2NF

2. Proyecciones de las relaciones 2NF para eliminarDF transitivas.


3. Proyecciones de las relaciones 3NF para eliminar DFrestantes donde el determinante no sea una clavecandidata.

↓Resultado: Conjunto de relaciones BCNF

4. Proyecciones de las relaciones BCNF para eliminarDMV que no sean DF.


5. Proyecciones de las relaciones 4NF para eliminarcualquier DR que no sea consecuencia de las clavescandidatas.


74

PASOS 1-3: Pueden ser condensados en un unicopaso:

1-3. Proyecciones de la relacion original 1NF para eli-minar todas las DF en las cuales el determinanteno sea una clave candidata.

↓Resultat: Conjunto de relaciones BCNF

EN LA PRACTICA:

• A menudo es suficiente llegar hasta la BCNF, ocomo maximo a la 4NF.

• 5NF puede considerarse como un caso patologicoque pocas veces se producira.

75

Documents

Normalizacion de Base de Datos