OPTIMIZACIÓN DEL DISEÑO DE BASES DE DATOS RELACIONALES.
Hechos/conceptos
(contenidos soporte)
ü Problemas
que puede presentar el diseño de una base de datos relacional. Anomalías de
Codd (inserción, actualización y borrado).
ü Normalización.
Necesidad de su utilización. Formas normales de Codd: primera forma normal
(condiciones que debe cumplir la relación para estar en primera forma normal,
paso a primera forma normal), segunda forma normal (condiciones que debe
cumplir la relación para estar en segunda forma normal, paso a segunda forma
normal), tercera forma normal
(condiciones de transformación de las relaciones a tercera forma
normal), proceso de transformación de las relaciones a tercera forma normal.
Forma normal de Boyce-Codd (condiciones que debe cumplir la relación para estar
en la forma normal de Boyce-Codd, paso a
la forma normal de Boyce-Codd). Algoritmo de descomposición. Otras formas normales.
5.-TEORIA DE LA NORMALIZACION
"hechos distintos, deben almacenarse en objetos distintos"
(num_socio, cod_libro) y (nombre_socio, cod_libro)
U Ai = A, i=1, n.
Para toda extensión r de R, la combinación (join) de las relaciones resultantes ha de producir la relación origen, es decir,
* ri = r, i=1,n.
Anomalías de Codd
Cuando se diseña una base de datos mediante el modelo relacional, al igual que ocurre en otros modelos de datos, tenemos distintas alternativas, es decir, podemos obtener diferentes esquemas relacionales y no todos son equivalentes, ya que algunos van a representar la realidad mejor que otros.
Es necesario conocer qué propiedades debe tener un esquema relacional para representar adecuadamente una realidad y cuáles son los problemas que se pueden derivar de un diseño inadecuado.
La teoría de la Normalización es un método objetivo y riguroso que se aplica en el diseño de bases de datos relacionales.
Cuando estudiamos la estructura del modelo relacional, nos dimos cuenta que la base de datos puede representarse por medio de un conjunto de objetos (dominios y relaciones) y de un conjunto de reglas de integridad.
El esquema relacional puede obtenerse de dos formas distintas:
- Directamente a partir de la observación de nuestro universo del discurso, en donde especificamos conjuntos de atributos, relaciones y restricciones que corresponden a los observados en el mundo real.
- Realizando el proceso de diseño en dos fases, primero el diseño conceptual (E/R) obteniendo el esquema conceptual y posteriormente transformar éste a un esquema relacional, siguiendo algunas reglas generales, que fueron dadas anteriormente.
Algunos problemas que se pueden presentar son:
- Incapacidad para almacenar ciertos hechos
- Redundancias y por tanto, posibilidad de incoherencias
- Ambigüedades
- Pérdida de información (aparición de tuplas espúreas)
- Pérdida de dependencias funcionales, es decir, ciertas restricciones de integridad que dan lugar a interdependencias entre los datos.
- Aparición en la BD de estados no válidos, es decir, anomalías de inserción, borrado y modificación.
En conclusión el esquema relacional obtenido debe ser analizado para comprobar que no presenta los problemas anteriores.
Analicemos la siguiente relación: ESCRIBE
| AUTOR | NACIONALIDAD | COD_LIBRO | TITULO | EDITORIAL | AÑO |
| Date, C. | Norteamericana | 98987 | Database | Addison | 1990 |
| Date, C. | Norteamericana | 97777 | SQL Stan | Addison, W. | 1986 |
| Date, C. | Norteamericana | 98987 | Guide for | Addison, W. | 1988 |
| Codd,E. | Norteamericana | 7890 | Relational | Addison,W. | 1990 |
| Gardarin | Francesa | 12345 | Basi Dati | Paraninfo | 1986 |
| Gardarin | Francesa | 67890 | Comp BD | Eyrolles | 1984 |
| Valduriez | Francesa | 67890 | Comp BD | Eyrolles | 1984 |
| Kim,W. | Norteamericana | 11223 | BD OO | ACM | 1989 |
| Lochovsky | Canadiense | 11223 | BD OO | ACM | 1989 |
Esta relación almacena datos de autores y de libros.
Algunos problemas son:
- Redundancia, ya que la nacionalidad del autor se repite por cada ocurrencia del mismo. Lo mismo sucede cuando un libro tiene mas de un autor, se repite la editorial y el año de publicación.
- Anomalías de modificación, es fácil cambiar el nombre de una editorial en una tupla sin modificar el resto de las que corresponden al mismo libro, lo que da lugar a incoherencias.
- Anomalías de inserción, ya que si queremos ingresar información de algún autor, del que no hubiera ningún libro en la base datos, no sería posible, ya que cod_libro es parte de la clave primaria de la relación (regla de integridad de la entidad). La inserción de un libro, que tiene dos autores obliga a insertar dos tuplas en la relación.
- Anomalías de borrado, ya que si queremos eliminar un cierto libro, deberíamos perder los datos de su autor y viceversa.
En los casos anteriores, se deja en manos del usuario manejar la integridad de la base de datos.
Lo anterior sucede pues no se cumple un hecho básico de todo diseño:
Una forma de evitar este tipo de problemas consiste en seguir la metodología propuesta en el curso, es decir, un riguroso diseño conceptual y un traspaso de éste al modelo relacional.
Sin embargo, ante posibles dudas respecto a si un esquema relacional está correcto, aplicaremos a dicho esquema un método formal de análisis, que permita analizar errores y generar esquemas correctos. Esta es la teoría de la normalización.
En el ejemplo anterior, el conjunto de las siguientes relaciones no presenta estos problemas:
LIBRO( cod_libro, titulo, editorial, año )
AUTOR( nombre, nacionalidad )
ESCRIBE( cod_libro, nombre )
La normalización introduce una técnica formal para diseñar bases de datos relacionales, y permite mecanizar parte del proceso al disponer de algoritmos de normalización.
Una observación importante, es que las anomalías antes descritas se producen en procesos de actualización y no en procesos de consulta. La normalización penaliza las consultas, al disminuir la eficiencia, ya que la normalización aumenta el nro. de relaciones presentes en la base de datos, por lo que una determinada consulta puede llevar consigo el acceso a varias tablas, lo que aumenta el costo de ésta.
5.1.-Noción intuitiva de las formas normales
La normalización tiene como objetivo obtener esquemas relacionales que cumplan determinadas condiciones, a través de las formas normales.
Primera Forma Normal (1FN) fue introducida por Codd, en su primer trabajo. Es una restricción inherente al modelo relacional por lo que su cumplimiento es obligatorio. Consiste en la prohibición de que en una relación existan grupos repetitivos, es decir, un atributo no puede tomar más de un valor del dominio subyacente.
Segunda Forma Normal (2FN), fue introducida por Codd. Una relación está en 2FN, si además de estar en 1FN, todos los atributos que no forman parte de ninguna clave candidata suministran información acerca de la clave completa.
Para la relación PRESTAMO( num_socio, nombre_socio, cod_libro, fec_prest, editorial, país )
las claves candidatas son:
Se puede observar que ciertos atributos que no forman parte de las claves candidatas, tal como editorial, constituye información acerca del libro, pero no acerca de la clave completa. Luego, la relación préstamo no se encuentra en 2FN.
La solución es descomponer esta relación en las siguientes:
PRESTAMO1( num_socio, nombre_socio, cod_libro, fec_prest )
LIBRO( cod_libro, editorial, país )
En la relación PRESTAMO1, el único atributo que no forma parte de las claves candidatas es fec_prest, pero suministra información acerca de la clave completa. Por lo que está en 2FN.
La relación LIBRO, la clave es cod_libro, y los dos atributos: editorial y país suministran información de la clave completa. Por lo tanto, está en 2FN.
OBS: Una relación que está formada por un único atributo esta en 2 FN.
Tercera Forma Normal (3FN), propuesta por Codd. Una relación está en 3FN, si además de estar en 2FN, los atributos que no forman parte de ninguna clave candidata facilitan información sólo acerca de la(s) clave(s) y no acerca de otros atributos.
En la relación PRESTAMO1, el atributo fec_prest facilita información acerca de las claves, ya que no existen más atributos. Por lo que está en 3FN.
En la relación LIBRO, el atributo país entrega información acerca de la editorial que publica el libro, por lo que no está en 3FN.
La solución es descomponerla en:
LIBRO1( cod_libro, editorial )
EDITORIAL( editorial, país ),
que están en 3FN, ya que todo atributo no clave facilita información acerca de la clave.
Forma Normal de Boycce y Codd (FNBC). La relación PRESTAMO1, que está en 3FN, todavía presenta anomalías, ya que num_socio y nombre_socio, se repiten innecesariamente por cada cod_libro. Una relación está en FNBCsi y solo si, el conocimiento de las claves candidatas permite averiguar todas las interrelaciones existentes entre los datos de la relación, o lo que es igual, las claves candidatas son los únicos descriptores sobre los que se facilita información por cualquier otro atributo.
En la relación PRESTAMO1, num_socio es información acerca de nombre_socio y viceversa. Ninguno de estos atributos son clave (aunque formen parte de la clave). Para solucionarlo la descomponemos:
SOCIO( num_socio, nombre_socio )
PRESTAMO2( num_socio, cod_libro, fec_prest ), que están en FNBC.
Hasta ahora nuestro esquema relacional está compuesto por las siguientes relaciones en FNBC:
LIBRO1( cod_libro, editorial )
EDITORIAL( editorial, país )
SOCIO( num_socio, nombre_socio )
PRESTAMO2( num_socio, cod_libro, fec_prest )
La teoría de la normalización se basa en restricciones definidas sobre los atributos de una relación. que son conocidas como dependencias. Existen varios tipos de dependencias:
- Funcionales, relacionadas con la 2FN y 3FN y FNBC
- Multivaluadas, relacionadas con la 4FN
- De proyección o combinación, relacionadas con la 5FN.
5.2.-Dependencias funcionales
Sea el esquema de relación R definido sobre el conjunto de atributos A y sean X e Y subconjuntos de A llamados descriptores. Se dice que Y depende funcionalmente de X o que X determina o implica a Y, que se representa porX ® Y, si solo si, cada valor de X tiene asociado en todo momento un único valor de Y.
ej: cod_libro ® titulo, el código del libro determina el titulo. El cod_libro es el implicante y titulo es el implicado. Siempre el implicado es un hecho (una información) acerca del implicante.
OBS1: la afirmación cod_libro determina titulo NO significa que a partir de cod_libro podamos conocer el titulo. Es decir, para un esquema R, si tenemos la dependencia funcional X ® Y, dado un valor de X no podemos en general conocer el valor de Y. Solo nos limitaremos a firmar que para dos tuplas de cualquier extensión de R que tengan el mismo valor de X, el valor de Y también será igual en ambas.
OBS2: Las dependencias son predicados o restricciones sobre cualquier extensión válida del esquema de relación, por lo que observar una determinada extensión (datos) no puede llevarnos a afirmar la existencia de una dependencia funcional.
5.2.1.-Dependencia funcional completa
Si el descriptor X es compuesto, es decir, X(X1, X2), se dice que Y tiene dependencia funcional completa de X, si depende funcionalmente de X, pero no depende de ningún subconjunto del mismo, esto es:
X ® Y
X1 ® | Y
X2 ® | Y. Se representa X Þ Y.
X Þ Y si y solo si NO $ X’ Ì X / X’ ® Y.
Ejemplos:
La relación PUBLICA( articulo, revista, numero, pagina ), que representa la pagina inicial en la que comienza un articulo en una revista. Un mismo articulo puede aparecer publicado en distintas revistas y en cada una de ellas, en paginas distintas y una revista publica varios artículos, se tiene:
articulo, revista, numero ® pagina
articulo ® | pagina
revista ® | pagina
numero ® | pagina
5.2.2.-Dependencia funcional trivial
Una dependencia funcional X ® Y es trivial si Y es un subconjunto de X (Y Í X).
Ejemplos:
cod_libro ® cod_libro
articulo, revista ® revista.
5.2.3.-Dependencia funcional elemental
Solo las dependencias elementales son útiles en la normalización.
Una dependencia funcional X ® Y es elemental si Y es un atributo único, no incluido en X y no existe X’ incluido en X tal que X’ ® Y, es decir, la dependencia funcional elemental es un dependencia funcional completa no trivial, en la que el implicado es un atributo único.
5.2.4.- Dependencia funcional transitiva
Sea la relación R( X,Y,Z ), en la que existen las siguientes dependencias funcionales:
X ® Y, Y ® Z y Y ® | X, se dice que Z tiene dependencia transitiva respecto a X, a través de Y.
ej: LIBRO_ED( codlibro, editorial, país )
La dependencia entre codlibro y país es transitiva, a través de editorial. Intuitivamente se interpreta como que PAIS es una información del libro, pero indirectamente, ya que es una información de EDITORIAL y esta a su vez de LIBRO.
5.3.-Teoría formal de la Normalización
Dado un conjunto de atributos A y un conjunto de dependencias entre ellos, D, que constituyen un esquema de relación R(A,D) (esquema origen), se trata de transformar este esquema original en un conjunto de n esquemas de relación Ri(Ai,Di), i=1,n (esquemas resultantes), que cumplan determinadas características.
Estas son:
- Conservación de la información
- Conservación de las dependencias
- Normalización de las relaciones
5.3.1.-Conservación de la información
Se debe cumplir:
Conservación de los atributos
Conservación del contenido (las tuplas)
Si el proceso de normalización no se lleva a cabo correctamente , pueden aparecen nuevas tuplas que no estaban en la relación origen. Estas se llaman tuplas espúreas, que falsean el contenido de la base de datos.
Ejemplo: Dada la relación original
| LIBRO(COD_LIBRO, EDITORIAL, PAIS) | ||
| COD_LIBRO | EDITORIAL | PAIS |
| RAMA | ESPAÑA | |
| RAMA | ESPAÑA | |
| PARANINFO | ESPAÑA | |
| ANAYA | ESPAÑA | |
| ADD.WES | USA | |
y las relaciones resultantes:
| LIBRO1(COD_LIBRO, PAIS) | |
| COD_LIBRO | PAIS |
| 9030 | ESPAÑA |
| 9040 | ESPAÑA |
| 9110 | ESPAÑA |
| 9234 | ESPAÑA |
| 9567 | USA |
| EDITORIAL(EDITORIAL, PAIS) | |
| EDITORIAL | PAIS |
| RAMA | ESPAÑA |
| RAMA | ESPAÑA |
| PARANINFO | ESPAÑA |
| ANAYA | ESPAÑA |
| ADD.WES | USA |
| LIBRO1 * EDITORIAL | ||
| COD_LIBRO | EDITORIAL | PAIS |
| 9030 | RAMA | ESPAÑA |
| 9030 | PARANINFO | ESPAÑA |
| 9030 | ANAYA | ESPAÑA |
| 9040 | RAMA | ESPAÑA |
| 9040 | PARANINFO | ESPAÑA |
| 9040 | ANAYA | ESPAÑA |
| 9010 | RAMA | ESPAÑA |
| 9110 | PARANINFO | ESPAÑA |
| 9010 | ANAYA | ESPAÑA |
| 9234 | RAMA | ESPAÑA |
| 9234 | PARANINFO | ESPAÑA |
| 9234 | ANAYA | ESPAÑA |
| 9567 | ADD.WES | USA |
En negrita, tuplas espúreas.
5.3.3.-Definición formal de la tres primeras formas normales
Primera Forma Normal: equivalente a la definición dada antes
Segunda Forma Normal:
- Está en 1FN
- Cada atributo no principal tiene dependencia funcional completa respecto de cada una de las claves.
ejemplo: La relación
PUBLICA2( articulo, revista, numero, pagina, editorial )
que refleja en qué numero de qué revista se publica un artículo, en qué pagina comienza y cuál es la editorial.
Tenemos las siguientes dependencias:
articulo, revista, numero ® pagina
revista ® editorial
clave:(articulo, revista, numero)
Esta relación no esta en 2FN, ya que editorial depende de la revista y tiene redundancia, pues se repite la editorial para cada articulo que se publica en una revista.
Tercera Forma Normal:
- Está en 2FN
- Ningún atributo no principal depende transitivamente de ninguna clave de la relación
Ejercicio:
R( estudiante, nro_matricula,curso,centro, profesor, texto ), con las restricciones:
- Un estudiante puede estar matriculado en varios cursos
- Un estudiante tiene un numero de matrícula distinto para cada curso en el que está matriculado
- Un curso se imparte en un solo centro
- El número de matrícula identifica al centro en el que se imparte el curso y al curso mismo
- Un curso es impartido por un solo profesor, pero un profesor puede impartir varios cursos
- Un curso se apoya en distintos textos y un mismo texto puede servir de soporte a varios cursos.
Reducir el esquema anterior a un conjunto equivalente de relaciones en FNBC
Las dependencias funcionales se relacionan con el modelado relacional de interrelaciones 1:N y 1:1.
5.4.- Dependencias Multivaluadas y 4FN
Las dependencias multivaluadas son una generalización de las dependencias funcionales. En éstas un conjunto de valores del implicado, son determinados por un implicante. Esta situación aparece cuando existen grupos repetitivos.
Ej: la siguiente tabla
| AUTORES | ||
| AUTOR | MATERIA | INSTITUCION |
| Date | Lenguaje SQL; Diseño BD | Relational Inst.; Codd& Date Cons. |
| Ullman | Diseño BD; Bases Conc. | Stanford Univ. |
La tabla no cumple la 1FN.
La normalización de esta tabla produce la siguiente:
| AUTORES | ||
| AUTOR | MATERIA | INSTITUCION |
| Date | Lenguaje SQL | Relational Inst |
| Date | Lenguaje SQL | Codd& Date Cons |
| Date | Diseño BD | Codd& Date Cons |
| Date | Diseño BD | Relatinal Inst. |
| Ullman | Diseño BD | Stanford Univ. |
| Ullman | Bases Conc. | Stanford Univ |
Esta tabla normalizada presenta gran cantidad de redundancia. La clave es el conjunto de los 2 atributos. Por lo que está en FNBC.
En ella tenemos que un autor multidetermina a materia y un autor multidetermina a institución.
Las dependencias multivaluadas se producen cuando existen interrelaciones N:M independientes entre si. Entre autor y materia hay una interrelación N:M y también entre autor e institución y materia e institución son independientes.
Definición Dependencia Multivaluada.
Fagin (1977). La dependencia multivaluada se denota X ®® Y, y se lee X multidetermina a Y, y significa que X implica un conjunto de valores de Y con independencia de los demás atributos de la relación.
Las dependencias multivaluadas dependen del contexto, es decir influye el resto de los atributos de la relación.
Si agregamos un atributo a AUTORES, departamento, que nos indica el departamento de una institución en el que se trabaja en una cierta materia, obteniendo:
| AUTOR | MATERIA | INSTITUCION | DEPTO |
| Date | Lenguaje SQL | Relational Inst. | Lenguajes |
| Date | Lenguaje SQL | Codd& Date Cons. | Bases de Datos |
| Date | Diseño BD | Codd& Date Cons. | Analisis |
| Date | Diseño BD | Relatinal Inst. | Bases de Datos |
| Ullman | Diseño BD | Stanford Univ. | Lenguajes |
| Ullman | Bases Conc | Stanford Univ. | Inteligencia Artificial |
Aquí, la dependencia autor®® materia no se cumple, porque depende del contexto ( de depto).
Cuarta Forma Normal (4 FN)
Una relación se encuentra en 4FN, si y solo si, las únicas dependencias multivaluadas no triviales son aquellas en las cuales una clave multidetermina un atributo, es decir, toda dependencia multivaluada viene determinada por una clave candidata.
En la tabla AUTORES(autor, materia, institución), existen las dependencias multivaluadas:
autor ®® materia y autor ®® institución. La relación no se encuentra en 4FN, ya que estas dependencias están implicadas por autor, que no es clave candidata. La clave candidata es el conjunto de los tres atributos.
Para normalizarla se descompone en 2 proyecciones:
AUTORES1(autor, materia)
AUTORES2(autor,institucion), que si están en 4FN.
Revisar la 5FN en libros.
5.6.-Organización de Relaciones
- estructuración (consideraciones lógicas)
- Normalización
- Particionamiento horizontal
- reestructuración (consideraciones físicas)
- Desnormalización
- Particionamiento (horizontal, vertical)
Particionamiento Horizontal de relaciones
Esta estructuración permite eliminar valores nulos, debido en general a no haberse detectado los subtipos de una entidad o haberlas reunido en una sola entidad.
DOCUMENTO(cod-doc, titulo, idioma, editorial)
Que almacena datos de libros y artículos. El atributo editorial es inaplicable a articulo, podríamos descomponer la relación en:
LIBRO(cod-doc, titulo, idioma, editorial)
ARTICULO(cod-doc, titulo, idioma)
Relación origen pasa por selección a una que tiene todos los atributos que la original, pero contiene valores conocidos junto con otra a través de selección que contiene solo los atributos no nulos, eliminando el atributo de la relación origen que tenia nulos (proyección).
La construcción de la relación original se realiza por medio de la unión relacional, después de añadir los atributos para que sean compatibles en la unión.
Desnormalizacion y Particionamiento
Son métodos o formas de organizar las relaciones, teniendo en cuenta razones de tipo físico:
- Tasa de actualizaciones versus consultas
- Las veces que se accede conjuntamente a los atributos
- El tamaño en bytes de los atributos
- Tipos de proceso (en linea-batch)
- Prioridad de los procesos
- Tamaño de las tablas.
