Skip to content

Instantly share code, notes, and snippets.

@brunocascio
Last active July 4, 2024 21:37
Show Gist options
  • Save brunocascio/f669aa9a4686ba3fe6a80b40b71f8552 to your computer and use it in GitHub Desktop.
Save brunocascio/f669aa9a4686ba3fe6a80b40b71f8552 to your computer and use it in GitHub Desktop.
Conceptos de Normalización de Bases de datos

Normalización de Bases de datos

Fuentes:

https://www.dropbox.com/sh/bygsxsk9hfvflev/AACy3g3746WmBfNOHmAvDqyAa/material%20adicional/Normalizacion?dl=0&preview=Apunte_Normalizacion_Completo_2013.pdf

¿Por qué Normalizar?

En el diseño de bases de datos existen propiedades indeseables que no deberían presentarse en los esquemas. Éstas son:

  • Repetición de información (Por ejemplo, mala división de relaciones)
  • Mala representación de la información (Por ejemplo, relaciones con cláusulas mal definiadas, campos opcionales que debería ser obligatorios)
  • Pérdida de información la misma (Por ejemplo, realaciones relacionadas por un campo que no es clave)

Conceptos relacionados con Normalización:

• Dependencias funcionales

• Dependencias Multivaluadas

• Superclave

• Clave candidata

• Clave primaria

• Atributo primo

• Formas normales

Dependencias funcionales

Las dependencias funcionales sirven para dar semántica a las tablas y para definir restricciones sobre las mismas. Una dependencia funcional significa que para un X dado siempre se recupera el mismo valor de Y.

Dependencia funcional trivial

X -> Y es trivial si Y es un subconjunto de X (Y ⊆ X). Por ejemplo, a,b -> a {a} es un subconjunto de {a,b}

Dependencia funcional total

X -> Y es una dependencia funcional total si la eliminación de cualquier atributo A de X hace que la dependencia funcional deje de ser válida.

Dependencia funcional parcial

X -> Y es una dependencia funcional parcial si la eliminación de cualquier atributo A de X hace que la dependencia funcional siga siendo válida.

Axiomas básicos


Reflexibidad

X es un conjunto de atributos y Y ⊆ X entonces X -> Y

Ejemplo: X = (a,b) y Y = (a), es decir, a ⊆ (a,b) luego se puede decir que a,b -> a

Aumento

Si X -> Y y Z es un conjunto de atributos, entonces Z,X -> Z,Y

Transitividad

Si se tiene X -> Y y Y -> Z, entonces se tiene la dependencia funcional X -> Z

Axiomas que se deducen a partir de los axiomas básicos


Union

Si se tienen X -> Y y X -> Z, entonces se tiene X -> Y,Z

Descomposición

Si se tiene X -> Y,Z, entonces X -> Y y X -> Z

Pseudotransitividad

Si se tiene X -> Y y Y,Z -> W, entonces X,Z -> W

Análisis de Pérdida de Información


Para corroborar que no se pierda información al particionar un esquema R en dos subesquemas R1 y R2 se debe cumplir alguna de las siguientes condiciones:

  • R1 ∩ R2 es clave en el esquema R1
  • R1 ∩ R2 es clave en el esquema R2

Y además se debe cumplir que R1 ∪ R2 = R {esto asegura que no se perdieron atributos}

Análisis de pérdida de dependencias funcionales cuando se particiona un esquema R.


Cuando se particiona un esquema R, además de no perder información, se debe tener en cuenta que no se pierdan dependencias funcionales. Para ello se debe verificar que cada una de las dependencias funcionales que valían en el esquema R, sigan valiendo en alguna de las particiones.

Cuando se chequean las dependencias funcionales pueden ocurrir dos cosas:

a) los atributos de la dependencia funcional original quedaron todos incluidos en alguna de las particiones generadas b) los atributos de la dependencia funcional original quedaron distribuidos en mas de una partición

Algoritmo para analizar la pérdida de dependencias funcionales


Res = x 
Mientras Res cambia 
  Para i= 1 to cant_de_ particiones_realizadas   
    Res = Res ∪ ((Res ∩ Ri)+ ∩ Ri)

Ejemplo: Supongamos que se tiene el siguiente esquema:

R2(a,b,c,d)

Con el siguiente conjunto de dependencias funcionales:

F = {a->b, b -> c, c->d, d->a}

Supongamos que se realizan las siguientes particiones del esquema R2:

R2.1(a,b) R2.2(b,c) R2.3(c,d)

Con el algoritmo para analizar pérdida de dependencias funcionales, se puede verificar si se perdió la dependencia funcional d -> a.

A continuación se ejecuta el algoritmo partiendo de Res = d:

Paso i=1)

Res= d ∪ ((d ∩ {a,b})+ ∩ {a,b})    
Res= d 

Paso i=2)

Res= d ∪ ((d ∩ {b,c})+ ∩ {b,c})    
Res = d 

Paso i=3)

Res= d ∪ ((d ∩ {c,d})+ ∩ {c,d}) 
Res= d ∪ ((d)+ ∩ {c,d}) 
Res= d ∪ (({a,b,c,d} ∩ {c,d}) 
Res= d ∪ {c,d}                               
Res = {c,d}   

Se termina la iteración y Res cambio, entonces se comienza nuevamente.

Paso i=1)

Res= {c,d} ∪ (({c,d} ∩ {a,b})+ ∩ {a,b})     
Res = {c,d} 

Paso i=2)

Res= {c,d} ∪ (({c,d} ∩ {b,c})+ ∩ {b,c})     
Res= {c,d} ∪ ((c) + ∩ {b,c})   
Res= {c,d} ∪ ({a,b,c,d} ∩ {b,c}) 
Res= {c,d} ∪ ({b,c})     
Res = {c,d,b} 

