Tema 7.2 - Normalización

Introducción

📖

Objetivos de la Normalización

Decidir si una relación es correcta, es decir, no redundante.

Si es incorrecta:

Descomponer la relación en varias relaciones correctas.
Descomponer la relación sin pérdidas.

La Teoría de la Normalización

Consigue una formalización en el diseño lógico.

Permite afrontar el problema de diseño de bases de datos relacionales de manera rigurosa y objetiva.

📢

La Normalización se basa en el concepto de Dependencia Funcional.

Posibles problemas durante el proceso de Normalización

Incapacidad para almacenar ciertos hechos.

Redundancias y ambigüedades.

Pérdida de información y dependencias funcionales.

Existencia de valores nulos (inaplicables).

💀

Anomalías

Al realizar un diseño inadecuado podemos incurrir en problemas con el diseño.

Anomalías de inserción → Dependemos de conocer los valores de la tabla está referenciada a través de la clave ajena.

Anomalías de borrado → Al borrar un elemento, si este elemento contenía información de la entidad con la que se relaciona, perderé esa información al borrar el último elemento.

Anomalía de modificación → Al modificar una tupla, puede ocurrir que una tupla tenga información no coincidente con los valores de otras tuplas en el mismo atributo.

📔

Palabras clave

Implicante / Implicado → El implicante es lo que está a la izq. de una implicación, y el implicado lo que está a la derecha: $Ite \rarr Ido$

Descriptores → Subconjunto de los atributos de una relación que nos son claves primarias.

Dependencia funcional → Expresion donde se expresa la relación a través de la cual un descriptor deriva en otro.

Ejemplos

$A \rarr B$

$AB \rarr C$

$A \rarr BC$

$ABC \rarr DE$

Dependencias Funcionales

📖

Las dependencias son propiedades inherentes al contrenido semántico de los datos.

Son restricciones de usuario del Modelo Relacional.

Se deben cumplir en cualquier extensión de un esquema.

No se pueden deducir a partir de una extensión del esquema.

Tipos de dependencias

Funcionales.
Multivaluadas.
Jerárquicas.
Combinatorias.

Composición del esquema de relación

$R \ (A,DEP)$
$A:$ Conjunto de atributos de la relación R.
$DEP:$ Conjunto de dependencias existentes entre los atributos.

📖

Sea el esquema de relación $R(A,DF)$

$A$ → Conjunto de atributos de la relación $R$

$DF$ → Conjunto de dependencias que existen entre los atributos de la relación

ℹ️

Existen dos tipos de atributos

Identificadores → Estos identifican unívocamente una ocurrencia de una entidad (claves candidatas)

Descriptores → Estos describen la ocurrencia (el resto de atributos)

Propiedades de los descriptores

📔

Descriptores equivalentes

Dos descriptores son equivalentes si:

X \rightarrow Y \land Y \rightarrow X

📔

Una dependencia funcional es trivial si

El implicado forma parte del implicante:

X\rightarrow Y

Y \subseteq X

Ejemplo

ABC \rightarrow B

📔

Una dependencia funcional es plena o completa si todos los miembros del implicante son necesarios.

Cuando un atributo es redundante, significa que no es necesario para resolver el implicado, por lo que podríamos prescindir de él (miembro $\small{X}$ del implicante)

📔

A este miembro del implicante se sobra se le dice que es extraño

📔

Dependencia transitiva

Una dependencia funcional es transitiva cuando esta se alcanza tras encadenar varias implicaciones. Se denota por:

X \text{---} \rarr Y

💡

Las dependencias transitivas también son dependencias funcionales

📔

Cierre de una dependencia

Se le dice cierre de una dependencia al conjunto de todas las dependencias funcionales implicables a partir de otra. Se denota con el superíndice

+

tras los atributos pertenecientes a la dependencia funcional

Ejemplo

Teniendo el atributo

A

y el

B

, tenemos

AB

. El cierre se denota por

AB^+

Axiomas de Armstrong

📖

Axiomas básicos

Reflexividad
Si $Y \subseteq X$ , entonces $X \rarr Y$ (trivial)

Aumento
Si $X \rarr Y, Z\subseteq W$ entonces $XW \rarr YZ$

Transitividad
Si $X \rarr Y$ y $Y \rarr Z$ entonces $X\rarr Z$

📖

Axiomas derivados

Proyectividad
Si $X \rarr Y$ entonces $X \rarr Y'$ si $Y' \subseteq Y$

Unión
Si $X \rarr Y$ y $X \rarr Z$ entonces $X \rarr YZ$

Pesudotransitividad
Si $X \rarr Y$ e $YW \rarr Z$ entonces $XW \rarr Z$

Verificar si una dependencia funcional es cierta

🧠

Para saber si una dependencia formal es cierta, debemos obtener el cierre de dicha dependencia funcional.

El cierre se obtiene implicando el implicante hasta llegar a obtener todos los atributos del implicado.

Sintaxis
$X \rarr Y\ \text{es cierta si}\ Y \in X^+$
La dependencia funcional $X \rarr Y$ es cierta si $Y$ pertenece al cierre de $X$

Algoritmo para la obtención de claves candidatas de una relación

