Formas Normales
– Normalización - Introducción
– Primera Forma Normal
– Segunda Forma Normal
– Tercera Forma Normal
– Forma Normal de Boyce-Codd
– Dependencias Multivaluadas
– Cuarta Forma Normal
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 1
Normalización
Introducción
– En el proceso de normalización se somete un esquema
relación (er) a una serie de pruebas para “certificar” si
pertenece o no a una cierta forma normal.
– Puede considerarse como un proceso durante el cual
los er insatisfactorios se descomponen repartiendo sus
atributos entre ers más pequeños que poseen
propiedades deseables.
– Las formas normales, sin considerar otros factores, no
garantizan un buen diseño de BD. Props adicionales:
» Join sin pérdida
» Preservación de dependencias
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 2
Superclave
Superclave
– Una superclave de R = {A1, …, An} es un
conjunto de atributos S ⊆ R tal que no existen 2
tuplas t1 y t2 en ningún r tal que t1[S] = t2[S].
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 3
Clave
Clave
– Una clave K es una superclave que cumple que
si se le quita alguno de sus atributos, deja de
ser superclave.
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 4
Clave Candidata
Clave candidata, clave primaria
– Si una relacion tiene mas de una clave, cada
una es una clave candidata. Una de ellas es
arbitrariamente designada como clave primaria.
El resto son secundarias.
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 5
Primera Forma Normal (1NF)
Definición
– Los dominios de los atributos deben incluir solo
valores atómicos (los atributos no pueden ser
multivaluados ni compuestos)
Ejemplo
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 6
Definiciones
Atributo Primo
– Un atributo del esquema relación R es primo si
es miembro de alguna clave de R.
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 7
Definiciones
Atributos redundantes a la izquierda de df
– Dado F conjunto de dfs que se cumplen en R,
decimos que la df X→A ∈ F contiene atributos
redundantes a la izquierda, si se cumple Y→A
∈ F+, donde Y ⊂ X.
Dependencia Parcial
– X→Y es una df parcial si contiene al menos un
atributo redundante a la izquierda.
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 8
Segunda Forma Normal (2NF)
Definición
– Un er R está en 2NF si ningún atributo no primo
A de R depende parcialmente de cualquier
clave de R.
Dicho de otra forma:
– Un er R está en 2NF si no existe una df parcial
X->A tal que X es clave y A no es un atributo
primo.
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 9
Segunda Forma Normal (2NF)
Ejemplo
–El atributo no primo NOMBREE viola 2NF, por la df2
–Los atr no primos NOMBREPR y LUGARP violan 2NF, por la df3
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 10
Segunda Forma Normal (2NF)
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 11
Definiciones
Dependencia Transitiva
– Una df X→Y en un er R es una df transitiva si
existe un conjunto de atributos Z que no sea un
subconjunto de una clave de R, y se cumplen
tanto X→Z como Z→Y.
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 12
Tercera Forma Normal (3NF)
Definición
– Un er R está en 3NF si está en 2NF y ningún
atributo no primo de R depende transitivamente
de una clave de R.
– Un er R está en 3NF si, siempre que una df
X→A se cumple en R, o bien (a) X es una
superclave de R, o (b) A es un atributo primo de
R.
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 13
Tercera Forma Normal (3NF)
Ejemplo
–Las dfs NUMEROD→NOMBRED y NUMEROD→NSSGTED violan 3NF
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 14
Tercera Forma Normal (3NF)
Ejemplo
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 15
Forma Normal de Boyce-Codd (BCNF)
Definición
– Un er R está en BCNF si, siempre que una df
X→A se cumple en R, entonces X es una
superclave de R.
Ejemplo
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 16
Forma Normal de Boyce-Codd (BCNF)
Ejemplo
Imparte (estudiante, curso, profesor)
F = { estudiante, curso profesor
profesor curso } 3NF
Claves: {estudiante, curso} y {estudiante,
profesor}
Descomposiciones posibles:
{estudiante, profesor} y {estudiante, curso}
{curso, profesor} y {curso, estudiante}
{profesor, curso} y {profesor, estudiante}
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 17
Algoritmos de diseño
– Descomposición de relaciones
– Preservación de dependencias
– Descomposición en 3NF preservando las dfs
– Join sin pérdida. Propiedad
– Test de join sin pérdida
– Descomposición en BCNF con JSP
– Descomposición en 3NF con JSP y pres de dfs
– Problemas con valores nulos y tuplas colgantes
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 18
Descomposición de relaciones
Esquema relación universal R
– R = (A1, A2, ..., An), que contiene todos los
atributos de la BD
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 19
Descomposición de relaciones
Descomposición de R, D
– D = (R1, R2, ..., Rm), que se obtiene mediante
los algoritmos que realizan la descomposición
utilizando las dependencias funcionales
– Se debe verificar: ∪i=1m Ri = R
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 20
Preservación de dependencias
Proyección de un conjunto de
dependencias sobre un Esquema de
Relación
– Dado un conjunto de dfs F sobre R, la
proyección de F sobre Ri, ΠRi(F), donde Ri es
un subconj de R, es el conj de dfs X→Y en F+
tal que los atributos en X∪Y estén todos
contenidos en Ri.
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 21
Preservación de dependencias
Preservación de dependencias
– Una descomposición D = (R1, R2, ..., Rm) de R
preserva las dependencias respecto a F si se
cumple: ( (ΠR1(F)) ∪ ... ∪ (ΠRm(F)) )+ = F+
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 22
Descomposición en 3NF con pres de dfs
Algoritmo
1. Encontrar un cubrimiento minimal G para F;
2. Para cada miembro izq X de una df que aparezca en G
crear un er {X ∪ A1 ∪ A2 ... ∪ Am} en D, donde
X→ A1, X→ A2, ... , X→ Am sean las únicas dfs en G
con X como miembro izq;
3. Colocar cualesquier atributos restantes en un solo er
para asegurar la prop de preservación de dependencias;
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 23
Join sin Pérdida
Definición
– Una descomposición D = (R1, R2, ..., Rm) de R
tiene la propiedad de JSP respecto al conjunto
de dfs F sobre R, si por cada instancia de
relación r de R que satisfaga F, se cumple lo
siguiente:
* (ΠR1(r), ..., ΠRm(r)) = r
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 24
Join sin Pérdida
Propiedad
– D = (R1, R2) de R tiene JSP respecto a F sobre
R sii - la df (R1 ∩ R2) → (R1 - R2) está en F+
ó - la df (R1 ∩ R2) → (R2 - R1) está en F+
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 25
Test de join sin pérdida
Algoritmo
1. crear una matriz S con una fila i por cada relación Ri en la desc
D, y una columna j por cada atributo Aj en R;
2. hacer S(i,j) := bij para todas las entradas de la matriz;
3. para cada fila i que represente el er Ri
para cada columna j que represente el atributo Aj
si Ri incluye a Aj entonces hacer S(i,j) := aj;
4. repetir hasta que una ejecución no modifique S
para cada df X→Y en F
igualar los símbolos en los atributos de Y para
aquellas filas que coinciden en los atributos de X;
5. si una fila tiene todos símbolos “a”, la desc es con JSP, en caso
contrario, no lo es;
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 26
Test de join sin pérdida
Ejemplo
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 27
Descomposición en BCNF con JSP
Algoritmo
1. hacer D := { R };
2. mientras haya un er Q en D que no esté en BCNF hacer
comenzar
escoger un er Q en D que no esté en BCNF;
encontrar una df X→Y en Q que viole BCNF;
reemplazar Q en D por dos esquemas (Q - Y) y (X ∪ Y)
fin;
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 28
Desc en 3NF con JSP y pres de dfs
Algoritmo
1. encontrar un cubrimiento minimal G para F;
2. para cada miembro izq X de una df que aparezca en G
crear un er {X ∪ A1 ∪ A2 ... ∪ A1m} en D, donde
X→ A1, X→ A2, ... , X→ Am sean las únicas dfs en G
con X como miembro izq;
3. colocar cualesquier atributos restantes en un solo er;
4. si ninguno de los er contiene una clave de R, crear un er
adicional que contenga atributos que formen una clave de R;
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 29
Problemas con nulos
Ejemplo
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 30
Problemas con nulos
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 31
Problemas con tuplas colgantes
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 32
Resumen
Se presentaron las ideas básicas de la
teoría de diseño relacional.
– Dependencia Funcional
– Forma Normal
– Descomposición
– Preservación de Dependencias
– Join Sin Pérdida
– Algoritmos de Normalización.
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 33
Resumen
1NF
2NF
3NF
BCNF
[Link]. - Facultad de Ingeniería Curso : Fundamentos de Bases de Datos Tema 4 - Diseño Relacional 34
