TEORÍA DE LA NORMALIZACIÓN

GESTIÓN Y MODELACIÓN DE DATOS

Problemas que se pueden presentar en un esquema relacional

● Información duplicada

● Actualizar el nombre de un jefe es complicado

● Como saber en que ciudad está un departamento, si aún no tiene empleados?

● 'Juan Carlos Melo' = 'Juan C. Melo'?...

CcEmpleado Nombre Departamento CiudadDpto Jefe

39288271 Sonia Maria Osorio Ventas Cali Santiago de Cali Mario Alfonso Gil

29282813 Mario Alfonso Gil Gerencia Reg. Cali Juan C. Melo

39372722 Juan Carlos Melo Presidente Bogotá

39387472 Andrea Solano Ventas Bogotá Bogotá Carolina Reyes

….

Problemas que se pueden presentar en un esquema relacional

● Redundancia de datos● Ambigüedad● Anomalías de inserción, modificación y

borrado de datos

Normalización

Formas Normales (FN): conjunto de restricciones que evitan problemas de redundancia y anomalías de inserción,

modificación y borrado de datos

Con base en las dependencias funcionales entre los atributos

Dependencias Funcionales

Dependencias Funcionales

Sea R una relación, X e Y subconjuntos de sus atributos:

Y depende funcionalmente de X si cada valor de X tiene asociado el mismo valor de Y en la

relación R

● Se denota X → Y ● X se denomina determinante o implicante● Y son los atributos implicados

Dependencias Funcionales - Ejemplo

ProgramaAcademico(codProg, registroIcfes, nombre,

noCreditos, codDirector, nombreDirector)

Dependencias funcionales:

codProg → registroIcfes nombre noCreditos

codDirector NombreDirector

registroIcfes → CodProg nombre noCreditos

codDirector NombreDirector

codDirector → nombreDirector

Dependencias Funcionales - Ejercicio

Encontrar las dependencias funcionales en:

Escribe(autor, pais, ISBN, titulo, editorial)

Teniendo en cuenta que un libro puede tener varios autores, pero solo esta publicado por una editorial.

Dependencias Triviales

Ejemplo:

A → A

AB → A

AB → B

α → β es trivial si β α

Normalización

Primera Forma Normal

Una relación R está en la primera forma normal (1FN) si los dominios de todos los atributos de R

son atómicos

1FN

Normalización

Segunda Forma Normal

Una relación R está en la segunda forma normal (2FN) si está en 1FN y todos los atributos que no

son parte de la llave primaria dependen funcionalmente, de manera completa, de ella

NormalizaciónSegunda Forma Normal

Eliminar dependencias parciales

Descomposición

● Para cumplir con las formas normales puede ser necesario descomponer una relación en varias relaciones

● Propiedades deseables de la descomposición:● Descomposición de reunión sin pérdida● Conservación de las dependencias funcionales

Normalización

Tercera Forma Normal

Una relación R está en la tercera forma normal (3FN) si está en 2FN y los atributos que no son

parte de la llave primaria no tienen dependencias funcionales transitivas

● Dependencia Funcional Transitiva: cuando un atributo Y depende funcionalmente de un atributo X, y X no hace parte de la llave de R

NormalizaciónTercera Forma Normal

Eliminar dependencias transitivas

Normalización

Forma Normal de Boyce-Codd

Una relación R está en la forma normal de Boyce y Codd (FNBC) si siempre que la dependencia

funcional no trivial X → Y se satisface en R, X es una superllave

Normalización

Forma Normal de Boyce-Codd

Llaves candidatas: {cod-e, cod-asig}, {cod-asig, cedula}

Normalización

Cliente Sucursal Vendedor

Frecuencia

● Ejemplo: una relación en 3FN, pero no en FNBC

Cliente-Sucursal

{Cliente, Sucursal} → Vendedor Frecuencia

Vendedor → Sucursal

● Para convertir la relacion a FNBC:

Vendedor

SucursalCliente Sucursal Frecuencia

Ejercicios● Para cada una de las siguientes relaciones:

● Encuentre las dependencias funcionales ● Identifique en que forma normal esta● Lleve el diseño hasta la FNBC

Book (authorName, title, ISBN, publisher, pubYear, pubCountry)

Student (rollNo, name, sex, hostelName, hostelAddress, hostelPhone, roomNo, admitYear) - Cada estudiante tiene una habitación independiente - Hay hospedajes exclusivos para hombres y para mujeres

gradeInfo(rollNo, studName, course, grade) - Cada estudiante tiene una nota en un curso - El nombre del estudiante es tambien un identificador del mismo

Normalización

Cuarta y Quinta Forma Normal

● Aplican en tablas en con 3 o más atributos, en las que todos los atributos hacen parte de la llave primaria

● 4FN: eliminar dependencias multivaluadas

● 5FN: continuar el proceso de descomposición, con base en llaves candidatas

Dependencias Multivaluadas

Dada una relación R y las tuplas t1, t2, t3, y t4:Si t1[α] = t2[α], existe t3 y t4 tal que: t1[α] = t2[α] = t3[α] = t4[α] t3[β] = t1[β] t3[R-β] = t2[R-β] t4[β] = t2[β] t1[R-β] = t4[R-β]

Ejemplo: prof(nombre, dir, tel, asignatura)nombre dir tel asignatura

Juan Cra 23 .. 12345 as2

Juan Cra 23 .. 98765 as1

Juan Cra 23 .. 12345 as1

Juan Cra 23 .. 98765 as2

nombre → dirnombre →→ telnombre →→ asignatura

Dependencias Multivaluadas

Una dependencia multivaluada (DMV) en R, X→→Y , significa que si dos tuplas de R

