Formas Pokenormales
Al diseñar las relaciones que deben formar parte de un esquema relacional de bases de datos hay ciertos aspectos que se deben considerar de forma que se asegure que al agregar los datos en el esquema estos no presenten anomalías. En este artículo, voy a discutir distintas anomalías que pueden presentarse en esquemas relacionales y cómo pueden ser erradicados utilizando formas normales. Las formas normales son condiciones que todas las tablas de un esquema deben cumplir para así garantizar ciertas propiedades deseables. Las formas normales fueron propuestas principalmente por Edgar F. Codd durante los 70s.
Para entender de mejor forma las condiciones que se requieren en cada forma normal, es recomendable que conozcas lo que es una llave y una dependencia funcional en el modelo relacional. En este post puedes encontrar definiciones y ejemplos también.
Vamos a guiar la explicación a través de una base de datos que mantiene el registro de los Pokémon que son capturados por los distintos entrenadores. En la Tabla 1, se muestra una forma sobre cómo organizar nuestros datos. La tabla contiene una columna con el identificador del entrenador y la segunda contiene una lista con las criaturas capturadas por dicho entrenador. La llave de la tabla es el nombre del entrenador por lo que se muestra en negrita y cursiva.
Entrenador | Pokemon |
---|---|
Ash | [Pikachu, Caterpie, Charmander, …] |
Misty | [Staryu, Goldeen, Starmie, …] |
Gary | [Krabby, Nidoking, Arcanine, …] |
Como se puede adivinar, es al menos extraño el manejar listas de elementos en una base de datos relacional. El utilizar ese tipo de estructuras en un atributo de una tabla puede producir dificultades al momento de implementar la base de datos. ¿Las colecciones pueden tener un tamaño máximo? ¿Cómo busco, agrego, ordeno o elimino eficientemente un elemento de la colección?
¿Cómo se puede solucionar? La solución más ingenua, podría ser agregar más columnas, una para cada Pokémon atrapado. Esto supone nuevos problemas: ¿Cuántas columnas son suficientes? ¿Qué pasa con las columnas que no son utilizadas? ¿Cómo saber en cuál columna agregar la captura?
Por lo general, la solución a este tipo de problemas es utilizar las llaves de ambas entidades relacionadas. En el caso del ejemplo, serían tanto el nombre del entrenador como el del Pokémon. El resultado puede apreciarse en la Tabla 2. Como un entrenador puede tener varios Pokémon tanto el nombre del entrenador como el nombre del Pokémon son la llave de la tabla. (Efectivamente esto restringe que un mismo entrenador capture dos pokémon del mismo nombre. ¿Cómo solucionar esto?)
Entrenador | Pokemon |
---|---|
Ash | Pikachu |
Ash | Caterpie |
Ash | Charmander |
Misty | Staryu |
… | … |
Cuando tenemos una relación como la de la Tabla 2, decimos que cada atributo tiene valores atómicos, es decir, valores que no son colecciones (conjuntos, listas, etc.). Este tipo de relaciones están en Primera Forma Normal.
Supongamos que ahora que tenemos más información sobre el entrenador, sobre el Pokémon capturado y sobre la captura en sí. Por ejemplo, queremos almacenar la ciudad de la que el entrenador proviene, la salud y tipo del Pokémon capturado y la fecha y hora de la captura. Si seguimos con lo que veníamos haciendo en la Tabla 2, podríamos proponer un esquema como el que se ve en la Tabla 3. Podemos ver que la llave sigue siendo el nombre del entrenador y el del pokémon, sin embargo, al agregar también la fecha de captura a la llave podemos admitir que un entrenador capture más de un pokémon de la misma especie en momentos diferentes.
Entrenador | Origen | Pokemon | Tipo | HP | Fecha Captura |
---|---|---|---|---|---|
Ash | Pueblo Paleta | Pikachu | Eléctico | 35 | 01-04-1997 10:20 |
Ash | Pueblo Paleta | Caterpie | Insecto | 45 | 02-04-1997 11:34 |
Ash | Pueblo Paleta | Charmander | Fuego | 39 | 05-04-1997 19:12 |
Misty | Ciudad Celeste | Staryu | Agua | 30 | 22-03-1995 09:44 |
Tabla 3: Entrenadores y sus Pokémon, con datos del entrenador, Pokémon y captura
En el modelo de la Tabla 3, podemos encontrar varios problemas. Primero notamos que hay redundancia, pues cada vez que un entrenador capture un nuevo pokémon debemos repetir su ciudad de origen. Esto conlleva varias anomalías consigo, las cuales vamos a enumerar:
- Anomalía de Actualización: Si quisieramos modificar la ciudad de origen de un entrenador debemos asegurarnos de cambiarla correctamente en todas las filas que se refieren al entrenador. El no hacerlo, lleva a un estado inconsistente de la base de datos.
- Anomalía de Inserción: No podemos agregar un nuevo entrenadoral sistema si es que no ha capturado ningún pokémon aún. Esto pues la columna pokémon es parte de la llave y por lo tanto no admite valores nulos. Lo mismo con un pokémon, no tendremos registro de la especie o el tipo si nadie lo ha capturado.
- Anomalía de Borrado: Si un entrenador decide liberar a todos sus pokémon capturados, ¿qué hacemos con él? ¿Borramos todos sus datos?
¿Cuál es el origen de estas anomalías? En este caso se debe a que hay atributos cuyo valor depende solo del entrenador. En este caso, la ciudad de origen depende del entrenador. Por otro lado, hay atributos que dependen solo del pokémon en cuestión, como el tipo. La salud del pokémon es un caso distinto, pues al contrario del tipo, no depende solo del pokemon del que se trata, sino que también depende del entrenador y de cuándo fue capturado1. Cuando se define una llave en una tabla, se espera que todos los atributos no-primos dependan de todos los atributos de la llave en conjunto, no solo de una parte de ésta. Eso es lo que en este caso produce las anomalías: hay atributos no primos que no dependen funcionalmente de la llave completa, sino que de un subconjunto (propio2) de ésta.
Entonces, la Segunda Forma Normal (2NF) indica que un esquema está en primera forma normal y además, ningún atributo no primo depende funcionalmente de algún subconjunto propio de alguna de las llaves candidatas. También puede leerse como que todos los atributos no primos deben depender funcionalmente de todas las llaves candidatas completas.
Nuestro esquema de Tabla 3 no cumple con la segunda forma normal. La única llave candidata (y por lo tanto la llave primaria) es {Entrenador, Pokemon, Fecha}
y tenemos las dependencias funcionales Entrenador
¿Cómo podemos lograr 2NF? En este caso en particular basta con tener una tabla para los entrenadores, otra para las especies de pokémon y otra para las capturas. En las tablas 4, 5 y 6 podemos encontrar el resultado de la normalización. Bastó en este caso con tomar las dependencias funcionales Entrenador
Entrenador | Origen |
---|---|
Ash | Pueblo Paleta |
Misty | Ciudad Celeste |
Gary | Pueblo Paleta |
Tabla 4: Entrenadores y sus ciudades de origen
Pokemon | tipo |
---|---|
Pikachu | Eléctrico |
Caterpie | Insecto |
Staryu | Agua |
Tabla 5: Especies de pokémon y sus tipos
Entrenador | Pokemon | HP | Fecha Captura |
---|---|---|---|
Ash | Pikachu | 35 | 01-04-1997 10:20 |
Ash | Caterpie | 45 | 02-04-1997 11:34 |
Ash | Charmander | 39 | 05-04-1997 19:12 |
Misty | Staryu | 30 | 22-03-1995 09:44 |
Tabla 6: Entrenadores y sus pokémon
El conjunto de las tablas 4, 5 y 6 cumple ahora con 2NF. Supongamos ahora que además del pueblo de origen del entrenador, queremos también saber la región de la que provienen, como se ve en la Tabla 7. En dicha tabla, es fácil notar que se cumple la dependencia funcional
Origen
Entrenador | Origen | Región |
---|---|---|
Ash | Pueblo Paleta | Kanto |
Misty | Ciudad Celeste | Kanto |
Gary | Pueblo Paleta | Kanto |
Professor Kukui | Hau’oli | Alola |
Tabla 7: Entrenadores y sus ciudades y regiones de origen
La Tercera Forma Normal (3NF) nos permite eliminar este tipo de anomalías. Un esquema está en 3NF sí está en segunda forma normal y ningún atributo no primo depende transitivamente de una llave candidata. La última condición también puede expresarse como que todos los atributos están determidados funcionalmente solo por las llaves candidatas y no por atributos no primos. En el caso de la Tabla 7 tenemos la Región depende transitivamente de la llave: Entrenador
Para normalizar una tabla que no está en 3NF, se puede utilizar el siguiente algoritmo (aunque en la mayoría de los casos solo basta usar el sentido común):
INPUT: (R, F) R un esquema y F un conjunto de relaciones funcionales
OUTPUT: El esquema normalizado
F` := reducir(F)
por cada X->A en F`:
Crear esquema (X U A, X->A)
Si en los esquemas creados no está la llave de (R, F), agregarla
En reducir, lo que se hace es eliminar dependencias funcionales redundantes y dejarlas de la forma
Pueblo | Región |
---|---|
Pueblo Paleta | Kanto |
Ciudad Celeste | Kanto |
Hau’oli | Alola |
Tabla 8: Pueblos y las regiones a las que pertenecen
¿Estamos listos entonces? Falta un poco, aunque muchas veces se considera que un esquema en 3NF está lo suficientemente normalizado, aún hay ciertas cosas que pueden surgir.
Supongamos ahora una tabla para guardar los duelos contra líderes de gimnasio. Vamos a suponer que un gimnasio puede tener solo un líder y que ese líder pertenece solo a un gimnasio. Podemos ver datos de ejemplo en la Tabla 9.
Lider | Entrenador | Gimnasio | Fecha | Ganador |
---|---|---|---|---|
Brock | Ash | Ciudad Plateada | 03-04-1997 | Brock |
Brock | Ash | Ciudad Plateada | 04-04-1997 | Nadie |
Misty | Ash | Ciudad Celeste | 18-04-1997 | Empate |
Tabla 9: Registro de duelos en gimnasios
Podemos inferir que una llave es esta tabla es
Un esquema está en Forma Normal de Boyce-Codd (FNBC) si para cada una de sus dependencias funcionales
El algoritmo que se sigue para normalizar es el siguiente:
Input: C ={(R0, F0)} # Esquema y dependencias iniciales
Output: N # Esquema normalizado en FNBC
for (R, F) in C:
if (R, F) no está en FNBC:
tomar X -> Y en F que viola FNBC
C = C U (R-Y, F1) # F1 son las df sobre los atributos en R-Y
C = C U (XY, F2) # F2 son las df sobre los atributos en XY
Entonces en el caso de la Tabla 9, tomamos una de las dependencias que viola FNBC, {lider}
Para cerrar, quiero mencionar dos cosas. La primera, es que existen la cuarta, quinta y sexta formas normales, las cuales tratan de reparar anomalías cada vez más difíciles de encontrar en el mundo real. La segunda, es que la existencia de estas reglas y definiciones para mejorar el diseño relacional se sugieren principalmente para evitar las anomalías, sin embargo, es posible que se esté desarrollando una aplicación donde hayan otros elementos que sean más críticos que la normalización de las tablas, por lo que no hay que ser puristas, sino que tomar en cuenta el dominio y requisitos de lo que se está haciendo antes de llegar y dejar todo en sexta forma normal. Hay escenarios en los que se prefiere tener redundancia para aumentar la eficiencia antes que tener que realizar joins entre miles de tablas. Hay escenarios en los que se prefiere lo contrario.
###Referencias
- Codd, Edgar F. “A relational model of data for large shared data banks.” Communications of the ACM 13.6 (1970): 377-387.
- Codd, Edgar F. “Recent Investigations into Relational Data Base Systems.” IBM Research Report RJ1385 (April 23, 1974).
- Ramakrishnan, Raghu, and Johannes Gehrke. Database management systems. McGraw Hill, 2000.
Esta diferencia ocurre pues un pokémon es una especie y una instancia a la vez: todos los Pikachu son eléctricos, pero cada uno tiene un HP distinto. La forma de diferenciar dos Pikachu distintos, es por el entrenador que los capturó. ↩︎
Un subconjunto propio es un subconjunto con cardinalidad estrictamente menor que el conjunto original, es decir
↩︎