📔

Un recubrimiento irredundante/minimal es un conjunto

DF

que no puede ser reducido/simplificado más.

🧮

Cálculo de un recubrimiento mínimo

Si para $DF_1$ y $DF_2$ sus cierres son iguales $(DF_1^+ = DF_2^+)$ , entontes $DF_1$ y $DF_2$ son equivalentes $(DF_1 \equiv DF_2)$

1️⃣ Un único atributo en el implicado

2️⃣ Irreducible por la izquierda (sin atributos extraños)

3️⃣ Sin DF redundantes

📔

Una relación sin independencias ni equivalencias $(R_{sie})$ es un subconjunto de la relación original en la que no se incluyen ni los descriptores independientes ni las dependencias redundantes

Partimos de una relación

R(A, DF)

, siendo

DF

un recubrimiento irredundante

0️⃣ Detectar dependencias triviales

Si encontramos una dependencia trivial del estilo $A \rightarrow A$ , la podemos excluir.

1️⃣ Simplificar dependencias mediante cierres

Intentamos hallar una simplificación a las dependencias compuestas mediante el cálculo de sus cierres correspondientes.
Ejemplo
ℹ️
Dadas las dependencias:
$A,B\ \rightarrow\ C$
$A\ \rightarrow\ D$
$D\ \rightarrow\ C$
Dadas estas dependencias, podemos observar que para $AB \rarr C$ :
$A$ $A$ $A$ $A^+ = [A,\ D,\ C]$
El cierre de $A$ incluye a $C$ por lo que no es extraño
$B$ es extraño? → $B^+ = [B]$
El cierre de $B$ no incluye $C$ por lo que es extraño
Determinamos que $B$ es extraño, y podemos prescindir de él.

2️⃣ Eliminación de descriptores indepentientes

Encontramos los descriptores que no aparecen en las dependencias y simplificamos el esquema mediante su eliminación.

3️⃣ Eliminación de descriptores equivalentes

Encontramos los descriptores que son equivalentes $(X \lrarr Y)$ .
Para eliminar este tipo de dependencia:
Elegimos uno de los descriptores para conservarlo $(X)$ .
Eliminamos la dependencia $Y \rarr X$ .
Sustituimos en el resto de dependencias donde aparezca $Y$ por $X$ .
Ejemplo
ℹ️
Dadas la dependencias:
$A \rightarrow B$
$B \rightarrow A$
$B \rightarrow C$
Podemos observar que:
$A \leftrightarrow B$
Como $A$ y $B$ son equivalentes, eliminamos la dependencia $B \rarr A$ y la dependencia $B \rightarrow C$ pasa a ser $A \rightarrow C$

4️⃣ Determinación de un descriptor que será parte de la clave $R_{sie}$

Buscamos los descriptores que sólo aparecen como implicantes.
Estos descriptores estarán sí o sí en $K_p$ .

5️⃣ Determinación de un descriptor de $R_{sie}$ (implicante o implicado)

Hallamos el cierre de $K_p$ ( ${K_p}^+$ )
Si conseguimos incluir todo el conjunto, pasamos al siguiente paso
Si no conseguimos alcanzar todo el conjunto, debemos incluir implicados a la clave y repetir este paso con esta nueva clave.

6️⃣ Añadir atributos independientes

Añadimos los atributos independientes de la clave original para conformar una clave $K_p$ completa.

7️⃣ Añadir descriptores equivalentes

Recuperamos las equivalencias que habíamos eliminado previamente y obtenemos las distintas claves de la relación.
Ejemplo
ℹ️
Dado el conjunto de claves $K_p = [A,\ C,\ D]$ determinamos que los descriptores $A$ y $B$ son equivalentes $(A \lrarr B)$ . Esto nos lleva a determinar las siguientes posibles claves
$K_1 = [A,\ C,\ D]$
$K_2 = [B,\ C,\ D]$

Formas Normales

📖

Un esquema de relación está en una cierta forma normal si satisface un conjunto de restricciones.

Cuanto más alta la forma normal, menores problemas de mantenimiento

Codd propuso inicialmente tres formas normales (1FN, 2FN y 3FN).

En 1974 introdujo una definición más restrictiva de la 3FN que se denominó Forma Normal de Boyce-Codd (FNBC).

La 4FN se basa en dependencias multivaluadas.

La 5FN se basa en dependencias de proyección-combinación.

💡

Cada forma nomal, en un subconjunto de las anterirores

(FNBC \subset 3FN \subset 2FN \subset 1FN)

1FN - Primera Forma Normal

📖

Propiedades

Cada atributo sólo toma un valor del dominio (un atributo de una tupla no puede tomar más de un valor).

💡

Todas las relaciones cumplen esta primera forma normal.

Ejemplo

Tabla no relacional (no cumple la 1FN)
Código
Nombre
Beca
E1
Juan
Beca1 Beca2
E2
María
Beca3
E3
Pepe
Beca2 Beca3

Relación (cumple la 1FN)
Código
Nombre
Beca
E1
Juan
Beca1
E1
Juan
Beca2
E2
María
Beca3
E3
Pepe
Beca2
E3
Pepe
Beca3