coinciden en todos los atributos de X, entonces sus componentes en Y se puede intercambiar, y el resultado serán dos tuplas que también están

en la relación

Ejemplo: prof(nombre, dir, tel, asignatura)

nombre dir tel asignatura

Juan Cra 23 .. 12345 as2

Juan Cra 23 .. 98765 as1

Juan Cra 23 .. 12345 as1

Juan Cra 23 .. 98765 as2

Normalización

Cuarta Forma Normal

Una relación R está en 4NF si: siempre quela dependencia X →→ Y es una DMV no

trivial, entonces X es una superllave

Una dmv no trivial significa que:1. Y no es un subconjunto de X, y2. X y Y no son, juntos, todos los atributos.

Normalización● Ejemplonombre dir tel asignatura

Juan Cra 23 .. 12345 as2

Juan Cra 23 .. 98765 as1

Juan Cra 23 .. 12345 as1

Juan Cra 23 .. 98765 as2

nombre dir

Juan Cra 23 ..

nombre tel asignatura

Juan 12345 as2

Juan 98765 as1

Juan 12345 as1

Juan 98765 as2

nombre tel

Juan 12345

Juan 98765

nombre asignatura

Juan as2

Juan as1

Ejercicios

Para cada una de las siguientes relaciones:● Encuentre las dependencias funcionales

multivaluadas ● Lleve el diseño hasta la 4FN

Libro(ISBN, Titulo, Materia, Autor, Fecha) - Un libro tiene varios autores y se usa en varias materias

Vendedor(cedula,nombre,producto,cliente)

- Un vendedor vende varios productos a varios clientes

Cierre de un Conjunto de Dependencias Funcionales

● Dado un conjunto F de dependencias funcionales se puede probar que se cumplen otras dependencias que están implicadas lógicamente por F

Ejemplo: Dado R = (A B C G H I) y

A→ B A→ CCG → H CG → I B → H

La dependencia funcional A→H está implicada lógicamente: Si t1 y t2 son dos tuplas tales que t1[A] = t2[A] Como A → B, entonces t1[B] = t2[B], Como B → H, entonces t1[H] = t2[H], Por lo tanto, siempre que t1[A] = t2[A] se cumple que t1[H] = t2[H], lo cual es la definición de A → H

Cierre de un Conjunto de Dependencias Funcionales

El Cierre de un Conjunto de Dependencias Funcionales F, denotado por F+, es el conjunto de

todas las dependencias funcionales implicadas lógicamente en F

Axiomas de Armstrong● Regla de la Reflexividad● Regla de la Aumentatividad● Regla de la Transitividad

Cierre de un Conjunto de Dependencias Funcionales

Axiomas de Armstrong● Reflexividad: Si β ⊆ α, entonces α→β

● Aumentatividad: Si α→β, entonces γα →γβ

● Transitividad: Si α →β y β →γ, entonces α →γ

Notación: α,β,γ,... denotan conjuntos de atributos A,B,C,... denotan un atributo particular αβ... denota α ᴜ β

Cierre de un Conjunto de Dependencias Funcionales

Los Axiomas de Armstrong son correctos y completos (sound and complete)● Correctos (sound): no generan dependencias

funcionales incorrectas● Completos (complete): generan todas las

dependencias funcionales implicadas lógicamente

Cierre de un Conjunto de Dependencias Funcionales

Reglas Adicionales (se pueden demostrar con los Axiomas de Armstrong):● Unión: Si α→β y α→γ, entonces α →βγ● Descomposición: Si α→βγ, entonces α→β y

α→γ● Pseudotransitividad: Si α →β y γβ →δ,

entonces αγ →δ

Cierre de un Conjunto de Atributos

● El cierre de un conjunto de atributos α, denotado α+, permite determinar las llaves de una relación, y si se cumple una dependencia funcional α → β

resultado := α;while (cambios en resultado) do for each dependencia funcional β →γ in F do begin if β ⊆ resultado then resultado := resultado ∪ γ; end

● α es una super llave si en resultado quedan todos los atributos de la relación

● α → β si β ⊆ resultado

Cierre de un Conjunto de Atributos

Ejemplo: Dado R = (A B C G H I) y

A→ B A→ CCG → H CG → I B → H

● Calcular (CG)+● ¿Es (CG) superllave de R?● ¿CG → A ?

● Calcular (AG)+● ¿Es (AG) superllave de R?

Normalización y Diseño de BD

● Generalmente un buen diseño E-R al trasladarse a relacional queda normalizado. Los problemas de normalización que se encuentren en el m.relacional se podrán corregir modificando el MER.

● Enfoque de Relación universal: un segundo enfoque de diseño de BD.● Consiste en definir un solo esquema de relación

con todos los atributos, y normalizarlo

Desnormalización y Rendimiento

● Algunas veces es necesaria la redundancia para mejorar el desempeño de operaciones críticas

● Se debe garantizar que los datos redundantes se mantengan consistentes: costo de codificación y de tiempo de ejecución, posibilidad de errores

● Alternativa: usar vistas materializadas (almacenadas fisicamente), que son actualizadas automáticamente por el gestor de BD. Solo costo de tiempo de ejecución

Ejercicio

● Usando el enfoque de Relación Universal, modele la base de datos de un banco, con la siguiente información:

● El banco ofrece a sus clientes cuentas corrientes y cuentas de ahorro. Las cuentas pertenecen a una sucursal.

● De los clientes se almacena la información básica: identificación, nombre, apellido, dirección de correspondencia, uno o varios números de teléfono, y empresa donde labora.

● De las sucursales se tiene código, nombre y dirección.● Las cuentas tienen saldo a la fecha y movimientos de

depósito y retiro, en los cuales se registra un número de transacción, el valor, la fecha, y la sucursal en que se realizó