Tema 7. Diseno ˜ de bases de datos relacionales. Juan Ignacio Rodr´ıguez de Leon ´ Resumen Normalizacion ´ y dependencias de datos. Motivacion ´ de cada forma normal. Significado intuitivo de cada tipo de dependencia de datos. Primera forma normal. Dificultades en el diseno ˜ de bases de datos relacionales. Dependencias funcionales. Descomposicion. ´ Propiedades deseables de la descomposicion. ´ Forma normal de Boyce-Codd. Tercera forma normal. Cuarta forma normal. Otras formas normales. Proceso general del diseno ˜ de bases de datos.
´ Indice 1. Normalizacion ´ de datos 1.1. Formas normales . . . . . . . . . . . . 1.2. primera forma normal (1NF) . . . . . 1.3. dependencia funcional . . . . . . . . . 1.4. Segunda forma normal (2FN) . . . . . 1.5. Tercera forma normal (3NF) . . . . . . 1.6. Forma normal de Boyce-Codd (BCNF) 1.7. Comparacion ´ entre FNBC y 3FN . . . 1.8. Dependencias multivaloradas . . . . . 1.9. Cuarta forma normal 4NF . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
2. Otras formas normales
2 2 2 4 5 5 6 7 7 9 9
3. Proceso general del diseno ˜ de bases de datos 3.1. Desnormalizacion ´ para el rendimiento . . . . . . . . . . . . . 3.2. Otros problemas de diseno ˜ . . . . . . . . . . . . . . . . . . . .
1
9 10 10
1
´ DE DATOS NORMALIZACION
2
El objetivo del diseno ˜ de las bases de datos relacionales es la generacion ´ de un conjunto de esquemas relacionales que nos permita almacenar la informacion ´ sin redundancias innecesarias, pero que tambi´en nos permita recuperar f´acilmente esa informacion. ´ Un enfoque es el diseno ˜ de esquemas que se hallen en una forma normal adecuada. Para determinar si el esquema de una relacion ´ se halla en una de las formas normales deseables hace falta informacion ´ adicional sobre la empresa real que ese est´a modelando con la base de datos. En este cap´ıtulo se introduce el concepto de la dependencia funcional. Luego se definir´an las formas normales en t´erminos de las dependencias funcionales y otros tipos de dependencias de datos.
1.
Normalizacion ´ de datos
La normalizaci´on de datos consiste en una serie de pasos que conducen a un diseno ˜ de base de datos relacional que permite un almacenamiento de datos consistente, sin redundancias innecesarias. A veces, por cuestiones como capacidad del sistema, tamano ˜ de los datos, etc. es deseable desnormalizar, para obtener un mejor rendimiento, aun a costa de reducir la consistencia.
1.1.
Formas normales
Una tabla o relacion ´ se dice que est´a en una determinada forma normal si satisface ciertas condiciones. En sus primeros trabajos, Edgar F. Codd definio´ tres formas normales, aunque en la actualidad este modelo se ha ampliado. Normalmente, cuando se habla de una base de datos normalizada se refiere a que todas las tablas est´en en tercera forma normal. Cada forma normal incluye a las de nivel inferior, por ejemplo, si una tabla est´a en tercera forma normal, tambi´en lo est´a en segunda y en primera forma normal.
1.2.
primera forma normal (1NF)
Una tabla est´a en primera forma normal si todos los valores de todas las columnas son at´omicos. Esto es otra forma de decir que no se aceptar´an como atributos de la relacion ´ listas de valores, sino valores simples. Una tabla que no cumpliera esta condicion ´ se normalizar´ıa creando una segunda tabla, dependiente de la primera mediante una clave externa, y que contuviera los valores multiples. ´ Otra forma de describir que los valores de una columna sean atomicos ´ es que cada columna solo ´ contendr´a los valores del dominio que le corresponde, es decir, no se ”reciclar´a” una columna para almacenar otro tipo de dato. De la misma manera, no se utilizar´an varias columnas para almacenar el mismo valor (no se duplicar´an columnas).
1
´ DE DATOS NORMALIZACION
3
Como ejemplo de una tabla no normalizada, supongamos que tenemos que guardar informacion ´ de los ingresos y saldos que tenemos en nuestras cuentas bancarias. Supongamos que trabajamos con los bancos Alfabank, BBLAV y CityCrash. Un primer enfoque podr´ıa ser la relacion: ´ ´ = (Fecha, Ingreso, Al f abank, BBLAV, CityCrash) Operacion Suponemos que podemos usar el campo Fecha como clave primaria. Y un ejemplo de datos de la tabla podr´ıa ser: Fecha 1/ene/2005 3/ene/2005 7/ene/2005 14/mar/2005
Ingreso 1500 100 200 -50
Operacion ´ Alfabank NULL NULL 200 200
BBLAV 1500 1500 1500 1450
CityCrash NULL 100 100 100
Estamos repitiendo las columnas de los saldos de los bancos, luego la relacion ´ no est´a en primera forma normal. Para solucionarlo, primero eliminamos las columnas repetidas, con lo que nos quedar´ıa la relacion ´ as´ı: ´ = (Fecha, Ingreso) Operacion Operacion ´ Fecha Ingreso 1/ene/2005 1500 3/ene/2005 100 7/ene/2005 200 14/mar/2005 -50 y crear´ıamos una nueva relacion, ´ Saldos, relacionada con la primera mediante una clave externa, para poder almacenar la informacion ´ de las columnas duplicadas Saldos = (Fecha, Banco, Saldo) Que, en nuestro ejemplo, contendr´ıa los siguientes datos: Saldo Fecha Banco 1/ene/2005 BBLAV 3/ene/2005 CityCrash 7/ene/2005 Alfabank 14/mar/2005 BBLAV
Saldo 1500 100 200 1450
Obs´ervese que esta normalizacion ´ ya presenta varias ventajas: Se aprovecha mejor el espacio de almacenamiento, se elimina valores nulos de la base de datos y se simplifican tareas como crear un nuevo banco o anotar un ingreso.
1
´ DE DATOS NORMALIZACION
1.3.
4
dependencia funcional
Antes de pasar a la segunda forma normal tenemos que definir el concepto de dependencia funcional. Sean X e Y dos subconjuntos de atributos de la relacion ´ R. Se dice que existe una dependencia funcional, denotada por X → Y si se cumple que, para cualesquiera dos tuplas t1 y t2 de R tales que t1 [X] = t2 [X], entonces obligatoriamente t1 [Y] = t2 [Y]. Esta significa que los valores de los atributos Y de una tupla de R dependen de los valores de los atributos de X. Dicho de otra manera, si conozco los valores de X de una tupla, puedo obtener o calcular de forma inmediata los valores de Y. Notese que el concepto de dependencia funcional no depende de los ´ datos que en un momento determinado tenga la tabla, sino que es una nocion ´ sem´antica. Si existen o no dependencias funcionales entre atributos no lo determina una serie abstracta de reglas, sino, m´as bien, los modelos mentales del usuario y las reglas de negocio de la organizacion ´ o empresa para la que se desarrolla el sistema de informacion. ´ Un mismo atributo puede determinar funcionalmente a varios atributos lo cual se denota a → (b1 , b2 , . . . , bn ). Tambi´en puede darse una dependencia funcional mutua: a → b y b → a, lo cual se representa a ↔ b. Las dependencias funcionales verifican una serie de propiedades denominadas axiomas de Armstrong: Reflexividad o Dependencia trivial. A partir de cualquier atributo o conjunto de atributos siempre puede deducirse e´ l mismo: x → x. Aumentatividad. Si x → y entonces (x, z) → y. As´ı se puede aumentar trivialmente el antecedente de una dependencia. Ejemplo: si con el DNI se determina el nombre de una persona, entonces con el DNI m´as la direccion ´ tambi´en se determina el nombre. Proyectividad. Si x → (y, z) entonces x → y. Ejemplo: si a partir del DNI es posible deducir el nombre y la direccion ´ de una persona, entonces con el DNI es posible determinar el nombre. Aditividad. Si x → y y z → w entonces (x, z) → (y, w). Ejemplo: si con el DNI se determina el nombre y con la direccion ´ el tel´efono de una persona, entonces con el DNI y la direccion ´ podr´a determinarse el nombre y el tel´efono. Transitividad o enlace de dependencias funcionales . Si x → y e y → z entonces x → z. Ejemplo: si con el DNI se puede determinar el codigo ´ de la provincia de residencia de una persona y con e´ ste codigo puede ´ determinarse el nombre de la provincia, entonces con el DNI puede determinarse el nombre de la provincia.
1
´ DE DATOS NORMALIZACION
5
Tambi´en se usa la expresion ´ Y depende funcionalmente de X para senalar que hay una dependencia funcional entre X e Y. ˜
1.4.
Segunda forma normal (2FN)
Para que una tabla est´e en segunda forma normal es necesario: 1.
Que est´e en primera forma normal.
2.
Que no exista ninguna dependencia funcional entre una parte de la clave primaria y un atributo que no forme parte de la clave. Dicho de otra manera, que cada atributo de la tabla que no forma parte de la clave depende funcionalmente de toda la clave y no de algun ´ subconjunto de ella. Si la clave est´an formada por un unico atributo entonces ´ ese esquema ya estar´a, obviamente, en segunda forma normal.
Como ejemplo de una normalizacion ´ 2FN, consid´erese la relacion ´ Componentes: Componentes = (id componente, proveedor, precio, direccion proveedor) La clave primaria est´a compuesta por los atributos id componente y proveedor. Esto es correcto, porque el mismo componente puede ser suministrado por diferentes proveedores. El atributo precio tambi´en est´a correctamente ubicado en esta relacion, ´ porque es totalmente dependiente de la clave primaria -diferentes proveedores pueden tener distintos precios para la misma pieza-. Sin embargo, la direccion ´ del proveedor solo ´ depende del nombre del proveedor, por lo que esta relacion ´ no cumple la segunda forma normal. Este atributo deber´ıa ubicarse en una nueva relacion, ´ de la forma Proveedor = (proveedor, direccion proveedor)
1.5.
Tercera forma normal (3NF)
Para que una tabla est´e en tercera forma normal es necesario: 1.
Que est´e en segunda forma normal.
2.
Que todos los atributos que no formen parte de la clave primaria sean mutuamente independientes; es decir, que no haya dependencias transitivas. Otra forma de verlo es que para toda dependencia funcional a → b (siendo a , b) que se verifique en una relacion, ´ a siempre forma parte de la clave primaria
1
´ DE DATOS NORMALIZACION
6
Este es el esquema de normalizacion ´ m´as utilizado. Llegados a este punto, todos los atributos que no forman parte de la clave dependen de la clave primaria, de toda la clave primaria y de nada m´as que de la clave primaria (con la excepcion ´ de las dependencias triviales del tipo A → A). Como ejemplo, consid´erese de nuevo la relacion ´ componente, ahora descrita de la siguiente manera: Componente = (Id Componente, nombre proveedor, direccion proveedor) La direccion ´ del proveedor no deber´ıa formar parte de esta relacion, ´ porque rompe la tercera forma normal. Existe una dependencia funcional transitiva, porque nombre proveedor → direccion proveedor, e Id Componente → nombre proveedor, luego Id Componente → direccion proveedor. En otras palabras, ni nombre proveedor ni direccion proveedor forman parte de la clave, y existe una dependencia entre ellos. Para remediarlo, es necesario crear una nueva relacion ´ Proveedor, de la forma: Proveedor = (nombre proveedor, direccion proveedor) y dejar la relacion ´ Componente en la forma: Componente = (Id Componente, nombre proveedor)
1.6.
Forma normal de Boyce-Codd (BCNF)
La forma normal de Boyce-Codd es una version ´ m´as fuerte de la tercera forma normal. Aqu´ı todos los atributos (incluidos los que forman parte de la clave primaria) dependen de la clave primaria, de toda la clave primaria y de nada m´as que de la clave primaria (con la excepcion ´ de las dependencias triviales del tipo A → A). Se basa en el concepto de determinante funcional: uno o varios atributos de una tabla de los cuales dependen funcionalmente de forma completa algun ´ otro atributo de la misma tabla. Una relacion ´ est´a en FNBC si cada determinante funcional es una clave candidata de la tabla. As´ı se garantiza que se han elegido bien las claves, al no existir dependencias funcionales entre atributos que no son clave. Cada vez que se verifica una dependencia funcional α → β entonces α es clave primaria o candidata con seguridad. Otra forma de verlo es que se debe cumplir que todas las dependencias funcionales cumplen que en su parte izquierda solo aparecen atributos que son parte de una clave candidata. Esta forma normal es m´as restrictiva que la tercera y tiene la interesante propiedad de que su cumplimiento implica la satisfaccion ´ de FN3 o sea que una relacion ´ que est´e en FNBC est´a autom´aticamente en FN3.
1
´ DE DATOS NORMALIZACION
7
Las afinidades en BCNF no tienen anomal´ıas con respecto a las dependencias funcionales. Las siguientes formas normales eliminar las anomal´ıas que pueden surgir de situaciones distintas a las dependencias funcionales.
1.7.
Comparacion ´ entre FNBC y 3FN
De las dos formas normales para los esquemas de las bases de datos relacionales, 3FN y FNBC, hay ventajas en 3FN porque se sabe que siempre es posible obtener un diseno ˜ en 3FN sin sacrificar la reunion ´ sin p´erdida o la conservacion ´ de las dependencias. Sin embargo, hay inconvenientes en 3FN: si no se eliminan todas las dependencias transitivas de las relaciones de los esquemas, puede que se tengan que emplear valores nulos para representar algunas de las relaciones significativas posibles entre los datos, y est´a el problema de repeticion ´ de la informacion. ´
1.8.
Dependencias multivaloradas
Para poder explicar la cuarta forma normal, necesitamos definir el concepto de dependencia funcional multivalorada. Dada una relacion ´ R(A, B, C), hay una dependencia multivalorada entre A y B, denotada por A →→ B, si y solos si el conjunto de valores posibles ´ de B, dado unos valores concretos de A y C (a:A, c:C), solo ´ depende de a y es independiente de c. Es decir, que si tenemos un valor concreto a para el atributo A, existe un conjunto limitado de posibles valores de B, y ese conjunto de valores es independiente de cualquiera que fuera el valor c Toda dependencia funcional es tambi´en una dependencia multivalorada (pero no al rev´es). La definicion ´ formal de dependencia multivalorada, para aquellos esp´ıritus fuertes que ans´ıan un desaf´ıo, ser´ıa: Sea R un esquema de relacion ´ y sean α ⊆ R y β ⊆ R. La dependencia multivalorada α →→ β se cumple en r(R) si para todo par de tuplas t1 y t2 de r tales que t1 [α] = t2 [β], existen unas tuplas t3 y t4 de r tales que: t1 [α] = t2 [α] = t3 [α] = t4 [α] t3 [β] = t1 [β] t3 [R − β] = t2 [R − β] t4 [β] = t2[β] t4 [R − β] = t1[R − β] Las dependencias multivaloradas nos producen anomal´ıas cuando vienen en parejas; ve´amoslo con un ejemplo:
1
´ DE DATOS NORMALIZACION
8
Supongamos una relacion ´ de un fabricante de zapatos, en la cual que un determinado modelo de zapato se puede fabricar en distintas tallas, as´ı como en diferentes colores. Podemos representar esto con la siguiente relacion: ´ Catalogo = (Color, Modelo, Talla) La clave primara de la tabla es la composicion ´ de los tres atributos. No hay dependencias funcionales entre ellos, as´ı que la relacion ´ es BCNF. Sin embargo, se presentan ciertas ambiguedades, al ser independientes los ¨ colores de las tallas. Existe una dependencia multivalorada entre el modelo y los posibles colores, y existe otra dependencia multivalorada entre el modelo y las tallas, y no existe ninguna relacion ´ entre los posibles colores y tallas. As´ı las cosas, veremos a continuacion ´ que no est´a claro como debemos almacenar la informacion. ´ Supongamos, por ejemplo, un modelo de zapato M, que se produce en dos colores (azul y negro) y en dos tallas (40 y 42). Una forma de almacenar esta informacion ´ ser´ıa la siguiente: Catalogo Color Modelo azul M negro M
Talla 40 42
No tenemos problemas cuando intentamos acceder a la informacion ´ de forma separada, pro ejemplo, las consultas ¿En cuantos colores se comercializa el modelo M? y ¿En cuantas tallas se comercializa el modelo M? se pueden realizar f´acilmente. Sin embargo, este sistema es confuso y propenso a error: ¿No existen zapatos del modelo M en color azul y de la talla 42? Existe otras posibilidad 1 , que ser´ıa almacenar todas las combinaciones, as´ı:
Color azul azul negro negro
Catalogo Modelo M M M M
Talla 40 42 40 42
Sin embargo, esto nos produce m´as problemas de los que resuelve: En primer lugar, es redundante, y ocupa m´as espacio del necesario. 1 Que existan distintas formas de almacenar la misma informacion ´ en una base de datos ya es, en si, un problema de falta de normalizacion ´
2
OTRAS FORMAS NORMALES
9
Adem´as, nos produce anomal´ıas de insercion. ´ No es posible almacenar las posibles tallas si no conocemos los colores en que se va a fabricar, a no ser que permitamos valores nulos en el campo color. De igual forma, en caso de querer incorporar un nuevo color, no podemos limitarnos a realizar una unica insercion, ´ ´ habr´a que realizar n inserciones, siendo n el numero ´ de tallas distintas en que se fabrica el modelo. De igual forma, hay anomal´ıas de borrado. retirar una posible talla del cat´alogo implica borrar n tuplas, tantas como colores posibles hubiera. Para resolver estas ambiguedades, la solucion ¨ ´ pasa por dividir la relacion ´ en dos, de la forma: Colores = (Modelo, Color) y Tallas = (Modelo, Talla)
1.9.
Cuarta forma normal 4NF
Una relacion ´ est´a en cuarta forma normal si est´a en BCNF y no tiene dependencias multivaloradas.
2.
Otras formas normales
La cuarta forma normal no es, de ningun ´ modo, la forma normal ((definitiva)). Como ya se ha visto, las dependencias multivaloradas ayudan a comprender y a abordar algunas formas de repeticion ´ de la informacion ´ que no pueden comprenderse en t´erminos de las dependencias funcionales. Hay tipos de restricciones denominadas dependencias de reunion ´ que generalizan las dependencias multivaloradas y llevan a otra forma normal denominada forma normal de reunion ´ por proyeccion ´ (FNRP) o Quinta forma normal (5NF). Hay una clase de restricciones todav´ıa m´as generales, que lleva a una forma normal denominada forma normal de dominios y claves (FNDC).
3.
Proceso general del diseno ˜ de bases de datos
Cuando se parte de un diagrama E-R, identificando correctamente todas las entidades, las tablas generadas normalmente no necesitan m´as normalizacion. ´ No obstante, puede haber dependencias funcionales entre los atributos de una entidad. Sin embargo, la mayor parte de los problemas surgen de un mal diseno ˜ del diagrama E-R, por lo que las dependencias funcionales pueden ayudar a detectar el mal diseno ˜ E-R.
3
˜ DE BASES DE DATOS PROCESO GENERAL DEL DISENO
10
Un segundo enfoque es partir de un unico esquema de relacion ´ ´ que contenga todos los atributos de inter´es y descomponerlo. Uno de los objetivos al escoger una descomposicion ´ es que sea una descomposicion ´ de reunion ´ sin p´erdida, es decir, que a partir de las relaciones resultantes se pueda obtener la relacion ´ inicial mediante reuniones.
3.1.
Desnormalizacion ´ para el rendimiento
A veces los disenadores de bases de datos escogen un esquema que ˜ tiene informacion ´ redundante; es decir, que no est´a normalizada. Utilizan la redundancia para mejorar el rendimiento para aplicaciones concretas. La penalizacion ´ sufrida por no emplear un esquema normalizado es el trabajo extra (en t´erminos de tiempo de codificacion ´ y de tiempo de ejecucion) ´ de mantener consistentes los datos redundantes. El proceso de tomar un esquema normalizado y hacerlo no normalizado se denomina desnormalizacion, lo utilizan para ajustar el ´ y los disenadores ˜ rendimiento de los sistemas para dar soporte a las operaciones cr´ıticas en el tiempo. Una alternativa mejor, soportada hoy en d´ıa por muchos sistemas de bases de datos, es emplear el esquema normalizado y, de manera adicional, almacenar la reunion ´ o cuenta e impositor en forma de vista materializada. (Recu´erdese que una vista materializada es una vista cuyo resultado se almacena en la base de datos y se actualiza cuando se actualizan las relaciones utilizadas en la vista.) Al igual que la desnormalizacion, ´ el empleo de las vistas materializadas supone sobrecargas de espacio y de tiempo; sin embargo, presenta la ventaja de que conservar la vista actualizada es labor del sistema de bases de datos, no del programador de la aplicacion. ´
3.2.
Otros problemas de diseno ˜
Hay algunos aspectos del diseno ˜ de bases de datos que la normalizacion ´ no aborda y, por tanto, pueden llevar a un mal diseno ˜ de la base de datos. A continuacion ´ se ofrecer´an algunos ejemplos; evidentemente, conviene evitar esos disenos. ˜ Consid´erese la base de datos de una empresa, donde se desea almacenar los beneficios de las compan´ Se puede utilizar la relacion: ˜ ıas de varios anos. ˜ ´ bene f icios(id empresa, anio, importe) para almacenar la informacion dependencia ´ de los beneficios. La unica ´ funcional de esta relacion ´ es (id empresa, anio) → importe), y esta relacion ´ se halla en FNBC. Un diseno ˜ alternativo es el empleo de varias relaciones, cada una de las cuales almacena los beneficios de un ano que los ˜ diferente. Supongase ´
3
˜ DE BASES DE DATOS PROCESO GENERAL DEL DISENO
11
anos ˜ de inter´es son 2000, 2001 y 2002; se tendr´an, entonces, las relaciones de la forma bene f icios 2000, bene f icios 2001, bene f icios 2002, todos los cuales se hallan en el esquema (id empresa, bene f icios). Aqu´ı, la unica dependencia ´ funcional de cada relacion ´ ser´a id empresa → bene f icios, por lo que estas relaciones tambi´en se hallan en FNBC. No obstante, este diseno ˜ alternativo es, claramente, una mala idea: habr´ıa que crear una relacion ´ nueva cada ano, ˜ y tambi´en habr´ıa que escribir consultas nuevas cada ano, ˜ para tener en cuenta cada nueva relacion. ´ Las consultas tambi´en tendr´ıan que ser m´as complicadas, ya que puede que tengan que hacer referencia a muchas relaciones. Otra manera m´as de representar los mismos datos es tener una sola relacion: ´ empresa anio(id empresa, bene f icios 2000, bene f icios 2001, bene f icios 2002) En este caso, las unicas dependencias funcionales van de id empresa ´ hacia los dem´as atributos, y la relacion ´ vuelve a estar en FNBC. Este diseno ˜ tambi´en es una mala idea, ya que tiene problemas parecidos al diseno ˜ anterior, es decir, habr´ıa que modificar el esquema de la relacion ´ y escribir consultas nuevas cada ano. ˜ Las consultas tambi´en ser´ıan m´as complicadas, ya que puede que tengan que hacer referencia a muchos atributos. Las representaciones como las de la compan´ ˜ ıa empresa anio, con una columna para cada valor de un atributo, se denominan de tablas cruzadas; se emplean ampliamente en las hojas de c´alculo, en los informes y en las herramientas de an´alisis de datos. Aunque estas representaciones resultan utiles para mostr´arselas a los usuarios, por las razones que acaban de ´ darse, no resultan deseables en el diseno ˜ de bases de datos. Se han propuesto extensiones de SQL para convertir los datos desde una representacion ´ relacional normal en una tabla cruzada, para poder mostrarlos.