2FN - Segunda Forma Normal

📖

Propiedades

Cumple los requisitos de la 1FN

Cada atributo no principal tiene DF completa (sin redundancias) respecto de cada una de las claves.

🔴

No se cumple cuando algún atributo no principal depende de algún subconjunto de la clave.

💡

Los esquemas en 2FN se obtienen sin pérdida de información ni de dependencias $(R_{sie})$ .

Están en Segunda Forma Normal…

Relaciones binarias.

Relaciones con claves simples.

Relaciones en las que todos sus atributos son principales.

Ejemplo

Estudiante_Beca (AT, DEP) donde:
AT = {Cod_Est, Cod_Beca, Fecha_Sol, Título}
DEP = {Cod_Est, Cod_Beca → Fecha_Sol, Cod_Est → Título}
Transformamos en:
K = {Cod_Est, Cod_Beca}
Estudiante_Beca1 (AT1, DEP1) donde:
AT1 = {Cod_Est, Cod_Beca, Fecha_Sol}
DEP1 = {Cod_Est, Cod_Beca → Fecha_Sol}
Estudiante (AT2, DEP2) donde:
AT2 = {Cod_Est, Título}
DEP2 = {Cod_Est, Título}

3FN - Tercera Forma Normal

📖

Propiedades

Cumple los requisitos de 2FN

No existe un atributo no principal que dependa transitivamente de alguna clave de R.

🔴

No se cumple cuando existen atributos no principales que dependen de otros atributos no principales.

💡

Los esquemas en 3FN se obtienen sin pérdida de información ni de dependencias.

Están en Tercera Forma Normal…

Relaciones binarias.

Relaciones que tienen, como mucho, un atributo no principal.

Ejemplo

Estudiante_Beca (AT, DEP) donde:
AT = {Cod_Est, Cod_Proy, Nom_Proy}
DEP = {Cod_Proy → Nom_Proy , Cod_Est → Cod_Proy}
Transformamos en:
K = {Cod_Est}
ANP = Cod_Proy, Nom_Proy
Estudiante1 (AT1, DEP1) donde:
AT1 = {Cod_Est, Cod_Proy}
DEP1 = {Cod_Est → Cod_Proy}
Proyecto (AT2, DEP2) donde:
AT2 = {Cod_Proy, Nom_Proy}
DEP2 = {Cod_Proy → Nom_Proy}

FNBC - Forma Normal de Boyce-Codd

📖

Propiedades

Se encuentra previamente en 3FN

Las claves candidatas compuestas no se solapan.

💡

Los esquemas en FNBC pueden sufrir pérdida de dependencias formales.

Están en Forma Normal de Boyce-Codd

Relaciones binarias.

Relaciones en las que todo implicante (determinante) es una clave candidata.

Ejemplo

Clase (AT, DEP) donde:
AT = {Cod_Est, Cod_Prof, Materia}
DEP = {(Cod_Est, Materia) → Cod_Prof, Cod_Prof → Materia}
Claves candidatas K: {Cod_Est, Materia} y {Cod_Est, Cod_Prof}
Como $K_1$ y $K_2$ se solapan, no se encuentra en $FNBC$
Clase1 (AT1, DEP1) donde:
AT1 = {Cod_Est, Cod_Prof}
DEP1 = {}
Proyecto (AT2, DEP2) donde:
AT2 = {Cod_Prof, Materia}
DEP2 = {Cod_Prof→ Materia}
Se produce pérdida de Dependencias Funcionales
(Cod_Est, Materia) → Cod_Prof

Resumen de Formas Normales

❓

¿Cómo detectar en que forma normal se encuentra una relación?

$\text{1FN}$

Las tuplas están claramente divididas (ninguna columna almacena más de un dato).

$\text{2FN}$

Todo atributo no principal dependen de la clave primaria al completo, directamente o transitivamente.

$\text{3FN}$

Un atributo no puede depender transitivamente de la clave.
$\text {Si} \ (A \rightarrow B \rightarrow C) \ \text {entonces} \ (A \rightarrow C) \ \text {No sería 3FN}$

$\text{FNBC}$

No debe haber solapamiento de claves primarias.
$\text {Si} \ k_1 \cap k_2 \neq \empty \rightarrow \text {No \ estamos \ en \ FNBC}$

Código	Nombre	Beca
E1	Juan	Beca1 Beca2
E2	María	Beca3
E3	Pepe	Beca2 Beca3

Tema 7.2 - Normalización

Introducción

Dependencias Funcionales

Propiedades de los descriptores

Axiomas de Armstrong

Verificar si una dependencia funcional es cierta

Algoritmo para la obtención de claves candidatas de una relación

Formas Normales

1FN - Primera Forma Normal

2FN - Segunda Forma Normal

3FN - Tercera Forma Normal

FNBC - Forma Normal de Boyce-Codd

Resumen de Formas Normales

1FN\text{1FN}1FN

2FN\text{2FN}2FN

3FN\text{3FN}3FN

FNBC\text{FNBC}FNBC

$\text{1FN}$

$\text{2FN}$

$\text{3FN}$

$\text{FNBC}$