UNIVERSIDAD NACIONAL DE LA MATANZA
DEPARTAMENTO DE INGENIERÍA
E INVESTIGACIONES TECNOLÓGICAS
INGENIERIA EN INFORMATICA
BASE DE DATOS
Clase práctica #4
Normalización
Ejercicios
de la
Guía
Ejercicio 20
Dado R(A,B,C,D,E,F) con F={AB→C, C→D, ABC→E, F→A, AB→FD, A→F }
1. Obtenga un cubrimiento minimal.
2. Normalizar a 3 FN
Dado R(A,B,C,D,E,F) con F={AB→C, C→D, ABC→E, F→A, AB→FD, A→F }
1- Descomponer a Derecha
f1= {AB→C, C→D, ABC→E, F→A, AB→F, AB→D, A→F}
2- Atributos redundantes lado Izquierdo
AB->C ABC->E AB->F AB->D
A+=AF A+=AF // AB+=ABCE A+=AF A+=AF
B+=B B+=B // B+=B // B es redundante! B+=B
C+=CD // C es redundante!
f2= {AB→C, C→D, AB→E, F→A, AB→D, A→F}
3- df Redundantes
AB+ en f2 - {AB->C} C+ en f2 - {C->D} AB+ en f2 - {AB->E} F+ en f2 - {F->A}
AB+=ABEFD C+=C AB+=ABCDF F+=F
Entonces AB->C NO es Redundante! Entonces C->D NO es Redundante! Entonces AB->E NO es Redundante! Entonces F->A NO es Redundante!
AB+ en f2 - {AB->D} A+ en f2 - {AB->D, A->F}
AB+=ABFCD A+=A
Entonces AB->D ES Redundante! Entonces A->F NO es Redundante!
FMIN= {AB→C, C→D, AB→E, F→A, A→F}
Ejercicio 20
R(A,B,C,D,E,F) y con FMIN= {AB→C, C→D, AB→E, F→A, A→F}
2. Normalizar a 3 FN
R(A,B,C,D,E,F) con F={AB→C, C→D, AB→E, F→A, A→F}
2- Obtener descomposición en 3FN
Claves Candidatas
A+=AF AB+=ABCDEF BCD+=BCD
B+=B BC+=BCD BCE+=BCED
C+=CD BD+=BD BDE+=BDE
E+=E BE+=BE …….
F+=FA BF+=BFACDE
CC= {AB, BF}
Forma Normal?
Fmin = {AB→C, C→D, AB→E, F→A, A→F} FNBC
FNBC 2FN FNBC 3FN 3FN
3FN
2FN
1FN
Está en 2FN ya que C→D no cumple con 3FN
Dado R(A,B,C,D,E,F) con F={AB→C, C→D, AB→E, F→A, A→F}
2- Obtener descomposición en 3FN
CC= {AB, BF}
R1 (ABCE) R2 (CD) R3 (FA) R4 (AF)
df1 {AB→C, AB→E} df2 {C→D} df3 {F→A} df4 {A→F}
CC: AB CC: C CC: F CC: A
FN? FNBC FN? FNBC FN? FNBC FN? FNBC
G = {df1 U df2 U df3 U df4} ====> F y G resultante son equivalentes. No hubo pérdida de Dependencias!
Ejercicio 17
Dado R(AOIVND) con F={ V → D, I → A, IV → N, A → O}
Indique si hay pérdida de información si descompone a R en:
2) R1(IVN), R2(IA), R3(VD), R4(IVO)
Dado R(AOIVND) con F={ V → D, I → A, IV → N, A → O}
Tableau Inicial V→D
A O I V N D A O I V N D
IVN b11 b12 a3 a4 a5 b16 IVN b11 b12 a3 a4 a5 b16
a6
IA a1 b22 a3 b24 b25 b26 IA a1 b22 a3 b24 b25 b26
VD b31 b32 b34 a4 b15 a6 VD b31 b32 b34 a4 b15 a6
IVO b41 a2 a3 a4 b45 b46 IVO b41 a2 a3 a4 b45 b46
a6
I→A IV → N
A O I V N D A O I V N D
IVN b11 b12 a3 a4 a5 a6 IVN a1 b12 a3 a4 a5 a6
a1
IA a1 b22 a3 b24 b25 b26 IA a1 b22 a3 b24 b25 b26
VD b31 b32 b34 a4 b15 a6 VD b31 b32 b34 a4 b15 a6
IVO b41
a1 a2 a3 a4 b45 a6 IVO a1 a2 a3 a4 b45
a5 a6
Ejercicios
de
Parciales
Ejercicio 1
Dado R(ABCDE) con F ={AB->CD, BDE->C, BC->A, A->E, E->C}
a)- Calcular Fmin
b)- Calcular todas las Claves Candidatas e indicar en que forma normal se encuentra R.
c)- Descomponer R en FNBC utilizando el algoritmo correspondiente.
R(ABCDE) con F ={AB->CD, BDE->C, BC->A, A->E, E->C}
1- Descomponer a Derecha
f1= {AB->C, AB->D, BDE->C, BC->A, A->E, E->C}
2- Atributos redundantes lado Izquierdo
AB->C AB->D BDE->C BC->A
A+=AEC A+=AEC B+= B C+=C
B+=B entonces B es redundante B+=B D+=D B+=B
E+=EC entonces B y D son redundantes
f2= {A->C, AB->D, E->C, BC->A, A->E}
3- df Redundantes
A+ en f2 - {A->C} AB+ en f2 - {AB->D, A->C} E+ en f2 - {E->C, A->C} BC+ en f2 - {BC->A, A->C}
A+=AEC AB+=ABDEC E+=E BC+=BC
Entonces A->C es Redundante! Entonces AB->D NO es Redundante! Entonces E->C NO es Redundante! Entonces BC->A NO es Redundante!
A+ en f2 - {A->E, A->C}
A+=A
Entonces A->E NO es Redundante!
FMIN= {AB->D, E->C, BC->A, A->E}
b- Calcular todas las Claves Candidatas e indicar en que forma normal se encuentra R.
R(ABCDE) con F ={AB->D, E->C, BC->A, A->E}
Claves Candidatas
A+=AEC AB+=ABCDE
B+=B BC+=BCAED
BD+=BD
BE+=BECAD
CC= {AB, BC, BE}
Forma Normal?
FNBC
Fmin = {AB->D, E->C, BC->A, A->E}
3FN
FNBC 3FN FNBC 3FN 2FN
1FN
Está en 3FN
Ejercicio 1
R (ABCDE) y Fmin = {AB->D, E->C, BC->A, A->E}
c)- Descomponer R en FNBC utilizando el algoritmo correspondiente.
Ejercicio 1 - Opción 1
Fmin = {AB->D, E->C, BC->A, A->E}
FNBC 3FN FNBC 3FN
R (ABCDE)
INFERENCIA
F = {AB->D, E->C, BC->A, A->E}
E -> C
1)- BC->A
2)- E->C
R1 (EC)
3)- BE->A
F1 = {E->C}
PseudoTransitividad entre
R’ (ABDE) 1y2
CC: E F = {AB->D, A->E, BE->A}
FN? FNBC
CC: {AB, BE}
A -> E
FN? 3FN
R2 (AE)
F2 = {A->E}
CC: A R3 (ABD)
FN? FNBC F3 = {AB->D}
CC: {AB}
FN? FNBC
Ejercicio 1 - Opción 2
Fmin = {AB->D, E->C, BC->A, A->E}
FNBC 3FN FNBC 3FN
R (ABCDE)
INFERENCIA
F = {AB->D, E->C, BC->A, A->E}
A -> E
1)- A->E
2)- E->C
R1 (AE)
3)- A->C
F1 = {A->E}
Transitividad entre
R’ (ABCD) 1y2
CC: A F = {AB->D, BC->A, A->C}
FN? FNBC
CC: {AB, BC}
A -> C
FN? 3FN
R2 (AC)
F2 = {A->C}
CC: A R3 (ABD)
FN? FNBC F3 = {AB->D}
CC: {AB}
FN? FNBC
Ejercicio 2
3) Dado el esquema de relación R(ABCDEF) F={BC→ A, A→ B, DE→ F, F→ E}
a) - Indicar en qué forma normal se encuentra
b) - Descomponer R en FNBC utilizando el algoritmo visto en clase.
R(ABCDEF) con F ={BC→ A, A→ B, DE→ F, F→ E}
1- Descomponer a Derecha
f1= {BC→ A, A→B, DE→F, F→E}
2- Atributos redundantes lado Izquierdo
BC->A DE->F
B+=B D+=D
C+=C E+=E
f2= {BC→ A, A→B, DE→F, F→E}
3- df Redundantes
BC+ en f2 - {BC->A} A+ en f2 - {A->B} DE+ en f2 - { DE->F} F+ en f2 - {F->E}
BC+=BC A+=A DE+=DE F+=F
Entonces BC->A NO es Redundante! Entonces A->B NO es Redundante! Entonces DE->F NO es Redundante! Entonces F->E NO es Redundante!
FMIN= {BC→ A, A→B, DE→F, F→E}
a) - Indicar en qué forma normal se encuentra
R(ABCDEF) con Fmin {BC→ A, A→B, DE→F, F→E}
Claves Candidatas
CD+=CD CDAE+=CDAEBF CDFE+=CDFE
CDA+=CDAB CDAF+= CDAFBE …….
CDB+=CDB CDAB+=CDAB
CDE+=CDEF CDBE+=CDBEAF
CDF+=CDFE CDBF+=CDBFAE
CC= {ACDE, ACDF, BCDE, BCDF}
Forma Normal?
FNBC
Fmin = {BC→ A, A→B, DE→F, F→E}
3FN
3FN 3FN 3FN 3FN 2FN
1FN
Está en 3FN
Ejercicio 2
R(ABCDEF) con Fmin {BC→ A, A→B, DE→F, F→E}
c)- Descomponer R en FNBC utilizando el algoritmo correspondiente.
Ejercicio 2 - Opción 1 Fmin = {BC→ A, A→B, DE→F, F→E}
3FN 3FN 3FN 3FN
R1 (AB) A -> B R (ABCDEF)
F1 = { A->B} F = {BC→ A, A→B, DE→F, F→E}
CC: A
FN? FNBC INFERENCIAS ????
R’ (ACDEF)
F -> E
F = {DE→F, F→E}
R2 (EF)
F2 = {F->E} CC: {ACDE, ACFD}
FN? 3FN
CC: F
FN? FNBC
R3 (ACDF)
F3 = { }
CC: {BCDE}
FN? FNBC
Ejercicio 2 - Opción 2 Fmin = {BC→ A, A→B, DE→F, F→E}
3FN 3FN 3FN 3FN
R1 (BCA) BC -> A R (ABCDEF)
F1 = {BC->A, A->B} F = {BC→ A, A→B, DE→F, F→E}
CC: BC, AC
FN? 3FN INFERENCIAS ????
R2 (AB) R3 (CA) R’ (BCDEF)
F2 = {A->B} F3 = { } F = {DE→F, F→E}
CC: AB CC: BCA
FN? FNBC FN? FNBC DE -> F CC: {BCDE, BCDF}
FN? 3FN
R4 (DEF)
F4 = {DE->F, F->E}
CC: DE, FD
FN? 3FN
R7 (BCDE)
F7 = { }
R5 (FE) R6 (DF) CC: {BCDE}
F5 = {F->E} F6 = { } FN? FNBC
CC: F CC: DEF
FN? FNBC FN? FNBC
Ejercicio 3
Dado R(ABCDEF) con F = {EC->A, AE->F, F->C, D->F, B->A, CF->B}
Verificar si la descomposición de R en R1(EF), R2(ACD) y R3(BDE) es sin pérdida de
información.
Tableau Inicial Iteración 1
A B C D E F A B C D E F
F={
R1(EF) R1 b11 b12 b13 b14 a5 a6 R1 b11 b12 b13 b14 a5 a6
EC->A
R2(ACD)
AE->F
R3(BDE)
R2 a1 b22 a3 a4 b25 b26 F->C R2 a1 b22 a3 a4 b25 b26
D->F
B->A R3 b31 a2 b33 a4 a5 b36
R3 b31 a2 b33 a4 a5 b36
CF->B b26
}
Iteración 2 Iteración 3
A B C D E F A B C D E F
F={ F={
EC->A R1 b11 b12 b13 b14 a5 a6 EC->A R1 b11 b12 b13 b14 a5 a6
AE->F AE->F
F->C R2 a1 b22 a3 a4 b25 b26 F->C R2 a1 a2 a3 a4 b25 b26
D->F a2 D->F
B->A B->A
R3 b31 a2 b33 a4 a5 b26 R3 b31 a2 a3 a4 a5 b26
CF->B CF->B
a3 a1
} }
Iteración 4
A B C D E F
F={
EC->A R1 b11 b12 b13 b14 a5 a6
AE->F
F->C R2 a1 a2 a3 a4 b25 b26
D->F
B->A
CF->B R3 a1 a2 a3 a4 a5 b26
}
No se producen cambios.
No se encuentra fila completa con variables distinguidas
HAY PÉRDIDA DE INFORMACIÓN
Preguntas?
Dudas?
Feedback
