Download Normalización

Normalización
Carlos A. Olarte
Bases de Datos I
Carlos A. Olarte Bases de Datos I
Normalización
Outline
1
Introducción
2
Dependencias Funcionales
3
Diseño de Bases de Datos
4
Forma Normal Boyce-Codd (FNBC)
5
3FN
6
Dependneicas Funcionales Multivaluadas
7
4FN
Carlos A. Olarte Bases de Datos I
Normalización
Introducción y Motivación
Por qué la normalización?
De dónde salen las formas normales?
Carlos A. Olarte Bases de Datos I
Normalización
Dependencias Funcionales
Sea r (R) una relación y k ⊆ R una clave de r entonces:
t1 6= t2 → t1 [k] 6= t2 [k]
Sea α ⊆ R y β ⊆ R. La Dep. Funcional
α→β
se cumple en R si para todo t1 , t2 :
t1 [α] = t2 [α] ⇒ t1 [β] = t2 [β]
k es una superclave de r si k → R
Carlos A. Olarte Bases de Datos I
Normalización
Ejemplo
Dado el esquema: R(Curso, Prof , Grupo, Horario) se cumplen
las siguientes D.F:
{curso, grupo} → profesor
{curso, grupo} → horario
Y no se cumple que:
{curso} → horario
Carlos A. Olarte Bases de Datos I
Normalización
Dependencias Triviales
Son aquellas que satisfacen todas las relaciones. Por ejemplo
A → A o AB → A
De forma general:
α → β es trivial si β ⊆ α
Carlos A. Olarte Bases de Datos I
Normalización
Conceptos
Relación que satisface una dependencia: Es una relación en la
cual se cumple la D.F
Dependencia que se cumple en un esquema: Es el conjunto de
dependencias que están obligadas a cumplir un esquema
Carlos A. Olarte Bases de Datos I
Normalización
Ejemplo
En la relación Horario:
Aud
A5
A5
A5
Curso
CC080
TE100
XY100
Fac
Ing
Ing
Ing
Car
Sys
Elec
Ind
Dı́a
Mar
Mie
Jue
Hora
7
7
7
Se satisface la dependencia Auditorio → Facultad y
Facultad → hora pero no es deseable que el esquema horario las
cumpla.
Carlos A. Olarte Bases de Datos I
Normalización
Continuación
Por lo anterior, el diseño de la base de datos debe formularse en
términos de las dependencias funcionales que debe cumplir el
esquema. Por ejemplo:
Curso → {Aud, Dia, Hora}
Curso → Facultad
Carrera → Facultad
Carlos A. Olarte Bases de Datos I
Normalización
Cierre de un conjunto de D.F
Dado un conjunto F de D.F, se puede definir una serie de D.F que
son implicaciones lógicas de F .
El conjunto F + (conjunto cierre), es el conjunto de todas las D.F
implicadas lógicamente de F .
Carlos A. Olarte Bases de Datos I
Normalización
Cálculo de F +
Se calcula a partir de las reglas de Armstrong que son correctas y
completas:
Reflexividad: Si β ⊆ α ⇒ α → β
Aumentatividad: Si α → β ⇒ αγ → βγ
Transitividad: Si α → β ∧ β → γ ⇒ α → γ
De las anteriores reglas se deducen las siguientes:
Unión: Si α → β ∧ α → γ ⇒ α → βγ
Descomposición: Si α → βγ ⇒ α → β ∧ α → γ
Pseudo Transitividad: Si α → β ∧ γβ → ϕ ⇒ αγ → ϕ
Carlos A. Olarte Bases de Datos I
Normalización
Cierre de un conjunto de atributos
Se define el CCA α dado un conjunto de D.F F (α+ ), al conjunto
de todos los atributos determinados funcionalmente a partir de α.
Si k es un superclave, α+ ≡ R
Carlos A. Olarte Bases de Datos I
Normalización
Cálculo de α+
resultado := α;
while(hay cambios)
for each β → γ in F do
if β ⊆ resultado then
resultado := resultado ∪ γ;
end;
end;
Carlos A. Olarte Bases de Datos I
Normalización
Recubrimiento Canónico
Es reducir el conjunto de D.F sin modificar el cierre del mismo
para facilitar el chequeo de las tuplas.
Definición: Un atributo de una D.F es raro si se puede
eliminar sin alterar F +
Formalmente: A es raro para α si A ∈ α y F implica
lógicamente (F − {α → β}) ∪ {(α − A) → β}
Carlos A. Olarte Bases de Datos I
Normalización
Continuación
Por otro lado, A es raro para β si A ∈ β y el conjunto de D.F:
(F − {α → β}) ∪ {α → (β − A)} implica lógicamente a F
El recubrimiento canónico Fc es un conjunto de D.F tales que
F implica Fc y Fc implica F . Además:
Ninguna D.F de Fc tiene atributos raros
Cada lado izquierdo de las D.F es único
Carlos A. Olarte Bases de Datos I
Normalización
Cálculo del Fc
repeat
utilizar la union para transformar α → βi y α → βj en α → βi βj
encontrar atrib raros en α → β
en α o en β y eliminarlos
until F no cambie
F y Fc tienen el mismo cierre
Carlos A. Olarte Bases de Datos I
Normalización
Ejemplo
Calcular Fc de:
A → BC
B→C
A→B
AB → C
Carlos A. Olarte Bases de Datos I
Normalización
Diseño de BD (Formas Normales)
El problema de la normalización:
Curso
CC080
CC080
CC100
CC100
CC100
Prof
COLARTE
COLARTE
COLARTE
COLARTE
COLARTE
CAlumno
4096
1232
2546
1232
3256
Carlos A. Olarte Bases de Datos I
NAlumno
ABC
XYZ
MNA
XYZ
BBD
Normalización
Nota
4.5
4.1
4.2
3.5
4.5
Errores en el diseño anterior
Hay información duplicada (gasto de espacio)
Actualizar el profesor de un curso es muy complicado (en
términos de eficiencia)
Cómo saber el profesor de un curso si hay dos registros del
mismo curso con profesor diferente?
Cómo saber el profesor de un curso si no hay ningún
estudiante matriculado?
Carlos A. Olarte Bases de Datos I
Normalización
Diseño de BD
Solución: Descomposición. Dicha descomposición debe
asegurar que no se pierda información y que el nuevo esquema
se encuentre en una Forma Normal
Descomposición: Un conjunto de esquemas {r 1..rn} es una
descomposición de r si R = R1 ∪ ... ∪ Rn
Carlos A. Olarte Bases de Datos I
Normalización
Algunos Conceptos
Superclave: Conjunto de atributos que en conjunto permiten
identificar una tupla
Clave Candidata: Subconjunto propio de la superclave que
sirven para identificar una tupla
Clave Primaria: Clave candidata elegida por el diseñador
Carlos A. Olarte Bases de Datos I
Normalización
Continuación
Descomposición de reunión sin pérdida: Sea C un conjunto de
ligaduras de Integridad. Una descomposición {R1..Rn} es una
descomposición de reunión sin pérdida si para todas las
relaciones r que son legales bajo C se cumple que:
r = πR1 (r ) ./ πR2 (r )... ./ πRn (r )
Carlos A. Olarte Bases de Datos I
Normalización
Continuación
De otra forma: Sea F un conjunto de D.F y R1 y R2 una
descomposición de R. La descomposición es sin pérdida, si al
menos una de las siguientes dependencias está en F + :
R1 ∩ R2 → R1
R1 ∩ R2 → R2
Carlos A. Olarte Bases de Datos I
Normalización
Conservación de las dependencias
En un diseño de bases de datos, se deben mantener las D.F iniciales
(en la medida de lo posible) , ası́ se descompongan las relaciones.
Carlos A. Olarte Bases de Datos I
Normalización
FNBC
Una esquema de relación R está en FNBC respecto a un conjunto
de D.F F si:
1
α → β es trivial
2
α es una superclave
Un diseño de B.D esta en FNBC si todas las relaciones del
esquema están en FNBC
Carlos A. Olarte Bases de Datos I
Normalización
Alg para la descomposición en FNBC
Resultado, hecho := {R}, false
Calcular F +
while(!Hecho)
if (hay un esq Ri de Result que no este en FNBC )
sea α → βno trivial que se cumple en Ri
de modo que α → Ri no este en F +
y α∩β =
Resultado :=
(resultado − Ri ) ∪ (Ri − β) ∪ (α, β)
end
end
Carlos A. Olarte Bases de Datos I
Normalización
Ejemplo
Sea r (Curso, Profesor , Creditos, Alumno, Grupo, Nota y las D.F:
curso → profesor , credito
alumno, curso, grupo → nota
La descomposición en FNBC serı́a: E 1(curso, prof , credito) y
E 2(curso, alumno, grupo, nota)
Carlos A. Olarte Bases de Datos I
Normalización
Ej. Pérdida de Dep
Sea R = {Sucur , Client, Banq} que indica que el cliente tiene un
banquero personal. Se exige que:
banquero → sucursal
sucursal, cliente → banquero
Aplicando el algoritmo se obtiene R1 = {Ban, Suc} y
R2 = {Cli, Ban} dónde se pierde la 2da D.F.
Carlos A. Olarte Bases de Datos I
Normalización
Criterios de diseño
Se debe lograr:
FNBC
Reunión sin Pérdida
Conservación de las Dependencias
Como no siempre se puede lograr se opta por:
3FN
Reunión sin Pérdida
Conservación de las Dependencias
Carlos A. Olarte Bases de Datos I
Normalización
3FN
Es una forma normal más débil que la FNBC . Se dice que R está
en 3FN con respecto al conjunto F de D.F si se cumple al menos
una de las siguientes condiciones:
1
α → β es trivial
2
α es una superclave
3
Cada atributo A en β − α está contenido en alguna clave
candidata de R ( dependencias transitivas)
Carlos A. Olarte Bases de Datos I
Normalización
3FN
Toda Relación en FNBC está en 3FN
En el ejemplo del banquero, la relación se encuentra en 3FN
puesto que una clave candidata puede ser {Suc, Cli} y
{Suc} − {ban} = {Suc} está contenido en una clave candidata. Y
para la 2da D.F, α es una superclave.
Carlos A. Olarte Bases de Datos I
Normalización
Algoritmo para Dec en 3FN
Calcular Fc
i := 0;
for each D.F α → β de Fc do
if ninguno Rj , j = 1..i contiene αβ
i + +; Ri := αβ
if ninguno Rj , j = 1..i contiene una clave
candidata de R
i + +;
Ri := Cualquier clave candidata de R
return(R1 ..Ri )
Carlos A. Olarte Bases de Datos I
Normalización
Ejemplo
Sea InfoBank = {suc, cli, banq, oficina} y las D.F
ban → {suc, ofic} y {cli, suc} → banq
En el ciclo del for se descompone en las siguientes relaciones:
ofic(banq, suc, ofic) y clien(cli, suc, banq)
Carlos A. Olarte Bases de Datos I
Normalización
FNBC vs. 3FN
La FNBC puede sacrificar dependencias, la 3FN no
Ambas aseguran reunión sin pérdida
En la 3FN puede duplicarse información (en el ejemplo
anterior, la información de dónde trabaja el banquero X está
duplicada)
Carlos A. Olarte Bases de Datos I
Normalización
Dependencias Multivaluadas
Se representa por
α →→ β
dónde: Si t1 [α] = t2 [α], ∃t3 , t4 tal que:
t1 [α] = t2 [α] = t3 [α] = t4 [α]
t3 [β] = t1 [β]
t3 [R − β] = t2 [R − β]
t4 [β] = t2 [β]
t1 [R − β] = t4 [R − β]
Carlos A. Olarte Bases de Datos I
Normalización
Dependencias Multivaluadas
Informalmente: La relación entre α y β es independiente a la
relación entre α y R − β. Por ejemplo, si un cliente puede tener
múltiples direcciones, puede escribirse:
cc cliente →→ direccion
α →→ β es trivial si β ⊆ α o si β ∪ α = R
Carlos A. Olarte Bases de Datos I
Normalización
4FN
Un esquema de relación R está en 4FN respecto a un conjunto D
de D.F.M si para toda D.F.M en D + cumple:
1
α →→ β es trivial
2
α es una superclave
Carlos A. Olarte Bases de Datos I
Normalización
Algoritmo
Resultado := {R}
Hecho := false;
CalcularD +
while(!Hecho)
if (hay un Ri que no este en4FN)
sea α →→ β no trivial
que cumple Ri de modo queα → Ri
no estaenD + y α ∩ β = Resultado := (Res − Ri ) ∪ (Ri − β) ∪ (α, β)
end;
end;
Carlos A. Olarte Bases de Datos I
Normalización
Ejemplo
Sea Libros(ISBN, Titulo, Materia, Autor , Fecha y las D.F:
ISBN → Titulo, Fecha
ISBN →→ Autor
ISBN →→ Materia
La descomposición en 4FN serı́a:
(ISBN, Titulo, Fecha), (ISBN, Materia)
(ISBN, Autor )
Carlos A. Olarte Bases de Datos I
Normalización
2FN
Solo reconocimiento histórico. Se dice que R está en 2FN si todo
atributo A pertenece a una clave candidata y A no depende
parcialmente de ninguna clave candidata.
Carlos A. Olarte Bases de Datos I
Normalización
1FN
Todos los atributos de una relación deben ser monovaluados
(inherente al modelo relacional)
Carlos A. Olarte Bases de Datos I
Normalización