Normalización
Tema 16
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es 2
Contenido
Introducción
Normalización de Relaciones
Bibliogra;a
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
• Al diseñar una BD relacional, podemos obtener diferentes esquemas
• La teoría de la normalización consigue una formalización en el diseño lógico
• ¿Qué propiedades debe tener un esquema para representar adecuadamente la realidad y qué problemas se pueden derivar de un diseño inadecuado?
• La teoría de la normalización permite afrontar el problema de diseño de bases de datos relacionales de una manera rigurosa y objetiva
Introducción
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Formas de abordar el proceso de modelado:
a) Realizando el proceso de diseño en dos fases
b) O b t e n i e n d o e l e s q u e m a r e l a c i o n a l directamente
Introducción
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
a) Proceso de diseño en dos fases: ESTUDIANTE (Cod_Estud, nombre, apellido, dirección)
SOLICITA (Cód_Beca, Cod_Estud, Fecha)
BECA (Cod_Beca, Nombre, Requisito)
Introducción: Proceso de diseño en dos fases
¿Es Correcto?
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Introducción: Proceso de diseño en dos fases
Cod_Estud Nombre_E Apellido Dirección
012323 Roberto Hens Antonio López 43
763476 Luis García Av. Ciudades 29
987765 Gregorio Celada Pl. Paises 67
232457 María García Rio Miño 2
Cod_Beca Cod_Estud Fecha
A22321 012323 10/10/08
B56784 763476 12/11/08
A22231 763476 14/10/08
G65434 763476 15/09/08
G65434 012323 17/09/08
G65434 987765 21/09/08
B56784 012323 11/11/08
B56784 987765 10/10/08
A22321 012323 12/11/08
A22321 232457 17/09/08
Cod_Beca Nombre Requisito
A22321 METRICA Ing. Técnico
B56784 ERASMUS Ing. Técnico
G65434 HIMMPA Ing. Superior
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Introducción: Esquema relacional directamente
¿Es correcto? ¿Recoge la misma información? ¿Es mejor o peor que el anterior?
Cod_Estud nombre apellidos dirección Cod_Bec nom_beca requisito Fecha
012323 Roberto Hens Antonio López 43 A22321 METRICA Ing. Téc 10/10/08
763476 Luis García Av. Ciudades 29 B56784 ERASMUS Ing. Téc 12/11/08
763476 Luis García Av. Ciudades 29 A22231 METRICA Ing. Téc 14/10/08
763476 Luis García Av. Ciudades 29 G65434 HIMMPA Ingenie. 15/09/08
012323 Roberto Hens Antonio López 43 G65434 HIMMPA Ingenie. 17/09/08
987765 Gregorio Celada Pl. Países 67 G65434 HIMMPA Ingenie. 21/09/08
012323 Roberto Hens Antonio López 43 B56784 ERASMUS Ing. Téc 11/11/08
987765 Gregorio Celada Pl. Países 67 B56784 ERASMUS Ing. Téc 10/10/08
012323 Roberto Hens Antonio López 43 A22321 METRICA Ing. Téc 12/11/08
232457 María García Rio Miño 2 A22321 METRICA Ing. Téc 17/09/08
b) Obteniendo el esquema relacional directamente:
ESTUDIANTE_SOLICITA_BECA
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
• Incapacidad para almacenar ciertos hechos. • Redundancias y, por tanto, posibilidad de
inconsistencias. • Ambigüedades. • Pérdida de información (aparición de tuplas espurias). • Pérdida de dependencias funcionales • Existencia de valores nulos (inaplicables) • Aparición de estados que no son válidos en el mundo
real
Estos problemas podemos tenerlos en cualquiera de los dos casos
Introducción: Posibles Problemas
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Introducción: Pérdida de Información
Cod_Asig Aula
DBD 318
DBD 121
IS 330
Cod_Asig Nom_Alum Aula
IS Juan 330
DBD Juan 318
DBD Leire 121
IS Leire 330
Cod_Asig Nom_Alum
IS Juan
DBD Juan
DBD Leire
IS Leire
Cod_Asig Nom_Alum Aula
IS Juan 330
DBD Juan 318
DBD Juan 121
DBD Leire 318
DBD Leire 121
IS Leire 330
Tuplas espurias
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Contenido
Introducción
Normalización de Relaciones • Dependencias y cálculo del cierre de un
descriptor. • Cálculo del recubrimiento minimal. • Cálculo de las claves candidatas • Formas Normales • Métodos de descomposición y síntesis Bibliogra;a
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Teoría de la Normalización
Dado un conjunto A de atributos y el conjunto D de dependencias existentes entre ellos que consAtuyen un esquema de relación R(A, D), se trata de transformar, por medio de sucesivas proyecciones, este esquema de parAda en un conjunto de n esquemas de relación
{ 𝑹↓𝒊 ( 𝑨↓𝒊 , 𝑫↓𝒊 ,)}↑𝒏 ↓𝒊=𝟏 tales que cumplan unas determinadas condiciones:
El conjunto de esquemas 𝑹↓𝒊 deberan ser equivalentes a 𝑹 y mejores que el esquema de parAda
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Normalización de Relaciones
Pasos para normalizar relaciones:
1. Calculo de las dependencias funcionales, mulAvaluadas, jerárquicas y en combinación que existen entre los atributos de la relación.
2. Calculo del recubrimiento minimal.
3. Calculo de las claves candidatas de la relación, de los atributos principales y de los no principales.
4. Cálculo de la de la forma normal en que se encuentra la relación
5. Aplicar los métodos de descomposición y síntesis para obtener la forma normal deseada.
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Contenido
Introducción
Normalización de Relaciones • Dependencias y cálculo del cierre de un
descriptor. • Cálculo del recubrimiento minimal. • Cálculo de las claves candidatas • Formas Normales • Métodos de descomposición y síntesis Bibliogra;a
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Dependencias entre los datos
Las dependencias son propiedades inherentes al contenido semánQco de los datos; forman parte de las restricciones de usuario del modelo relacional y se han de cumplir para cualquier extensión de un esquema de relación.
Sin pérdida de generalidad vamos a considera que el esquema relacional está compuesto por un único esquema de relación:
R(A, DEP) • A: conjunto de dependencias existentes entre los atributos • DEP: cjto. de dependencias existentes entre los atributos
Tipos: funcionales, mulQvaluadas, jerárquicas…
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Dependencias Funcionales
Si para cada valor de X, solamente existe un único valor de Y
Ejemplo:
Si e entonces
X e Y son equivalentes
yx→implicado
profesornombreprofesordni __ →
yx→ xy→ yx↔
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Además sí, DF Transitiva Estricta
Dependencias Funcionales: Tipos
1. DF Trivial: y además Y es un subconjunto de X Ejemplo:
2. DF Elemental: Si Y es un atributo único, se trata de una dependencia plena (no
parcial) y no trivial.
3. DF TransiAva:
yx→profesornombreprofesornombre __ →
xyzyyx
DEPzyxR
→
→
→
)},,,({
zx →−yz→
profesornombrepostalcodigociudadpostalcodigo
postalcodigoprofesornombreDEPciudadpostalcodigoprofesornombreR
___
__)},,_,_({
→
→
→
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Dependencia MulQvaluada
X mulAdetermina a Y, si para cada valor de X existe un conjunto bien
definidos de valores posible en Y, con independencia del resto de los atributos de la relación.
Ejemplo:
Tipos: Dependencias mulAvaluadas jerárquicas
yx→→
Nombre Titulación
Juan Mag. Música
Juan Ing. Informática
Ana Ing. Caminos
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Dependencias Jerárquicas
X mulAdetermina jerárquicamente a Y y Z si:
X mulAdetermina a Y y
X mulAdetermina a Z
Ejemplo:
Nombre Titulación Proyecto
Pedro Mag. Música A
Pedro Ing. Informática B
Maria Ing. Caminos A
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Cierre de un Descriptor
• DF+: conjunto de todas las dependencias funcionales implicadas por DF.
• Primera aproximación: axiomas de Armstrong:
§ Reflexividad: si Y ⊆ X, entonces X → Y
§ Aumento: si X → Y, entonces XZ → YZ
§ Transitividad: si X → Y y Y → Z, entonces X → Z
Cierre de un conjunto de dependencias:
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Cierre de un Descriptor (II)
• Podemos calcular DF+ aplicando los axiomas
• Calcular el cierre de un subconjunto tal que X sea implicante: cierre transi(vo de un descriptor X de R respecto al conjunto de dependencias DF, (X+
DF)
• Dado R(A, DF), se define X+DF como un subconjunto de los
atributos de A tales que X → X+DF ∈ DF+, siendo X+
DF máximo en el senAdo de que la adición de cualquier atributo vulneraría la condición anterior
• Consecuencias: cálculo de SK (superclave) y K (clave)
• Algoritmo de Ullman
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Ejemplo: Cierre TransiQvo de un Descriptor
Sea R ({A, B, C, D, E, F}, DF), donde DF={A → B, B → A, C → A, D → C, (E, C) → D, A → F, C → F}
Hallar el cierre del descriptor (E, C)
E, C → E, C
E, C → E, C, D
E, C → E, C, D, A
E, C → E, C, D, A, B
E, C → E, C, D, A, B, F
Por tanto, (E, C)+ = E, C, D, A, B, F
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Equivalencia de conjuntos de DF
Dado DF, X → Y ∈ DF+ sii Y ⊆ X+DF
DF1 y DF2 son equivalentes si DF+1 = DF+2. § Si para toda dependencia X → Y∈DF2 se cumple que Y ⊆ X+
DF1, entonces toda dependencia de DF2 está en DF1 y por tanto DF1 es un recubrimiento de DF2
§ Si para toda dependencia Z → W∈DF1 se cumple que W ⊆ Z+DF2, entonces toda dependencia de DF1 está en DF2 y por tanto DF2 es un recubrimiento de DF1 está
Si se cumplen ambas condiciones, DF1 y DF2 son mutuamente
recubrimientos, luego son equivalentes
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Contenido
Introducción
Normalización de Relaciones • Dependencias y cálculo del cierre de un
descriptor. • Cálculo del recubrimiento minimal. • Cálculo de las claves candidatas • Formas Normales • Métodos de descomposición y síntesis Bibliogra;a
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Cálculo del Recubrimiento Minimal
Un conjunto de dependencias es mínimo, y se denota , cuando se cumplen las siguientes condiciones:
a) Todas son dependencias son elementales (plenas, no triviales y con un
único atributo implicado)
b) No existen atributos extraños. A es extraño en sí,
c) No existe en la relación ninguna dependencia redúndate.
Se pueden obtener varios de conjuntos de dependencias mínimos válidos
mDEP
}),{},,,({ CABCACBAR →→
}),,{},,,({ CACBBACBAR →→→
YX →
YAX →− )(
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Contenido
Introducción
Normalización de Relaciones • Dependencias y cálculo del cierre de un
descriptor. • Cálculo del recubrimiento minimal. • Cálculo de las claves candidatas • Formas Normales • Métodos de descomposición y síntesis Bibliogra;a
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Cálculo de Claves Candidatas
Dado un esquema de relación R(A,DEP) se denomina superclave de la relación R a un conjunto no vacio de atributos perteneciente de A, tal que estos atributos determinan a todo el conjunto A, es decir, que el cierre transiAvo de ese conjunto de atributos sea todo A
El cierre transiAvo de X se define como el conjunto de atributos determinados por
X aplicando los axiomas de Armstrong, denotado. Ejemplo:
+X
}{}{},{
},,,{});,}{,,,({
DDCCCBB
DCBAACBDBADCBAR
=
=
=
=
→→
+
+
+
+
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Cálculo de Claves Candidatas (II)
Se denomina clave candidata (CC) de una relación a una superclave tal que cumple que ningún subconjunto de la misma determina a todo A
Ejemplo:
CC ya que determina a todos los atributos No es CC, aunque determina a todos los atributos, porque el
subconjunto {A} determina a todos los atributos. Atributos Principales y No Principales • AP: Cuando forma parte de laguna de las claves candidatas de la relación.
• ANP: Cuando no forma parte de ninguna de las claves candidatas
},{}{AB
A
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Contenido
Introducción
Normalización de Relaciones • Dependencias y cálculo del cierre de un
descriptor. • Cálculo del recubrimiento minimal. • Cálculo de las claves candidatas • Formas Normales • Métodos de descomposición y síntesis Bibliogra;a
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Esquemas en 1FN
Esquemas en 2FN
Esquemas en 3FN
Esquemas en FNBC
Esquemas en 4FN
Esquemas en 5FN
Formas Normales
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
1FN. Primera Forma Normal
Condiciones:
• Cada atributo solo toma un valor del dominio. No existen grupos repeAdos
Ejemplo: La primera forma normal es una restricción inherente al modelo relacional, por lo
que su cumplimiento es obligatorio para toda relación
Nombre Titulaciones
Miguel Informática Física
Vanesa E. Infantil
Nombre Titulaciones
Miguel Informática
Miguel Física
Vanesa E. Infantil
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
2FN. Segunda Forma Normal
Condiciones: • Se encuentra en 1FN • Cada atributo no principal (ANP) tiene dependencia funcional completa
respecto de alguna de las claves.
Ejemplo:
}}{{:}}{{:
:},{});,{},,,,({
DCANPBAAP
CCBADACBADCBAR →→
}){},,({2
}),{},,,({1
DADAR
CBACBAR
→
→
NO ESTÁ EN 2FN ESTÁ EN 2FN
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
3FN. Tercera Forma Normal
Condiciones: • Se encuentra en 2FN • No existe ningún atributo no principal (ANP) que dependa transiQvamente de
alguna clave de R.
Ejemplo:
}}{{:}{:
:}{});{},,,({
CBANPAAPCCA
CBBACBAR →→
NO ESTÁ EN 3FN
}){},,({2
}){},,({1
CBCBR
BABAR
→
→
ESTÁ EN 3FN
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
FNBC. Forma Normal Boyce-‐Codd
Condiciones: • Se encuentra en 3FN • Si y solo si todo determinante es clave candidata.
Ejemplo:
CCCBCANoCCBA
DCABADCBAR
:},{},,{:}{},{
}),;{},,,,({ →↔
NO ESTÁ EN FNBC ESTÁ EN FNBC
}),{},,,({2
}){},,({1
DCADCAR
BABAR
→
↔
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
4FN. Cuarta Forma Normal
Condiciones: • Si y solo si las únicas dependencias mulQvaluadas no triviales son aquellas en
las que una clave mulQdetermina un atributo.
Ejemplo:
});{},,,({ CABACBAR →→→→
NO ESTÁ EN 4FN ESTÁ EN 4FN
}){},,({2
}){},,({1
CACAR
BABAR
→→
→→
C no participa B no participa
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
5FN. Quinta Forma Normal
Condiciones: • Se encuentra en 4FN. • Toda dependencia de combinación está implicada por una clave candidata.
Definición:
“Una relación se encuentra en 5FN si y solo sí toda dependencia funcional, mulAvaluada o de combinación no trivial es consecuencia de las claves candidatas”
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Contenido
Introducción
Normalización de Relaciones • Dependencias y cálculo del cierre de un
descriptor. • Cálculo del recubrimiento minimal. • Cálculo de las claves candidatas • Formas Normales • Métodos de descomposición y síntesis Bibliogra;a
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Métodos de Descomposición y Síntesis
ObjeAvo: • Transformar, por medio de proyecciones, un esquema de relación
en un conjunto de n esquemas resultantes. • Los n esquemas resultantes serán equivalentes a la relación inicial
y tendrán menor redundancia en los datos. A tener en cuenta: • Conservación de la información. • Conservación de las dependencias. • Mínimas redundancias en los datos. • Avanzar en las formas normales.
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Proceso de Descomposición
1) Hallar un recubrimiento minimal DFm 2) Determinar la(s) clave(s), AP y ANP 3) Identificar la FN en que se encuentra la relación Si se desea llegar a una forma normal más avanzada: 4) Agrupar las DF que tengan el mismo implicante y/o equivalente 5) Obtener proyecciones independientes sobre cada una de las DF
(o de los grupos), de forma que los atributos que aparecen en la DF constituyen una nueva relación y los ANP, así como la DF, desaparezcan de la relación origen.
6) Proseguir esta descomposición repitiendo el paso 5 hasta que no pueda continuarse porque todas las DF estén implicadas por una clave.
Nos aseguramos relaciones en 5FN
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Ejemplo: Proceso de Descomposición
Claves:{A,B,D} 1FN
Claves:{A,C} 5FN
Claves:{A,B,D} 1FN
},{},,{FDADEP
FDAAT→=
=
Claves:{A,D} 5FN Claves:{A,B}
5FN
R
R2
R1’ R1
R3
},{},,{CBADEP
CBAAT→=
=
},;,{},,,,{
FDACBADEPFDCBAAT
→→=
=},{
},,{ECADEP
ECAAT→=
=
},;,;,{},,,,,{
}){},({
ECAFDACBADEPFEDCBAAT
DEPATR
m
m
→→→=
=
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Proceso de Síntesis
1) Hallar un recubrimiento minimal DFm
2) Agrupar las DF en particiones que tienen el mismo implicante, uniendo los atributos equivalentes
3) Crear un esquema Ri para cada parAción, que tenga como atributos todos los que parAcipen en las dependencias y como grupo de dependencias las del grupo.
4) Si existen atributos que no son implicantes ni implicados , formar un esquema de relación con estos sin dependencias o alternativamente crear un esquema con la clave de la relación sin dependencias.
Nos aseguramos relaciones en FNBC
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Ejemplo: Proceso de Síntesis
},;,;,{},,,,,{
}){},({
ECAFDACBADEPFEDCBAAT
DEPATR
m
m
→→→=
=
Se crea un nuevo esquema de relación por cada conjunto de dependencias que poseen el mismo implicante
}),{},,,({1 CBACBAR →
}),{},,,({2 FDAFDAR →
}),{},,,({3 ECAECAR →
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
Contenido
Introducción
Normalización de Relaciones • Dependencias y cálculo del cierre de un
descriptor. • Cálculo del recubrimiento minimal. • Cálculo de las claves candidatas • Formas Normales • Métodos de descomposición y síntesis Bibliogra;a
Diseño de Bases de Datos y Seguridad de la Información -‐ 2010 www.kybele.urjc.es
& Date, C. J. “An Introduction to Database Systems” (8ª edición), Addison-Wesley, 2004. (Existe traducción al castellano de la 7ª Ed.)
& Piattini, M., Marcos, E., Calero, C. y Vela, B. Tecnología y Diseño de Bases de Datos, Ed.: RA-MA, 2006
& de Miguel A., et al. Diseño de Bases de Datos. Problemas Resueltos. Ed.: RA-MA, 2001
Bibliogra;a