BASES DE DATOS PRACTICO 7 IN.CO. 92 Soluciones. Ejercicio 1. a)- No se cumple. Contraejemplo: F = CDE --> A (1) E --> D (2) Verifico si en (1) hay atributos redundantes. + + (CE)S1FT = {C,E,D,A} => CE --> A î F => En CDE --> A, el atributo D es redundante y no existe W --> S î F con W <> (CDE). b)- Es correcto. Lo demostraremos por el absurdo. Suponemos que no existe W <> X / W --> Y î F y que X--> Y es redundante en F. Sea FS11T = F - {X --> Y}. Como X -->Y es redundante en F + + => (X --> Y) î FS11T => Y C_ XS1F1T + Consideremos el calculo de XS1F1T, aplicando el algoritmo: + - En el calculo de XS1F1T, obtengo Y - en el primer paso o bien - en el n_esimo paso con n > 1 - Si obtengo Y en el primer paso del algoritmo => existe W --> Y î FS11T, W C_ X W <> X (porque X --> Y C_/ FS11T) => existe W --> Y î F con W <> X. Absurdo. S1(n-1)T - Si obtengo Y en el n_esimo paso del algoritmo: llamamos Z = XS1F1T => existe W --> Y î FS11T W C_ Z C_ X W <> X => existe W --> Y î F con W <> X. Absurdo. c)- No se cumple el sii .Si hay una dependencia A --> B => R es igual al join R1 |><| R2 (Por el teorema de descomposicion con join sin perdida). .Si R = R1 |><| R2 no necesariamente se cumple A --> B en R. Contraejemplo: R(A, B, C) R1(A, B) R2(A, C) a1 b1 c1 a1 b1 a1 c1 a1 b2 c1 a1 b2 R1|><|R2 (A, B, C) a1 b1 c1 R1|><|R2 = R y en R A -/-> B a1 b2 c1 Ejercicio 2. F = { AB -> C, A -> B } y G = { A -> B, B -> C } a). G no es un cub. minimal de F, porque no son equivalentes. .Tratemos de deducir (B -> C) a partir de F. .(B)+S1FT= {B}, por lo que F |=/ (B -> C). b). En F se cumple A -> C, (A)+={A,B,C}, por lo que reemplazo AB -> C por A -> C. Queda F1 = { A -> B, A -> C } que es minimal. Ejercicio 3. .R(A,B,C,D) y F = { A -> C, D -> C, BD -> A }. .p={(AB),(ACD),(BCD)}. | A B C D ------------------------------ R1 = AB | a1 a2 a3(1) b14 ==> No tiene jsp segun F. ------------------------------ R2 = ACD | a1 b22 a3 a4 ------------------------------ R3 = BCD | b31 a2 a3 a4 ------------------------------ => Sigo el mecanismos utilizado en el ej. 4 para construir el contraejemplo. r = { (a1,a2,a3,b14),(a1,b22,a3,a4),(b31,a2,a3,a4) } r1 = { (a1,a2), (a1,b22), (b31,a2) } r2 = { (a1,a3,b14), (a1,a3,a4), (b31,a3,a4) } r3 = { (a2,a3,b14),(b22,a3,a4),(a2,a3,a4) } .Al joinear r1 con r2 aparece la tupla (a1,a2,a3,a4), que luego al hacer el join con r3 se mantiene porque esta (a2,a3,a4) en r3. .Entonces en r1|><|r2|><|r3 aparece (a1,a2,a3,a4), que no existe en r. => La desc. tiene join CON perdida. Ejercicio 4. .R(A,B,C,D,E,G) y F = {A --> C, B --> D, E --> G, GE --> D, C --> E D --> G, G --> C, CD --> A } a). p = { (AB),(CDE),(EG),(BC) } | A B C D E G ---------------------------------------- AB | a1 a2 a3 b14 a6 A -> C ---------------------------------------- B -> D, D -> G,G->C,CD->A CDE | a3 a4 a5 a6 E -> G, G -> C ---------------------------------------- DG -> A EG | a3 a5 a6 C -> E ---------------------------------------- BC | a2 a3 b14 a5 a6 ---------------------------------------- | A B C D E G ---------------------------------------- AB | a1 a2 a3 b14 a6 A -> C ---------------------------------------- B -> D, D -> G,G->C,CD->A CDE | a3 a4 a5 a6 E -> G, ---------------------------------------- GE -> D EG | a3 a5 a6 C -> E ---------------------------------------- BC | a1 a2 a3 b14 a5 a6 ---------------------------------------- | A B C D E G ---------------------------------------- Por aplicacion de: AB | a1 a2 a3 b14 a6 ---------------------------------------- B -> D, D -> G,G->C,CD->A CDE | a3 a4 a5 a6 E -> G, ---------------------------------------- GE -> D EG | a3 a5 a6 C -> E ---------------------------------------- BC | a1 a2 a3 b14 a5 a6 ---------------------------------------- | A B C D E G ---------------------------------------- AB | a1 a2 a3 a5 a6 ---------------------------------------- CDE | a3 a4 a5 a6 ---------------------------------------- EG | a3 a5 a6 ---------------------------------------- BC | a1 a2 a3 a4 a5 a6 Tiene join sin perdida. b). | A B C D E G ---------------------------------------- AB | a1 a2 ---------------------------------------- CDE | a3 a4 a5 ---------------------------------------- EG | a5 a6 ---------------------------------------- BC | a2 a3 ---------------------------------------- Aplicando B --> D, E --> G, C --> E, E --> G, D --> G, G --> C luego aplico CD --> A, C --> E | A B C D E G ---------------------------------------- AB | a1 a2 a3 a5 a6 ---------------------------------------- CDE | a3 a4 a5 a6 ---------------------------------------- EG | a3 a5 a6 ---------------------------------------- BC | a1 a2 a3 a5 a6 ---------------------------------------- Tiene join con perdida. r = a1 a2 a3 b14 a5 a6 b21 b22 a3 a4 a5 a6 b31 b32 a3 b34 a5 a6 a1 a2 a3 b14 a5 a6 c)- F = {B --> D, E --> G, C --> E, D --> G, G --> C, GE --> D, CD -->A} A B C D E G --------------------------------- AB | a1 a2 --------------------------------- CDE| a3 a4 a5 --------------------------------- EG | a5 a6 --------------------------------- BC | a2 a3 --------------------------------- Aplico B --> D, E --> G, C --> E, E --> G, D --> G, G --> C, CD --> A, C --> E , luego aplico EG --> D A B C D E G --------------------------------- AB | a1 a2 a3 a4 a5 a6 --------------------------------- CDE| a3 a4 a5 a6 --------------------------------- EG | a3 a4 a5 a6 --------------------------------- BC | a1 a2 a3 a4 a5 a6 --------------------------------- Es con join sin perdida. Ejercicio 5. Contraejemplo: .R(A,B,C,D), F = { AB -> C, C -> D } y p = {(AB),(CD)}. | | + R1 R2 A --> B î F ? + + A --> CD î F ? AS1FT = {A} => Es con join con perdida. Ejercicio 6. .R(A,B,C,D,E,G) F = { A -> BC, C -> DG, BD -> E, AB -> D, BC -> G } a). R1(ABC) { A -> BC } R2(CDG) { C -> DG } R3(BDE) { BD -> E } Sea H = ãS1R1T(F) U ãS1R2T(F) U ãS1R3T(F) = { A --> BC, C --> DG, + BD --> E} Verifico si AB --> D î H ? + + (AB)S1HT = {A,B,C,D,G,E} => AB --> D î H + Verifico si BC --> G î H ? + + (BC)S1HT = {B,C,D,G,E} => BC --> G î H => p preserva las df. b). R1(ADE) { A --> DE } R2(ABC) { A --> BC } R3(ADG) { A --> DG } Sea H = ãS1R1T(F) U ãS1R2T(F) U ãS1R3T(F) = { A --> DE, A --> BC, + A --> DG} Verifico si C --> DG î H ? + + ==> C --> DG î/ H ==> p no preserva CS1HT = { C } C --> DG î F las dfs. Sean r1, r2, r3 relaciones de R1, R2 y R3 respectivamente (A D E) (A B C) (A D G) a1 d1 e1 a1 b1 c1 a1 d1 g1 a2 d2 e1 a2 b2 c1 a2 d2 g2 Al realizar r1 |><| r2 |><| r3 obtengo las tuplas A B C D E G a1 b1 c1 d1 e1 g1 a2 b2 c1 d2 e1 g2 donde no se cumple C --> DG ==> no es una relacion valida de R. c). R1(ABDE) { A -->BDE, BD --> E } R2(BCG) { BC --> G, C --> G} = { C --> G} R3(CDG) { C --> DG } Sea H = ãS1R1T(F) U ãS1R2T(F) U ãS1R3T(F) = { A --> BDE, BD --> E, BC --> G, C --> G, + C --> DG } Verifico si A --> C î H + + AS1HT = { A,B,D,E } ==> A --> C î/ H ==> p no preserva las dfs. d). R1(ABCG) { A --> BCG, C --> G} R2(CD) { C --> D } R3(ADE) { A --> DE } Sea H = ãS1R1T(F) U ãS1R2T(F) U ãS1R3T(F) = { A --> BCG, C --> DG, + A --> DE} Verifico si BD --> E î H + + (BD)S1HT = { B,D } ==> BD --> E î/ H ==> p no preserva las dfs. e). R1(AB) { A --> B } R2(AC) { A --> C } R3(AD) { A --> D } R4(CG) { C --> G } R5(BDG) { BD --> E } Sea H = ãS1R1T(F) U ãS1R2T(F) U ãS1R3T(F) U ãS1R4T(F) U ãS1R5T(F) = { A --> BCD, C --> G, BD --> E } + Verifico si C --> D î H + + CS1HT = { C,G } ==> C --> D î/ H ==> p no preserva las dfs. f). R1(ABCDG) {A --> BCDG, C --> DG} R2(BE) {} R3(DE) {} + Verifico si BD --> E î H Sea H = ãS1R1T(F) U ãS1R2T(F) U ãS1R3T(F) + + BDS1HT = {B,D} => BD --> E î/ H => p no preserva dfs. Ejercicio 7. a). No se cumple. Sea R(A,B,C) y F={A -> B, B -> C}. p={ (AC),(AB) } tiene jsp y se pierde B -> C. b). No se cumple. Sea R(A,B,C,D) y F = { A -> B, C -> D }. p={ (AB),(CD) } pres. fds pero no tiene jsp. Ejercicio 8. => R(A,B,C,D) y F = { A -> B, B -> C, A -> D, D -> C }. p={(AB),(AC),(BD)}. a). R1(A,B) { A -> B } R2(A,C) { A -> C } R3(B,D) { } b). Aplico alg. 2. | .Tomo una relacion r con 3 tuplas: | { (a1,a2,a3,b14), (a1,a2,a3,b14), | A B C D | (b31,a2,a3,a4) } ---------------------------- | AB | a1 a2 a3(2) b14 | .Esta relacion satisface F. ---------------------------- | AC | a1 a2(1) a3 b14 | .Proyecto por (AB),(AC) y (BD), y "joineo" ---------------------------- | (AB) con (AC). BD | b31 a2 a3(2) a4 | .Queda la siguiente relacion para (ABC): ---------------------------- | { (a1,a2,a3), (b31,a2,a3) }. ==> La desc. no tiene jsp | .Ahora "joineo" esta rel. con la que quedo segun F. | para (BD), y queda: | { (a1,a2,a3,b14), (a1,a2,a3,a4), ... }. ==> La tupla (a1,a2,a3,a4) no pertenecia a r, por lo que la desc. tiene join CON perdida. c). R(A,B,C,D) y F = { A -> B, B -> C, A -> D, D -> C }. p={(AB),(AC),(BD)}. Por a): R1(A,B) { A -> B }, R2(A,C) { A -> C }, R3(B,D) { } .Trato de deducir (B -> C) a partir de la union de las proyec. de F. (B)+={B}, se pierde B -> C. .Lo mismo con (A -> D), (A)+={ABC}, se pierde A -> D. .Lo mismo con (D -> C), (D)+={D}, se pierde D -> C. Ejercicio 9. a). Es correcto. Supongo que p no preserva dfs de F => ]- (X-->Y) î F / (X-->Y) no proyecta en ningun Ri de p. Pero por construccion para cada (X-->Y) î F obtengo un esquema (XY) => Esta df se proyecta en este esquema . Absurdo. => p preserva las dfs. b). Contraejemplo. R(ABCD) F = { A --> B, C --> D } R1(AB) R2(CD) Ejercicio 10. a). Incorrecto, por definicion. Un esquema p esta en determinada forma normal si todos los subesquemas de p estan en esa forma normal. b). Incorrecto, por definicion. c). Incorrecto, por definicion. d). Incorrecto. .Si R esta en BCNF => R esta en 3NF. .Pero R puede estar en 3NF y no estar en BCNF. R(ABCD) 3NF AB --> CD C --> A viola BCNF. e). Correcto. Por definicion R esta en 2NF si no se cumplen df parciales. Por definicion R esta en 3NF si no se cumplen df parciales y df transitivas. f). Incorrecto. Si en F hay dfs parciales => R no esta en 2NF. => R no esta en BCNF. Pero en cada ãS1RiT (F) pueden ser que para todo X --> Y î ãS1RiT(F) X sea superclave => entonces Ri estaria en BCNF. O sea que p estara en BCNF si solo se proyectan dependencias que en cada esquema no violan BCNF. g). Incorrecto. Justificacion analoga al caso anterior. h). Correcto. Si para cada Ri, las dfs de ãS1RiT(F) son tales que los atributos de la parte izquierda son superclave => (def) Ri esta en BCNF. Si todas las Ri estan en BCNF => p esta en BCNF. Ejercicio 11. R(ABCDEG) F = { A --> BC, C --> DG, BD --> E, AB --> D, BC --> G} a). p = { (ABC), (CDG), (BDE) } R1(ABC) {A --> BC} Clave: A => R1 esta en BCNF. R2(CDG) {C --> DG} Clave: C => R2 esta en BCNF. R3(BDG) {BD --> E} Clave: BD => R3 esta en BCNF. => p esta en BCNF. b). p = { (ADE), (ABC), (ADG) } R1(ADE) {A --> DE} Clave: A => R1 esta en BCNF. R2(ABC) {A --> BC} Clave: A => R2 esta en BCNF. R3(ADG) {A --> DG} Clave: A => R3 esta en BCNF. => p esta en BCNF. c). p = { (ABDE), (BCG), (CDG) } R1(ABDE) {A --> BDE, BD --> E} Clave: A => BD --> E es una dep. transitiva. => R1 esta en 2NF. R2(BCG) {C --> G} Clave: BC => C --> G dependencia parcial=>R2 esta en 1NF. => p esta en 1NF. d). p = { (ABCG), (CD), (ADE) } R1 (ABCG) { A --> BCG, C --> G} Clave: A => C --> G es una df. transitiva => R1 esta en 2NF. R2 (CD) { C --> D } Clave: C => R2 esta en BCNF. R3 (ADE) {A --> DE } Clave: A => R3 esta en BCNF. => p esta en 2NF. e). p = { (AB), (AC), (AD), (CG), (BDE) } R1(AB) {A --> B} Clave: A => R1 esta en BCNF. R2(AC) {A --> C} Clave: A => R2 esta en BCNF. R3(AD) {A --> D} Clave: A => R3 esta en BCNF. R4(CG) {C --> G} Clave: C => R4 esta en BCNF. R5(BDE) {BD --> E} Clave: BD => R5 esta en BCNF. => p esta en BCNF. f). p = { (ABCDG), (BE), (DE) } R1(ABCDG) {A --> BCDG, C --> DG} Clave: A => C --> DG es df transitiva => R1 esta en 2NF. R2(BE) { } => R2 esta en BCNF. R3(DE) { } => R3 esta en BCNF. => p esta en 2NF. Ejercicio 12. a). A B C D E G ---------------------------------------------- R1(ABCD) | a1 | a2 | a3 | a4 | a5 | a6 AB --> CD ---------------------------------------------- A --> E R2 (AE) | a1 | b22 | b23 | b24 | a5 | b26 B --> G ---------------------------------------------- EG --> C R3 (BG) | b31 | a2 | b33 | b34 | b35 | a6 ---------------------------------------------- R4 (EGC) | b41 | b42 | a3 | b44 | a5 | a6 ---------------------------------------------- Aplico A --> E, B --> G y obtengo toda la primer fila con ai => p tiene jsp. ãS1R1T(F) = {AB --> CD } Clave: AB => R1 esta en BCNF. ãS1R2T(F) = {A --> E } Clave: A => R2 esta en BCNF. ãS1R3T(F) = {B --> G } Clave: B => R3 esta en BCNF. ãS1R4T(F) = {EG --> C } Clave: EG => R4 esta en BCNF. => p preserva las dependencias funcionales. c). R1 (A B C D) R2 (A E) r1 a1 b1 c1 d1 r2 a1 e1 R3(B G) R4 (E G C) r3 b1 g1 r4 e1 g1 c2 En r1 podemos ver que asociado a "a1 b1" tenemos "c1". En r2 asociado a "a1" tenemos "e1". En r3 asociado a "b1" tenemos "g1". => Esperamos que en r4 asociado a "e1 g1" tengamos "c1", pero no tenemos forma de imponer esto. Ejercicio 13. .Sea R y F conj. de fds, tales que hay una clave unica X de R s/F. .Si R esta en 3NF s/F, entonces V- (Y -> A) î F, Y es superclave o A primo. (por supuesto no se consideran las fds triviales) .Si V- (Y -> A) î F se cumple que Y es superclave, entonces R esta en BCNF. * Supongamos que ]- (Y -> A) î F tq. Y no es superclave (A debe ser primo). + Caso 1: Y C X. .Sea Z = X - {A}, se cumple que: Y C_ Z ==> Z -> Y -> A entonces: Z -> ZA ==> Z -> X y Z C X ==> X no es clave entonces: A no es primo, ABSURDO. + Caso 2: Y C/ X. .Sea Z = { X - {A} } U Y. .Se cumple que: Z -> Y -> A ==> Z -> A ==> Z -> ZA ==> Z -> X. .Entonces Z es superclave y X C_/ Z, por lo que existe otra clave ademas de X. ABSURDO. ==> Entonces no existen fds (Y -> A) con Y no superclave y A primo. ==> V- (Y -> A) Y es superclave. ==> R esta en BCNF s/F. Ejericico 14. a). i)- Correcto, porque se demostro que en cada paso del algoritmo la descomposicion es con jsp. ii)- Incorrecto, porque sino el algoritmo hubiera terminado. iii)- Incorrecto, en la descomposicion p, hay por lo menos un esquema que no esta en BCNF, mas aun este esquema puede no estar en 3NF. iv)- Correcto, por la definicion de modelo relacional . v)- Incorrecto, pues el algoritmo no garantiza la preservacion de dependencias en ninguno de sus pasos. b). i)- Correcto, lo garantiza el algoritmo. ii)- Correcto, lo garantiza el algoritmo. iii)- Correcto, al finalizar el algoritmo, la descomposicion esta en BCNF, por lo tanto la descomposicion esta en 3NF. iv)- Correcto, por la definicion del Modelo Relacional v)- Incorrecto, pues el algoritmo no garantiza la preservacion de dependencias en ninguno de sus pasos. Ejercicio 15. Si R1 y R2 son el resultado del primer paso del algorimo que lleva a BCNF => 1._ B --> A î F. 2._ B no es superclave en R segun F (sino B-->A no violaria BCNF) a). Esta consulta cuenta las tuplas del resultado de: r - (r1|><|r2). Pero como el algoritmo garantiza obtener descomposicion son jsp en todos sus pasos => r = r1|><|r2 => Esta consulta dara como resultado: O/ b). En R1 (AB) se cumple la df: B --> A => B es clave de R1. => Al agrupar por B, no obtendremos grupos con mas de un elemento. => Esta consulta dara como resultado O/. c). Aqui no podemos predecir el resultado, ya que no tenemos ningun tipo de informacion de si existe alguna relacion de los valores de A a los valores de B. d). No se puede predecir el resultado, de forma analoga al caso anterior no sabemos si existe o no alguna relacion entre los valores de B y los valores de C, D. Ejercicio 16. a). Debemos demostrar que: 1._ El algoritmo para. 2._ La descomposicion resultante esta en 3NF. 3._ La descomposicion resultante es con jsp S/F. 1. Podemos afirmar que el algoritmo para ya que: - Si el esquema original esta en 3NF => el algoritmo termina. - Sino en cada momento cada esquema que no esta en 3NF es sustituido por dos esquemas con menos atributos. A lo sumo llegaremos a todos los esquemas con 2 atributos y estos siempre estan en 3NF. => En algun momento todos los esquemas estaran en 3NF. => El algoritmo para. 2. La descomposicion resultado esta en 3NF, ya que por la condicion de fin del algoritmo todos los esquemas estan en 3NF => la descomp. esta en 3NF. 3. Por propiedad vista en el curso teorico podemos afirmar que: p = {R1,....,Ri-1,Ri,Ri+1,.....,Rn} descomp de R con jsp S/F ç = {S1, S2} descomp de Ri con jsp S/F \______________________________________/ || \/ p2 = { R1,...,Ri-1,S1,S2,Ri+1,......,Rn} es una descomp de R con jsp. Demostraremos que en cada paso la descomposicion que realizamos es con jsp => (por prop. anterior) la descomposicion resultado es con jsp. La descomposicion que se realiza es la siguiente: Sea S esquema no esta en 3NF, sea F su conj. df. donde se cumple X-->A p = {S1,S2} donde S1 = (XA) S2 = (S - A) por el teorema 5 (visto en el curso teorico) p es una descomposicion con jsp <=> S1 ï S2 --> S1 - S2 + o S1 U S2 --> S1 - S2 pertenecen a F S1 ï S2 = X + S1 - S2 = A => X --> A î F (por hip) => p es con jsp. b) El algoritmo no toma en cuenta la preservacion de dependencias. r (ABCD) F = { A --> B, C --> D, D --> B } R (ABCD) / \ R1(AB) R2(ACD) A-->B C-->D / \ R21(CD) R22(AC) C-->D -- Se pierde D --> B.