TAREA 4
4.7 Algoritmos de descomposición.
Debido a esta pérdida de información se dice que la descomposición de Esquema empréstito en Esquema- sucursal-cliente y Esquema-cliente-préstamo es una descomposición con pérdida, o una descomposición de reunión con pérdida. Una descomposición que no es una descomposición con pérdida es una descomposición de reunión sin pérdida. Queda claro con este ejemplo que una descomposición de reunión con pérdida supone, en general, un mal diseño de base de datos.
El concepto de reunión sin pérdida resulta fundamental para gran parte del diseño de bases de datos relacionales. Por lo tanto, se volverán a formular los ejemplos anteriores de manera más concisa y formal. Sea R un esquema de relación. Un conjunto de esquemas de relación {R1, R2, ..., Rn} es una descomposición de R si
R = R1 ∪ R2 ∪ … ∪ Rn
Es decir, {R1, R2, ..., Rn} es una descomposición de R si, para i = 1, 2,..., n, cada Ri es un subconjunto de R y cada atributo de R aparece en al menos un Ri. Sea r una relación del esquema R y ri = ΠRi (r) para i = 1, 2,..., n. Es decir, {r1, r2,..., rn} es la base de datos que resulta de descomponer R en {R1, R2, ..., Rn}. Siempre se cumple que
r ⊆ r1 r2 ... rn
Para comprobar que esta afirmación es cierta considérese una tupla t de la relación r. Cuando se calculan las relaciones r1, r2, … , rn, la tupla t da lugar a una tupla ti en cada ri, i = 1, 2, … , n. Estas n tuplas se combinan para regenerar t cuando se calcula r1 r2 · · · rn. Los detalles se dejan para completarlos como ejercicio. Por tanto, cada tupla de r aparece en r1 r2 … rn.
En general, r ≠ r1 r2 · · · rn. Para mostrarlo consideremos el ejemplo anterior, en el que
• n = 2.
• R = Esquema-empréstito.
• R1 = Esquema-sucursal-cliente.
• R2 = Esquema-cliente-préstamo
• r = la relación mostrada en la Figura 7.1.
• r1 = la relación mostrada en la Figura 7.9.
• r2 = la relación mostrada en la Figura 7.10.
• r1 r2 = la relación mostrada en la Figura 7.11.
Obsérvese que las relaciones de las Figuras 7.1 y 7.11 no son iguales.
Para tener una descomposición de reunión sin pérdida hay que imponer restricciones en el conjunto de las relaciones posibles. Se descubrió que la descomposición de Esquema-empréstito en Esquema-sucursal y Esquema-info-préstamo era sin pérdida porque se cumple la dependencia funcional
nombre-sucursal → ciudad-sucursal activo en Esquema-sucursal.
Sea C un conjunto de restricciones de la base de datos y R un esquema de relación. Una descomposición {R1,R2, …, Rn} de R es una descomposición de reunión sin pérdida si, para todas las relaciones r del esquema R que son legales bajo
C r = ΠR1 (r) ΠR2 (r) ... ΠRn (r).
Descomposición de reunión sin pérdida
En el Apartado 7.4 se arguyó que, al descomponer una relación en varias relaciones de menor tamaño, resulta fundamental que la descomposición sea una descomposición sin pérdida. Se puede afirmar que la descomposición del Apartado 7.5 es realmente una descomposición sin pérdida. Para demostrar esta afirmación antes hay que presentar un criterio para determinar si una descomposición es una descomposición con pérdida.
Sea R un esquema de relación, y sea F un conjunto de dependencias funcionales de R. R1 y R2 forman una descomposición de R. Esta descomposición es una descomposición de reunión sin pérdida de R si al menos una de las siguientes dependencias se halla en F+:
• R1 ∩ R2 → R1
• R1 ∩ R2 → R2
En otras palabras, si R1 ∩ R2 forma una superclave de R1 o de R2, la descomposición de R es una descomposición de reunión sin pérdida.
Ahora se demostrará que la descomposición de Esquema-empréstito es una descomposición de reunión sin pérdida mostrando una secuencia de pasos que generan la descomposición. Para empezar se descompone Esquema-empréstito en dos esquemas:
Esquema-sucursal = (nombre-sucursal, ciudad-sucursal, activo)
Esquema-info-préstamo = (nombre-sucursal, nombre-cliente, número-préstamo, importe)
Dado que nombre-sucursal → ciudad-sucursal activo, la regla de la aumentatividad para las dependencias funcionales (Apartado 7.3.2) implica que
nombre-sucursal → nombre-sucursal ciudad-sucursal activo
Como Esquema-sucursal ∩ Esquema-info-préstamo = {nombre-sucursal}, se concluye que la descomposición inicial es una descomposición de reunión sin pérdida. A continuación se descompone Esquema-info-préstamo en
Esquema-préstamo = (número-préstamo, nombre-sucursal, importe)
Esquema-prestatario = (nombre-cliente, número-préstamo)
En el caso general de la descomposición simultánea de una relación en varias partes, la búsqueda de la descomposición de reunión sin pérdida resulta más complicada.
Conservación de las dependencias
Hay otro objetivo en el diseño de las bases de datos relacionales: la conservación de las dependencias. Cuando se lleva a cabo una actualización de la base de datos el sistema debe poder comprobar que la actualización no crea ninguna relación ilegal, es decir, una relación que no satisface todas las dependencias funcionales dadas. Si hay que comprobar de manera eficiente las actualizaciones,
se deben diseñar unos esquemas de bases de datos relacionales que permitan la validación de las actualizaciones sin que haga falta calcular las reuniones. Para decidir si hay que calcular las reuniones para comprobar una actualización hace falta determinar las dependencias funcionales que hay que comprobar verificando cada relación una a una.
Repetición de la información
La descomposición de Esquema-empréstito no sufre el problema de repetición de la información que se estudió en el Apartado 7.2. En Esquema-empréstito era necesario repetir la ciudad y el activo de la sucursal para cada préstamo. La descomposición separa los datos de la sucursal y los del préstamo en relaciones diferentes, con lo que elimina esta redundancia. De manera parecida, se observa que, en Esquema-empréstito, si se concede un solo préstamo a varios clientes, hay que repetir
el importe del préstamo una vez por cada cliente (así como la ciudad y activo de la sucursal). En la descomposición, la relación del esquema Esquema-prestatario contiene la relación número-préstamo, nombre-cliente, y no la contiene ningún otro esquema.
4.8 Formas normales superiores
7.8 CUARTA FORMA NORMAL
Hay que definir una nueva forma de restricción, denominada dependencia multivalorada. Como se hizo para las dependencias funcionales, se utilizarán las dependencias multivaloradas para definir una forma normal para los esquemas de relación. Esta forma normal, denominada cuarta forma normal (4FN), es más restrictiva que FNBC.
7.8.1. Dependencias multivaloradas
Las dependencias funcionales impiden que ciertas tuplas estén en una relación. Si A→B, entonces no puede haber dos tuplas con el mismo valor de A y diferentes valores de B. Las dependencias multivaloradas, no impiden la existencia de esas tuplas.
Las dependencias funcionales se denominan a veces dependencias de generación de igualdad y las dependencias multivaloradas se conocen como dependencias de generación de tuplas. Sea R un esquema de relación y sean α ⊆ R y β ⊆ R.
La dependencia multivalorada.
α →→β
Se cumple en R si, en toda relación legal r(R), 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 – β]
Ejemplo:
Para ilustrar la diferencia entre las dependencias funcionales y las multivaloradas, considérense de nuevo Esquema-BC y la relación bc (Esquema-BC) de la Figura 7.17. Hay que repetir el número de préstamo una vez por cada dirección que tenga un cliente, y la dirección en cada préstamo que tenga el cliente. Esta repetición es innecesaria, ya que la relación entre el cliente y su dirección es independiente de la relación entre ese cliente y el préstamo. Si un cliente (por ejemplo, Gómez) tiene un préstamo (por ejemplo, el préstamo número P-23), se desea que ese préstamo esté asociado con todas las direcciones que tenga Gómez. Por tanto, la relación
Si se compara el ejemplo anterior con la definición de dependencia multivalorada, se ve que se desea que se cumpla la dependencia multivalorada
nombre-cliente →→ calle-cliente ciudad-cliente
(La dependencia multivalorada nombre-cliente →→número-préstamo también se cumplirá. Pronto se verá que son equivalentes.) Al igual que con las dependencias funcionales, las dependencias multivaloradas se utilizan de dos maneras:
1. Para verificar las relaciones y determinar si son legales bajo un conjunto dado de dependencias funcionales y multivaloradas.
2. Para especificar restricciones del conjunto de relaciones legales; de este modo, sólo habrá que preocuparse de las relaciones que satisfagan un conjunto dado de dependencias funcionales y multivaloradas.
A partir de la definición de dependencia multivalorada se puede obtener la regla siguiente:
• Si α →β, entonces α →→β.
En otras palabras, cada dependencia funcional es también una dependencia multivalorada.
7.8.2. Definición de la cuarta forma normal
Un esquema de relación R está en la cuarta forma normal (4FN) con respecto a un conjunto F de dependencias funcionales y multivaloradas si, para todas las dependencias multivaloradas de F+ de la forma α →→β, donde α ⊆ R y β ⊆ R, se cumple, como mínimo, una de las condiciones siguientes.
• α →→β es una dependencia multivalorada trivial.
• α es una superclave del esquema R.
Un diseño de base de datos está en 4FN si cada componente del conjunto de esquemas de relación que constituye el diseño se halla en 4FN.
7.8.3. Algoritmo de descomposición
resultado := {R};
hecho := falso;
calcular F+; Dado el esquema Ri, supongamos que Fi denota la
restricción de F+ a Ri
while (not hecho) do
if (hay un esquema Ri en resultado que no se halla en 4FN
con respecto a Fi)
then begin
supongamos que α →→ β es una dependencia
multivalorada no trivial que se cumple en Ri tal
que α → Ri no se halla en Fi, y α ∩ β = ∅;
resultado := (resultado – Ri) ∪ (Ri – β) ∪ (α, β);
end
else hecho := verdadero;
FIGURA 7.19. Alogaritmo de descomposición en 4FN.
Si se aplica el algoritmo de la Figura 7.19 a Esquema-BC se halla que nombre-cliente →→ número-préstamo es una dependencia multivalorada no trivial, y que nombre-cliente no es una superclave de Esquema-BC.
Siguiendo el algoritmo, se sustituye Esquema-BC por dos esquemas:
Esquema-prestatario = (nombre-cliente,
número-préstamo)
Esquema-cliente = (nombre-cliente, calle-cliente,
ciudad-cliente).
Este par de esquemas, que se halla en 4FN, elimina el problema que se encontró anteriormente con la redundancia de Esquema-BC.
7.9. OTRAS FORMAS NORMALES
Hay tipos de restricciones denominadas dependencias de reunión que generalizan las dependencias
multivaloradas y llevan a otra forma normal denominada forma normal de reunión por proyección (FNRP) (la FNRP se denomina en algunos libros quinta forma normal). Hay una clase de restricciones todavía más generales, que lleva a una forma normal denominada forma normal de dominios y claves (FNDC).
TAREA 5
Integridad de entidad: establece que la clave primaria de una tabla debe tener un valor único para cada fila de la tabla; si no, la base de datos perderá su integridad.
La restricción de integridad de entidades establece que ningún valor de clave primaria puede ser nulo. Esto porque el valor de la clave primaria sirve para identificar las tuplas individuales en una relación; el que la clave primaria tenga valores nulos implica que no podemos identificar algunas tuplas.
Ejemplo 1
Tenemos la siguiente relación:
En esta relación, puesto que la clave primaria está formada por edificio y número, no hay ningún despacho que tenga un valor nulo para edificio, ni tampoco para número.
Esta regla es necesaria para que los valores de las claves primarias puedan identificar las tuplas individuales de las relaciones. Si las claves primarias tuviesen valores nulos, es posible que algunas tuplas no se pudieran distinguir.
Ejemplo de clave primaria incorrecta con valores nulos
En el ejemplo anterior, si un despacho tuviese un valor nulo para edificio porque en un momento dado el nombre de este edificio no se conoce, por ejemplo <NULO, 120, 30>, la clave primaria no nos permitiría distinguirlo del despacho <Marina, 120, 10> ni del despacho <Diagonal, 120,10>. No podríamos estar seguros de que el valor desconocido de edificio no es ni Marina ni Diagonal.
EJEMPLO 2
Si dos o más tuplas tuvieran nulo en su clave primaria, tal vez no podríamos distinguirlas.
La integridad de dominio viene dada por la validez de las entradas para una columna determinada. Puede exigir la integridad de dominio para restringir el tipo mediante tipos de datos.
EJEMPLO 1
“El tipo de publicación únicamente puede ser Novela, Cuento, Teatro o Poesía”.
• Dominios:
Dom_tipo : {Novela, Cuento, Teatro, Poesía, ...}
• Publicaciones:
Publicación(id_lib:dom_id_lib, título:dom_título, tipo:dom_tipo,
autor_id:dom_autor_id);
EJEMPLO 2
Para el hipotético Registro Estatal de Automóviles, el número de serie del vehículo en combinación con la marca y el modelo; la marca, el color y nombre del dueño; y la matrícula, son llaves candidatas. Pero de entre estas tres llaves candidatas, nos basta con la matrícula porque cumple perfectamente con las dos condiciones y además no es compuesta, con el consecuente ahorro de espacio y tiempo de cómputo. Las otras dos pasan a ser llaves alternas.
La integridad referencial protege las relaciones definidas entre las tablas cuando se crean o se eliminan filas.
EJEMPLO 1
En las tablas Sales.SalesOrderDetail y Production.Product de la base de datos AdventureWorks2008R2, la integridad referencial se basa en la relación entre la clave externa (ProductID) de la tabla Sales.SalesOrderDetail y la clave principal (ProductID) de la tabla Production.Product. Esta relación garantiza que un pedido de ventas no pueda nunca hacer referencia a un producto que no existe en la tabla Production.Product.
EJEMPLO 2
En la fig. 3.17 el atributo ND de EMPLEADO da el número del departamento para el cual trabaja cada empleado; por tanto, su valor en cada tupla de EMPLEADO deberá coincidir con el valor de NÚMEROD en alguna tupla de la relación DEPARTAMENTO.
La integridad definida por el usuario permite definir reglas de empresa específicas que no pertenecen a ninguna otra categoría de integridad. Todas las categorías de integridad admiten la integridad definida por el usuario. Esto incluye todas las restricciones de nivel de columna y nivel de tabla en CREATE TABLE, procedimientos almacenados y desencadenadores.
Ejemplos:
- Los dueños de cuentas de ahorro no pueden solicitar un monto mayor de dinero del que hayan juntado hasta la fecha.
- Para que un cliente sea considerado especial, deberá tener un mínimo de USD 1.000 en compras promedio al año.
Integrantes:
Omar Pastor Goinez
Héctor Juárez Santiago
No hay comentarios:
Publicar un comentario