Paso i=3)

Res= {c,d, b} ∪ (({c,d,b} ∩ {c,d})+ ∩ {c,d})     
Res = {c,d,b} 

Se termina la iteración y Res cambio, entonces se comienza nuevamente.

Paso i=1)

Res= {c,d,b} ∪ (({c,d,b} ∩ {a,b})+ ∩ {a,b})
Res = {c,d,b,a}

En este paso se ve que partiendo del atributo d, se recupera el atributo a, entonces la dependencia funcional d -> a NO SE PERDIÓ.

Dependencias Multivaluadas

X-->> Y si dado un valor de X, hay un conjunto de valores de Y asociados y este conjunto de valores es independiente de los atributos de R-X-Y.

Una dependencia multivaluada de la forma X->> Y, es trivial cuando el conjunto de atributos {X,Y} conforma el total de los atributos del esquema.

Superclave

Una superclave es un conjunto K de atributos, los cuales conjuntamente, identifican unívocamente a una entidad en el conjunto de entidades. Si K es superclave cualquier conjunto que contenga a K es superclave.

Ejemplo:

R = (a,b,c,d)

Si {a} es superclave, entonces {a,b} tambien lo es, ya que es un superconjunto que contiene a {a}.

Clave Candidata

Una clave candidata es una superclave en la cual ningún subconjunto propio es superclave. Puede existir más de una clave candidata.

Ejemplo:

R = (a, b, c, d)

Aquí a como d, son superclaves, y ambas claves candidatas.

Clave Primaria

Cuando un esquema R tiene mas de una clave candidata, en el proceso de normalización queda sólo una de ellas y las otras quedan divididas en el esquema, sin que esto implique pérdida de información. Esa clave candidata que queda luego del proceso, se denomina clave primaria

Atributo primo

Un atributo del esquema de relación R se denomina atributo primo de R si es miembro de cualquier clave candidata de R.

Ejemplo:

R = (#nAlumno, #dni, #materia)

Se sabe que un alumna cursa muchas materias. Entonces tenemos las siguientes claves candidatas:

(cc1) = (#nroAlumno, #materia) (cc2) = (#dni, #materia)

En este caso, #materia es un atributo primo.

Formas Normales

1FN:

Se prohíben los atributos multivaluados (aquellos que tienen múltiples valores), los atributos compuestos (aquellos compuestos a su vez de otros atributos) y sus combinaciones.

2FN:

Una relación R está en 2FN si está en 1FN y si todo atributo no primo depende funcionalmente de manera total de la clave primaria de R.

Ejemplo:

EMPLEADO_PROYECTO(dni, nombreEmpleado, horasTrabajadas, proyecto, nombreProyecto, lugarProyecto)

Teniendo la cc, dni, proyecto

Y las siguientes dfs.

df1) dni -> nombreEmpleado

df2) proyecto -> nombreProyecto, lugarProyecto

df3) dni, proyecto -> horasTrabajadas

Vemos que para recuperar el atributo no primo nombreEmpleado de manera únivoca, no necesitamos de proyecto. Con esto decimos entonces que nomreEmpleado no depende de manera total de la cc. Entonces, existe una dependencia funcional parcial, dando como conclusión que el esquema no está en 2FN.

3FN

Se basa en el concepto de dependencia funcional transitiva. Un esquema esta en 3NF si esta en 2NF y ningún atributo no primo de R depende transitivamente de la clave primaria. Es decir, un esquema esta en 3NF siempre que una dependencia funcional X -> A se cumple en R, o bien:

a) X es superclave de R

b) A es un atributo primo de R

Ejemplo:

Dado el siguiente esquema:

EMPLEADO_DEPARTAMENTO(nombreApellido, dni, fechaNac, direccion, #Depto, nombreDepto)

Se sabe que un empleado trabaja únicamente en un departamento, y que en cada departamento trabajan varios empleados.

La clave candidata es dni.

Se tienen las siguientes dependencias funcionales:

1. dni -> nomApellido, fechaNac, direccion, #Depto

2. #Depto -> nombreDepto

La relación EMPLEADO_DEPARTAMENTO no esta en 3NF ya que existe la dependencia funcional 2 que no cumple con ninguna de las dos condiciones de 3NF, es decir:

  • #Depto no es superclave en R
  • nombreDepto no es un atributo primo de EMP_DEPTO

Forma normal de Boyce-Cod (BCNF)

Es más restricta que la 3FN, lo que significa que toda relación que este en BCNF estará en 3NF pero no necesariamente una relación en 3NF esta en BCNF. Un esquema de relación esta en BCNF si, siempre que una dependencia funcional X -> A es válida en R, entonces X es superclave de R. Es decir, la única diferencia entre BCNF y 3FN es que en BCNF no esta presente la condición b) de 3NF.

Ejemplo:

Supongamos que se tiene el siguiente esquema:

R(#nroalumno, dni, #materia)

Donde se sabe que un alumno cursa muchas materias. Las claves candidatas (cc) de este esquema son:

cc1:(dni, #materia)

cc2: (#nroalumno, #materia)

Se tienen las siguientes dependencias funcionales:

1. #nroalumno -> dni

2. dni -> #nroalumno

R no esta en BCNF ya que al menos #nroalumno no es superclave de R.

4FN:

Se basa en el concepto de dependencia multivaluada. Un esquema esta en 4FN cuando:

  • no existen dependencias multivaluadas ó
  • sólo existe una dependencia multivaluada trivial
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment