Capítulo 4
Dependencias Funcionales – Parte 2
Encontrando las DF del Problema Actual
• Meta: responder a las siguientes preguntas:
• Problema 1: ¿Qué significa tener un conjunto
adecuado de DFs para el problema actual?
• Problema 2: ¿Cómo encontrar un conjunto adecuado
de DF para el problema actual?
• ¿Por qué debo preocuparme por esto?
Encontrando las DF del Problema Actual
• Problema 1: ¿Qué significa tener un conjunto
adecuado de DFs para el problema actual? (repaso)
Encontrando las DF del Problema Actual
• Problema 1: ¿Qué significa tener un conjunto
adecuado de DFs para el problema actual?
• Solución 1: Un conjunto adecuado F de DF deberá
cumplir:
1. Que no haya DF demás en F.
o Estas pueden ser inferidas a partir de otras DF del
conjunto.
2. Que no falten DF en F.
Encontrando las DF del Problema Actual
• Pero se puede hacer algo mejor que la solución
anterior.
• Atributos de DF pueden ser redundantes:
Ejemplo: {A B, B C, A CD}
o puede simplificarse a:
Encontrando las DF del Problema Actual
• Pero se puede hacer algo mejor que la solución
anterior.
• Atributos de DF pueden ser redundantes:
Ejemplo: {A B, B C, A CD}
o puede simplificarse a: {A B, B C, A D} .
Ejemplo: {A B, B C, AC D}
o puede simplificarse a:
Encontrando las DF del Problema Actual
• Pero se puede hacer algo mejor que la solución
anterior.
• Atributos de DF pueden ser redundantes:
Ejemplo: {A B, B C, A CD}
o puede simplificarse a: {A B, B C, A D} .
Ejemplo: {A B, B C, AC D}
o puede simplificarse a: {A B, B C, A D} .
Encontrando las DF del Problema Actual
• Problema 1: ¿Qué significa tener un conjunto
adecuado de DFs para el problema actual?
• ¿Qué sugiere el ejemplo anterior?
Encontrando las DF del Problema Actual
• Problema 1: ¿Qué significa tener un conjunto
adecuado de DFs para el problema actual?
• Solución 2:
– Una DF puede tener atributos redundantes
(llamados atributos raros);
– No debería haber atributos raros en un conjunto
adecuado de DFs.
Cubrimiento Canónico
• Problema 2: ¿Cómo encontrar un conjunto adecuado
de DF para el problema actual?
Cubrimiento Canónico
• Problema 2: ¿Cómo encontrar un conjunto adecuado
de DF para el problema actual?
• Solución: Si tenemos un conjunto de DF G para el
problema actual, tendremos que sacarle todas las DF
que están demás y también tendremos que sacar en
las DF todos los atributos raros.
– ¿Por qué debería preocuparme por hacer esto?
Cubrimiento Canónico
• Problema 2: ¿Cómo encontrar un conjunto adecuado
de DF para el problema actual?
• Solución: Si tenemos un conjunto de DF G para el
problema actual, tendremos que sacarle todas las DF
que están demás y también tendremos que sacar en
las DF todos los atributos raros.
– ¿Por qué debería preocuparme por hacer esto?
– Porque tener atributos de más en una DF implica
costo adicional e innecesario en su chequeo (i.e.
luego que se alteró la BD).
Cubrimiento Canónico
• ¿Entonces cuál es la meta?
• Encontrar un conjunto “minimal” de DF equivalente
a F, que no tiene DF demás o atributos raros en DFs.
• Conjuntos de DF que cumplen esto se llaman
cubrimientos canónicos de F.
Cubrimiento Canónico
Un cubrimiento canónico para F es un conjunto de
DF Fc tal que:
1. F ⊨ Fc ,
2. Fc ⊨ F,
3. ninguna DF en Fc contiene un atributo raro, y
4. cada lado izquierdo de una DF en Fc es único.
Cubrimiento Canónico
¿Por qué tenemos que preocuparnos con que
los lados izquierdos de las DF sean únicos?
Cubrimiento Canónico
¿Por qué tenemos que preocuparnos con que
los lados izquierdos de las DF sean únicos?
Tener más de una DF con el mismo lado
izquierdo implica mayores costos de chequeo de
DFs, los cuales se pueden evitar.
Atributos Raros
• Para poder formalizar si un atributo es redundante
en una DF necesitamos la noción de equivalencia
entre conjuntos de DF.
• ¿Qué significa que dos conjuntos de DF son
equivalentes?
Atributos Raros
• Para poder formalizar si un atributo es redundante
en una DF necesitamos la noción de equivalencia
entre conjuntos de DF.
• Sean F y G dos conjuntos de DF. Decimos que F y G
son equivalentes (F ≡ G) si y solo si F ⊨ G y G ⊨ F .
Atributos Raros
• A los atributos redundantes en una DF les llamamos
atributos raros.
• ¿Cómo definir el concepto de atributo raro usando el
concepto de equivalencia anterior?
Atributos Raros
• A los atributos redundantes en una DF les llamamos
atributos raros.
• Sea F un conjunto de DF y la DF en F.
– El atributo A es raro in si A
y F ≡ (F – { }) {( – A) }.
– El Atributo A is raro in if A
y (F – { }) { ( – A)} ≡ F.
Atributos Raros
• Las dos definiciones anteriores de atributo raro pueden ser
simplificadas.
• Uno de los lados de la equivalencia siempre es válido.
¿Cómo queda entonces lo que hay que probar?
Atributos Raros
• Las dos definiciones anteriores de atributo raro pueden ser
simplificadas.
• Sea F conjunto de DF y la DF en F.
– El atributo A is raro en si A
y F ⊨ (F – { }) {( – A) }.
– El atributo A es raro en si A
y (F – { }) { ( – A)} ⊨ F.
– La implicación lógica en la dirección opuesta es trivial en cada
uno de los casos de arriba.
Atributos Raros
Ejemplo: Dado F = {A C, AB C }
o ¿Hay algún atributo raro en F?
Atributos Raros
Ejemplo: Dado F = {A C, AB C }
o ¿Hay algún atributo raro en F?
o B es raro en AB C porque {A C,AB C} ⊨ A C (I.e.
el resultado de tirar B de AB C).
Ejemplo: Dado F = {A C, AB CD}
o ¿Hay algún atributo raro en F?
Atributos Raros
Ejemplo: Dado F = {A C, AB C }
o ¿Hay algún atributo raro en F?
o B es raro en AB C porque {A C,AB C} ⊨ A C (I.e.
el resultado de tirar B de AB C).
Ejemplo: Dado F = {A C, AB CD}
o ¿Hay algún atributo raro en F?
o C es raro en AB CD debido a que AB C puede ser
inferida incluso después de borrar C.
Atributos Raros
¿Cómo probar que un atributo es raro sin tener que
usar consecuencia lógica o deducción?
Atributos Raros
¿Cómo probar que un atributo es raro sin tener que
usar consecuencia lógica o deducción?
Hay que usar la noción de cierre de conjunto de
atributos.
Atributos Raros
Considere F conjunto de DFs y la DF in F.
Para probar si un atributo A es raro en
1. Computar ( – {A})+ usando las DF de F
2. Chequear que ⊆ ( – {A})+; si es cierto entonces A es raro
Veamos que esta receta funciona:
Encontrando las DF del Problema Actual
Para probar si un atrtibuto A es raro en
1. Computar + usando solo las DF en
G = (F – { }) { ( – A)},
2. Chequear que A ∈ +; si es cierto, entonces A es raro.
Veamos que esta receta funciona:
Atributos Raros
• Ejercicio: Probar las siguientes afirmaciones
usando los métodos de las 2 filminas anteriores.
o {AC, A B C} B raro
o {AC, A B C D} C raro
Cubrimiento Canónico
Algoritmo para computar el cubrimiento canónico de F:
Res := F
repeat
Use the union rule to replace any dependencies in Res
1 1 and 1 2 with 1 1 2
Find a DF in Res with an
extraneous attribute either in or in
If an extraneous attribute is found, delete it from
until Res does not change
La regla de unión puede ser aplicable luego de que algunos
atributos raros hayan sido borrados,
así que tiene que ser reaplicada.
Este algoritmo tiene el invariante: Res ⊨ F ∧ F ⊨ Res.
Cubrimiento Canónico
• Ejercicio: Sea el esquema R = (A, B, C) con DFs:
{A BC, B C, AB, AB C}
– Encontrar recubrimiento canónico usando el
algoritmo anterior.
Descomposiciones
• Motivación: Un algoritmo de normalización va
descomponiendo un esquema universal
– hasta obtener un esquema de BD relacional de calidad.
• Sea R un esquema de relación. Un conjunto de
esquemas de relación {R1,…,Rn} es una descom-
posición de R sii
R = R1 ∪ ... ∪ Rn.
Descomposiciones sin
Pérdida de información
• Ejemplo: Sea el siguiente esquema universal:
– SmaAutomotor = (DNI, nombre, marca, modelo, patente,
numSeguro, compañíaSeguro, direcciónCS)
• La siguiente es una descomposición de
SmaAutomotor:
– Persona = (DNI, nombre)
– Auto = (marca, modelo, patente)
– CompañíaAseguradora = (compañíaSeguro, direcciónCS)
– Seguro = (patente, compañíaSeguro, numSeguro)
• Sin embargo, esta descomposición tiene pérdida de
información, porque no se puede reflejar:
– qué persona es dueña de cuáles autos.
– Este es parte del significado de que una tupla pertenezca a
una tabla del esquema universal.
Metas de una buena descomposición
• ¿Qué cosas pedir a una descomposición para que
sea razonable?
Metas de una buena descomposición
• ¿Qué cosas pedir a una descomposición para que
sea razonable?
1. Que evite la redundancia de información.
2. Que evite pérdida de información importante en la BD.
• [Link]. que no se pierdan relaciones entre atributos (Noción de
descomposición de reunión sin pérdida).
3. Que la descomposición permita el chequeo eficiente de
restricciones de integridad (i.e. DF) luego de
actualizaciones en la BD.
• Noción de preservación de dependencias.
Descomposiciones sin
Pérdida de información
• Meta: Responder las siguientes preguntas.
• Problema 1: ¿Qué significa tener una descom-
posición del esquema universal donde todas las
relaciones entre atributos están representadas?
• Problema 2: ¿Cómo encontrar una de tales
descomposiciones?
Descomposiciones sin
Pérdida de información
• Solución 1 al problema 1:
1. Escribir qué significa que una tupla pertenezca a una tabla del
esquema universal RU ,
• expresando todas las relaciones entre atributos relevantes que nos
llegan a la mente o provistas por el cliente.
2. La descomposición de RU debe “preservar” ese significado.
• Esto es cierto si para cada conjunto de atributos relacionados, el conjunto
está contenido en el esquema de una tabla de la descomposición.
• Evaluación: Esta solución depende de nuestro buen juicio para
encontrar todas las relaciones entre atributos relevantes.
Descomposiciones sin
Pérdida de información
• Ejemplo: Sea el esquema universal de un banco.
Préstamo = (numSucursal, ciudad, activo, numCliente,
numPréstamo, importe)
– Lo descomponemos en:
SucursalCliente = (numSucursal, ciudad, activo, numCliente)
ClientePréstamo = (numCliente, numPréstamo, importe)
– Evaluación de la descomposición: Si tenemos un cliente con
varios préstamos en distintas sucursales:
• no se puede decir el préstamo que pertenece a cada sucursal en la
descomposición que tenemos.
• Luego en la descomposición que tenemos se perdió información con
relación al esquema universal.
Descomposiciones sin
Pérdida de información
• En el ejemplo anterior: es fácil darse cuenta que cliente
debe estar relacionado con préstamo pero es más difícil
saber que préstamo debe estar relacionado con sucursal.
• Conclusión: es fácil no darse cuenta de algunas
relaciones entre atributos y justo la descomposición que
se elige no las tiene en cuenta.
• Requisito: necesitamos una solución diferente que no
dependa de conocer todas las relaciones entre atributos
del problema.
Descomposiciones sin
Pérdida de información
• Problema 1: ¿Qué significa tener una descomposición del
esquema universal donde todas las relaciones entre atributos
están representadas?
• Solución 2: Sea r(R), R1, R2, , …, Rn descomposición de R, r
legal.
– En la práctica en lugar de almacenar r voy a almacenar tablas
para R1, R2, , …, Rn . Esas tablas son los ri = Ri (r) (i ∈ {1,2,…,n}).
– Idea genial: Si se puede reconstruir r a partir de los ri ,
entonces no se pierde información al descomponer.
• Aquí hablo de tirar r y usar los ri .
Descomposiciones sin
Pérdida de información
– ¿Qué significa reconstruir?
Por ejemplo, Sea:
SucursalCliente = (numSucursal, ciudad, activo, numCliente)
ClientePréstamo = (numCliente, numPréstamo, importe)
Descomposiciones sin
Pérdida de información
– ¿Qué significa reconstruir?
Por ejemplo, sea:
SucursalCliente = (numSucursal, ciudad, activo, numCliente)
ClientePréstamo = (numCliente, numPréstamo, importe)
– El único atributo en común entre SucursalCliente y Cliente-
Préstamo es numCliente.
• Luego a lo sumo puedo calcular el natural join de las dos.
– Generalizando: Reconstruir r significa: r = R (r1 ⨝r2 ⨝ … ⨝ rn)
• Se puede omitir R si el esquema de r1 ⨝r2 ⨝ … ⨝ rn es R.
– Ahora vemos un ejemplo de que no siempre se puede hacer tal
reconstrucción.
Descomposiciones sin
Pérdida de información
• Asumimos que r(Préstamo) viene dada por la siguiente tabla:
r numSucursal ciudad activo numCliente numPréstamo importe
Centro Arganzuela 9000000 Santos P17 1000
Becenil Aluche 400000 Santos P93 500
• Entonces
r1 numSucursal ciudad activo numCliente
centro Arganzuela 9000000 Santos
Becenil Aluche 400000 Santos
• Y
r2 numCliente numPréstamo importe
Santos P17 1000
Santos P93 500
Descomposiciones sin
Pérdida de información
• Por otro lado :
r1 ⨝ r2 numSucursal ciudad activo numCliente numPréstamo importe
Centro Arganzuela 9000000 Santos P17 1000
Centro Arganzuela 9000000 Santos P93 500
Becenil Aluche 400000 Santos P93 500
Becenil Aluche 400000 Santos P17 1000
• El ejemplo anterior muestra que al hacer r1 ⨝r2 se pueden
obtener más tuplas que en r.
– En ese caso no puedo reconstruir r desde r1 y r2.
Descomposiciones de
Reunión sin Pérdida
• ¿Cómo formalizamos la solución 2 al problema 1?
Descomposiciones de
Reunión sin Pérdida
• ¿Cómo formalizamos la solución 2 al problema 1?
• Definición: Sea C un conjunto de restricciones de
integridad de la BD y R un esquema de relación. Una
descomposición {R1,...,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 se cumple que
r = R r1 ⨝r2 ⨝… ⨝rn
– Recordar que ri = Ri (r) para todo i.
Descomposiciones sin
Pérdida de información
• Observación: Sea r(R) una relación y sea ri = Ri (r) (1 ≤ i ≤ n).
{r1, …, rn} es la BD que resulta de descomponer R en {R1,...,Rn}.
En general vale r ⊆ R r1 ⨝r2 ⨝… ⨝rn
• ¿Qué utilidad tiene esta observación?
Descomposiciones sin
Pérdida de información
• Problema 2: ¿Cómo encontrar una descomposición del
esquema universal en la cual todas las relaciones entre
atributos están representadas?
• Vamos a ver cómo resolver este problema cuando
veamos algoritmos de normalización.
• Por ahora atacaremos un problema más básico:
• Problema 3: ¿Cómo probar que una descomposición del
esquema universal es de reunión sin pérdida?
Descomposiciones de
Reunión sin Pérdida
• Proposición 2: Una descomposición de R en R1 y R2
es de reunión sin pérdida si al menos una de las
+
siguientes DF está en F :
R1 R2 R1
R1 R2 R2
• ¿Qué nos dice este resultado?
Descomposiciones de
Reunión sin Pérdida
• Proposición 2: Una descomposición de R en R1 y R2
es de reunión sin pérdida si al menos una de las
+
siguientes DF está en F :
R1 R2 R1
R1 R2 R2
• ¿Qué nos dice este resultado?
• Las DF del problema actual pueden servir para decir
si la descomposición es de reunión sin pérdida.
Descomposiciones de
Reunión sin Pérdida
• Ejercicio: Si considero la descomposición de Préstamo en:
– Sucursal = (numSucursal, ciudad, activo)
– InfoPréstamo = (numSucursal, numCliente, numPréstamo, importe)
– ¿Se puede recuperar r(Préstamo) legal a partir de r1(Sucursal) y
r2(InfoPréstamo)? (usar la proposición anterior)
Descomposiciones de
Reunión sin Pérdida
• Ejercicio: Si considero la descomposición de Préstamo en:
– Sucursal = (numSucursal, ciudad, activo)
– InfoPréstamo = (numSucursal, numCliente, numPréstamo, importe)
– ¿Se puede recuperar r(Préstamo) legal a partir de r1(Sucursal) y
r2(InfoPréstamo)?
– Notar que para Sucursal, se tiene la DF:
numSucursal ciudad, activo
– Obviamente que numSucursal ciudad, activo, numSucursal
Descomposiciones de
Reunión sin Pérdida
• La prueba se hace para el caso donde R1 R2 R1∊ F+. La
prueba del otro caso es similar y por eso se omite.
• Sea r legal. Probaremos que r ⊇ R (R1(r) ⨝R2 (r)).
t∈ R (R1(r) ⨝ R2 (r))
(⇒) t1[R1] = t[R1] ⋀ t2[R2] = t[R2] para algún t1, t2 ∈ r
(⇒) t2[R2] = t[R2] ⋀ t1[R1] = t[R1] ⋀
t2[R1⋂R2] = t1[R1⋂R2] ⋀ t1, t2 ∈ r
(⇒) t2[R2] = t[R2] ⋀ t2[R1] = t1[R1] ⋀ F ⊨ R1 R 2 R1
t1[R1] = t[R1] ⋀ t2 ∈ r y r legal bajo F
(⇒) t2[R2] = t[R2] ⋀ t2[R1] = t[R1] ⋀ t2 ∈ r
(⇒) t2[R] = t[R] ⋀ t2 ∈ r R = R 1 ⋃ R2
(⇒) t = t2 ⋀ t2 ∈ r
(⇒) t ∈ r
Descomposiciones de
Reunión sin Pérdida
• Ejercicio: ¿Sea R = (A, B), R1 = (A), R2 = (B), será esa una
descomposición de reunión sin pérdida?
– Ayuda: ¿qué significa probar que no lo es? Probarlo.
• Ejercicio: Sean R = (A, B, C, D), F = {ABC, D A, BD}
y Q = {(A, B), (A, C), (B, D)} una descomposición de R. ¿es Q
de reunión sin pérdida? Justifique su respuesta.
– Ayuda: usar el mismo procedimiento que con la prueba de la
proposición anterior (hasta las dos primeras implicaciones
inclusive) y luego usar las DF de F y la definición de DF hasta
llegar a la parte donde se hacen las 3 últimas implicaciones.
Chequeo Eficiente de las DFs
• Objetivo: obtener una descomposición del esquema
universal que permita el chequeo eficiente de las DFs del
problema actual en la BD.
• Meta: Responder las siguientes preguntas:
• Problema 1: ¿Qué significa que el chequeo en la BD por
violaciones de DFs luego de actualizaciones a la BD sea
eficiente?
• Problema 2: ¿Cómo encontrar una descomposición del
esquema universal que permita esto?
Chequeo Eficiente de las DFs
• ¿Qué es lo que hace costoso chequear una DF en la BD?
• Ejemplo: Sea R = (A, B, C, D) con DFs
F = {CA, AC, ADB}.
– R1 = (A,C) y R2 = (C,D,B) - de reunión sin pérdida.
– Si tengo r1(R1) y r2(R2), para chequear ADB necesito
hacerlo en r1 ⨝ r2 .
• ¿Qué conclusión se puede sacar de este ejemplo?
Chequeo Eficiente de las DFs
• Conclusión: Chequear algunas DF en la BD obligan a
construir reuniones naturales de tablas y luego
chequearlas.
– Esto suele ser muy costoso.
– Deseo: A uno le gustaría que no haya que calcular
reuniones naturales para chequear las DF en la BD.
Chequeo Eficiente de las DFs
• Proposición 3: R1,…, Rn, descomposición de R, F
conjunto de DFs, r(R) legal, α, β ⊆ Ri, entonces: αβ
se cumple en ∏Ri (r) si y solo si αβ se cumple en r .
• ¿Cuáles son las DF que se pueden chequear
eficientemente en la BD?
Chequeo Eficiente de las DFs
• Proposición 3: R1,…, Rn, descomposición de R, F
conjunto de DFs, r(R) legal, α, β ⊆ Ri, entonces: αβ
se cumple en ∏Ri (r) si y solo si αβ se cumple en r .
• ¿Cuáles son las DF que se pueden chequear
eficientemente en la BD?
• Respuesta: DF con atributos en miembros de la
descomposición se pueden chequear eficientemente.
– Porque no hace falta calcular reuniones naturales para su
chequeo.
Chequeo Eficiente de las DFs
• Definición: Sea F un conjunto de DF del esquema R y R1, R2,..,
Rn, una descomposición de R. La restricción de F a Ri se
denota Fi y es el conjunto de todas las DF de F+ que incluyen
solo atributos de Ri. Formalmente:
Fi = {αβ ∈ F+ : α, β ⊆ Ri} .
Chequeo Eficiente de las DFs
• Problema 1: ¿Qué significa que el chequeo en la
BD por violaciones de DFs luego de
actualizaciones a la BD sea eficiente?
Chequeo Eficiente de las DFs
• Problema 1: ¿Qué significa que el chequeo en la
BD por violaciones de DFs luego de
actualizaciones a la BD sea eficiente?
• Solución: Que F sea equivalente a conjunto G de
DF que se pueden chequear eficientemente;
– o sea, en las tablas de la BD.
Preservación de Dependencias
• ¿Cómo formalizar la solución anterior?
• Sea F’ = F1 F2 … Fn. Se dice que las
descomposiciones donde se cumple F’+ = F+ son
descomposiciones que conservan las dependencias.
• Procedimiento: para cada Fi se puede calcular un
cubrimiento canónico
– y la unión de todos esos cubrimientos canónicos será el
conjunto de DFs (del problema actual) a chequear.
Preservación de Dependencias
• Problema 2: ¿Cómo encontrar una descomposición del
esquema universal que preserva las dependencias?
• Vamos a ver cómo resolver este problema cuando
veamos algoritmos de normalización.
• Por ahora atacaremos un problema más básico:
• Problema 3: ¿Cómo chequear que una descomposición
del esquema universal preserva las DFs?
Preservación de Dependencias
• Solución 1: Computar (F1 F2 … Fn)+ y probar
que F ⊆ (F1 F2 … Fn)+ .
• Evaluación: Vimos que computar el cierre de un
conjunto de DF es demasiado costoso.
Preservación de Dependencias
• Ejercicio: Sea R = (A, B, C) con conjunto de DFs:
F = {AB, BC}, y sea la descomposición de R:
R1 = (A, B), R2 = (B, C) .
¿Esta descomposición preserva las dependencias?
¿Generalizando el ejemplo anterior qué podemos decir?
Preservación de Dependencias
• Ejercicio: Sea R = (A, B, C) con conjunto de DFs:
F = {AB, BC}, y sea la descomposición de R:
R1 = (A, B), R2 = (B, C) .
¿Esta descomposición preserva las dependencias?
¿Generalizando el ejemplo anterior qué podemos decir?
Si se puede comprobar cada miembro de F en alguna de las
relaciones de la descomposición, entonces la descomposición
trivialmente preserva las dependencias.
Preservación de Dependencias
Situación: Hay casos en los que una descomposición
preserva las dependencias y hay un miembro de F que
no puede verificarse en ninguna de las tablas de la BD.
• Ejemplo: Sea R = (A, B, C, D) con DFs
F = {CA, AC, ADB}.
– R1 = (A,C) y R2 = (C,D,B)
– ADB no puede comprobarse en las tablas de la BD.
– Pero esta descomposición preserva las dependencias.
– ¿Cómo probarlo?
Preservación de Dependencias
• Solución 2: Hacer el chequeo de preservación de las
DFs usando la definición de preservación de
dependencias y conceptos como deducción,
proyección, etc.
– Se puede intentar probar: F1 F2 … Fn ⊢ F
• Ejercicio: Sea R = (A, B, C, D) con DFs
F = {CA, AC, ADB}.
– R1 = (A,C) y R2 = (C,D,B)
Preservación de Dependencias
• Solución 3: Para la comprobación de la preservación de
las dependencias se aplica el siguiente procedimiento a
cada DF ∊F:
– result =
while (changes to result) do
for each Ri in the decomposition
t = (result Ri)+ Ri
result = result t
– Si result contiene todos los atributos en , entonces la DF
es preservada.
Preservación de Dependencias
Aplicamos la prueba a todas las DF de F para chequear si
una decomposición preserva las dependencias.
La descomposición preserva las dependencias si y solo sí
cada DF de F se preserva.
Este procedimiento es completamente automático.
Este procedimiento toma tiempo polinomial.
Preservación de Dependencias
• Ejercicio: Sea R = (A, B, C) con conjunto de DFs
F = {AB, BC}, y sea la descomposición de R:
R1 = (A, B), R2 = (A, C) .
– ¿Será que esa descomposición conserva las dependencias?
• Resolver primero usando definición de preservación de
dependencias.
• Resolver luego usando el algoritmo anterior.