EBASES DE DATOS PRACTICO 6 - -1 SOLUCIONES-0 IN.CO. 92F EEjercicio 1. F .Se tiene R(A,B,C,D,E) con F = { A -> B, B -> D, C -> E, E -> B }. a) b) c) d) A B C D E A B C D E A B C D E A B C D E ------------- ------------- ------------- ------------- a1 b1 c1 d1 e1 a1 b1 c1 d1 e1 a1 b1 c1 d1 e1 a1 b1 c1 d1 e1 a2 b2 c2 d1 e1 a2 b2 c2 d1 e2 a2 b1 c1 d2 e1 a1 b1 c2 d1 e1 ------------- ------------- ------------- ------------- .No sat. F .Sat. F. .No sat. F. .Sat F. .viola: .viola: E -> B. B -> D. EEjercicio 2. F FABS(#f,nombre,direccion) { #f -> nombre,direccion } PROD(#p,descripcion) { #p -> descripcion } VENDE(#f,#p,precio) { #f,#p -> precio } a). i). Como se cumple la fd (#f -> nombre,direc) en FABS y ‚sta involucra a todos los atributos de FABS, no pueden haber distintas tuplas con el mismo valor de #f. Por lo que el resultado debe ser 0 o 1. Pero como el resultado del SELECT COUNT(*) FROM FABS,VENDE ... da resultado > 0, esto significa que existe el fabricante #4 en FABS. ==> POR LO QUE EL RESULTADO ES 1. ii). Como se cumple la fd (#f -> nombre,direc) en FABS y ‚sta involucra a todos los atributos de FABS, no pueden haber distintas tuplas con el mismo valor de #f. Por lo que al agrupar las tuplas, quedar n grupos de a lo sumo un elemento. ==> POR LO QUE EL RESULTADO ES vacio. iii). Como se cumple (#f,#p -> precio) e involucra todos los atributos, no pueden haber tuplas que tengan valores repetidos de #f,#p. Por lo que al agrupar las tuplas quedar n grupos de un elemento. ==> ENTONCES EL RESULTADO ES vac¡o. b). select #p,count(*) from PRODS group by #p having count(*) > 1; .El resultado dar  los #p para los cuales se viola (#p -> descrip), junto con la cantidad de tuplas con ese #p repetido. c). El resultado de la consulta dada indica que hay por lo menos 2 fabricantes de nombre "juan". Las tuplas del resultado no pueden corresponder a un mismo fabricante ya que, dado un producto, s¢lo puede haber una tupla por fabricante en VENDE; entonces si hubiera un solo "juan" entre los fabricantes, habr¡a una sola tupla que lo asocia con el producto #10. Observar que podr¡an haber m s fabricantes de nombre "juan", que no venden el producto #10. Entonces el resultado de la segunda consulta ser  vac¡o. d). Si las (f1 p1 r1) y (f1 p1 r2) son validas en VENDE, significa que no se cumple la fd (#f,#p -> precio), por lo que el resultado de la primera consulta podria corresponder a un mismo fabricante de nombre "juan". ==> ENTONCES el resultado de la 2a. no tiene porque ser vacio. EEjercicio 3. F .Tomamos como definicion de 4dependencia funcional5 la siguiente: DEFINICION. .Sea R(A1,...,An) un esquema relacion, y X y Y subconjuntos de {A1,...,An}. .Decimos que X -> Y, que se lee X determina funcionalmente Y si para toda relacion r que sea valor corriente de R, no es posible que r tenga dos tuplas que coincidan en los atributos de X y no lo hagan en los de Y. a). Es correcta, corresponde directamente a la definicion. b). Idem a), pero usando "existe". c). No es correcta, ya que obligaria a que los valores de X y Y fueran siempre los mismos, lo cual es mas restrictivo que una fd. d). No es correcta, puede darse lo siguiente en R(X,Y,Z): R(X,Y,Z) .Se repiten valores de X y no se viola X -> Y. -------- x1 y1 z1 x1 y1 z2 -------- e). Es correcta. f). No es correcta, puede darse lo siguiente: R(X,Y,Z) --------- * No hay una corresp. biunivoca y x1 y1 z1 no se viola X -> Y. x2 y1 z1 -------- g). Es correcta, es equivalente a a). pero sin usar implicacion. h). No es correcta, ver caso f). EEjercicio 4. F a).{ X -> Y, Z -> Y } |= XZ -> Y Es correcta. Se obtiene aplicando aumentacion y descomposicion: X -> Y |= ZX -> YZ |= ZX -> Y (en realidad se utiliza una fd). b).{ XZ -> Y } |= X -> Y No es correcta. Ver este contraejemplo: R(X,Y,Z) * esta relacion sat. XZ -> Y, pero no -------- sat. X -> Y. x1 y1 z1 x1 y2 z2 -------- c).{ XZ -> Y, X -> Z } |= X -> Y X -> Z |= X -> XZ |= X -> Y (aplicando transitiva con XZ -> Y) d).{ XY -> Z, Z -> X } |= Z -> Y No se cumple. Ver el siguiente contraejemplo: R(X,Y,Z) * esta relacion sat. XY -> Z y Z -> X, -------- pero no Z -> Y. x1 y1 z1 x1 y2 z1 -------- e).{ X -> Y, Y -> Z } |= X -> YZ X -> Y |= X -> Z (por trans.) |= X -> YZ (por union). f).{ X -> Y, W -> Z, W C_Y } |= X -> Z .Se cumple Y -> W (fd trivial), y por transitiva: X -> Y -> W -> Z => X -> Z EEjercicio 5. F .Sea R(A,B,C,D,E,G,H,I) y F = { AB -> CH, CD -> B, B -> GAE, H -> DI }. i). (A)+ = {A} ii). (B)+ = {B,G,A,E,C,H,D,I} iii). (CD)+ = {C,D,B,G,A,E,H,I} iv). (BEI)+ = {B,E,I,G,A,C,H,D} v). (BE)+ = {B,E,G,A,C,H,D,I} vi). (HA)+ = {H,A,D,I} vii). (ABH)+= {A,B,H,C,D,I,B,E} EEjercicio 6. F .Sea F = { AB -> C, C -> D, B -> C, C -> E, HB -> D } .Se van a calcular los X+(F) correspondientes para cada fd, y se concluira si una fd X -> Y î F+ en caso de que Y î X+. i). (B)+={BC -1D-0}, D î B+ => (B -> D) î F+. ii). (E)+ = {E}, D î/ E+ => (E -> D) î/ F+. iii).(C)+ = {C -1DE-0}, (C -> DE) î F+. iv). (A)+ = {A), A -> C î/ F+. v). (HA)+ = {HA}, HA -> CD î/ F+. vi). (CD)+ = {CD -1E-0}, CD -> E î F+. vii).(A)+ = {A}, A -> D î/ F+. EEjercicio 7. F .Sea R(A B C D E G) y F = { AB -> D, CD -> G, E -> A, A -> C, BG -> C, D -> A } a). i). (AD)+ = {A,D,C,G} ii). (D)+ = {D,A,C,G} iii).(BC)+ = {B,C} iv). (EB)+ = {E,B,A,C,D,G} v). (B)+ = {B} vi). (EBC)+ = {E,B,C,A,D,G} b). Los conjuntos (EB) y (EBC) son superclave. c). El conj. que podria ser clave es (EB), pero primero hay que verificar que no contiene una clave. (E)+ = {EAC} no es clave. (B)+ = {B} no es clave ==> (EB) es clave d). B y E no quedan determinados por ningun otro conj. de atributos, porque nunca aparecen en la parte derecha de ninguna fd. Por lo que estaran contenidos en todas las claves. Pero (BE) es clave (por c).), por lo tanto no habra otra clave, porque si la hubiera deberia contener a (BE) y entonces seria superclave. ENTONCES: la unica clave es (BE). EEjercicio 8.F a). si existe X tq. no aparece en ninguna fd, X esta en toda clave. * Por absurdo, supongo que ]-Z clave tq. X C/_ Z. .si Z es clave, entonces se cumple Z -> X. .si Z -> X entonces, o bien X C_ Z (que contradice la hip), o bien Z -> X es una fd no trivial, lo cual contradice que X no aparece en ninguna fd. ==> ABSURDO, X pertenece a toda clave. b). si ]-X tq. no esta a la der. de ninguna fd, X esta en toda clave. * Por absurdo, supongo que ]-Z clave tq. X C/_ Z. .si Z es clave, entonces se cumple Z -> X. .si Z -> X entonces, o bien X C_ Z (que contradice la hip), o bien Z -> X es una fd no trivial, lo cual contradice que X no aparece a la derecha de ninguna fd. ==> ABSURDO, X pertenece a toda clave. c). idem anterior, hay una sola clave y es X. * No se cumple. Por ejemplo: R(A,B,C) y F = { A -> B } .En este caso A esta en las hipotesis y no es clave (y menos unica). d). idem anterior y X es superclave, X es clave y es unica. * Por b). X esta en toda clave. O sea toda clave contiene a X. Como X es superclave, X determina funcionalmente al resto de los atributos. ENTONCES ES CLAVE. Notar que es minimal porque no hay clave que no contenga a TODA X. * Es unica, porque si hubiera otra clave, deberia contener a X; y como X ya es clave la otra seria superclave. e). No se cumple. Contraejemplo: R(A,B,C,D) F = { AC -> B, A -> BC }. * (AC) es superclave y aparece a la izq. de (AC -> B), sin embargo no es clave ya que A lo es. EEjercicio 9. F .Sea R(A,B,C,D,E,G,H) y el conjunto de dependencias funcionales F = { AB -> CDE, C -> A, D -> E, H -> E, HE -> G } a). Aplicando props. del Ej. 8, se sabe que: .(BH) estan en todas las claves. .Verifico si se superclave: (BH)+ = {BHEG} no es superclave. .Considero los conjuntos de tres atributos que contienen a (BH): .(BHA)+ = {BHAEGCD} => (BHA) es clave. .(BHC)+ = {BHCEGAD} => (BHC) es clave. .(BHD)+ = {BHDEG} .(BHE)+ = {BHEG} .(BHG)+ = {BHGE} .Existiran mas claves ? Si existen contienen a (BH) y no a A ni a C, porque sino serian superclaves. Entonces considero X = R - {AC} y verifico si es superclave. X+ = (BDEGH)+ = {BDEGH}, no es superclave, por lo que ningun subconjunto de X lo sera, por lo que no hay superclaves que no contengan A ni C, por lo que no hay claves que no contengan ni A ni C. Por lo que no hay mas claves. ==> Las unicas claves son (BHA) y (BHC). b). Cubrimiento minimal. * PRIMER PASO: Obtengo conj. equivalente con un solo atr. a la derecha. .Aplicando la regla de descomposicion queda: F1 = { AB -> C, AB -> D, AB -> E, C -> A, D -> E, H -> E, HE -> G } * SEGUNDO PASO: Obtengo conj. eq. sin atrib. redundantes a la izq. .Parto de F1, veo si en las primeras tres fds hay atr. redundantes. .(A)+S1F1T = { A } => B no es redundante en las 1as. 3 fds. .(B)+S1F1T = { B } => A no es redundante en las 1as. 3 fds. .Ahora estudio (HE -> G). .(E)+S1F1T = { E } => G no es redundante en (HE -> G). .(H)+S1F1T = { HEG } => E es redundante en (HE -> G), por lo que tomo F2 equiv. a F1 de la forma: F2 = { AB -> C, AB -> D, AB -> E, C -> A, D -> E, H -> E, H -> G } .No hay otras fds que puedan tener atrib. redundantes a la izq. * TERCER PASO: Eliminar fds redundantes. .Para eso calculo XS0+TS1F2-{X->Y}T para toda (X -> Y). .Si Y î a esa clausura, se cumple X -> Y en F2 - {X -> Y}, por lo que X -> Y es redundante en F2. Si ocurre esto tomo un nuevo conj. de fds. F2 - {X -> Y}. .(AB)S0+TS1F2-{AB->C}T = {ABDE}, AB -> C no es redundante en F2. .(AB)S0+TS1F2-{AB->D}T = {ABCE}, AB -> D no redund. en F2. .(AB)S0+TS1F2-{AB->E}T = {ABCDE}, AB -> E es redundante en F2. => tomo F3 = F2 - {AB -> E} .(C)S0+TS1F2-{C->A}T = {C}, C -> A no es red. en F3. .(D)S0+TS1F2-{D->E}T = {D}, D -> E no es red. en F3. .(H)S0+TS1F2-{H->E}T = {HG}, H -> E no es red. en F3. .(H)S0+TS1F2-{H->G}T = {HE}, H -> G no es red. en F3. ==> QUEDA: Fmin = { AB -> C, AB -> D, C -> A, D -> E, H -> E, H -> G } EEjercicio 10. F .R(A,B,C,D,E,G,H,I) D HI A <-> EGC F = { A -> B, B -> C, E -> I, EGC -> B, G -> H, B -> A } * D no esta en ninguna fd, entonces esta en toda clave. .HI no estan nunca a la izq. en fds, entonces no sirven para determinar a ningun atributo, entonces no estan en ninguna clave. .E y G no estan a la derecha de ninguna dependencia, entonces estan en toda clave .Pruebo con (E,G,D), (EGD)+ = {E,D,G,I,H}, no es superclave, ent. no es clave. .Pruebo con claves de cuatro atributos: .(E,G,D,A)+ = {D,A,B,C,E,G,I,H} es clave .(E,G,D,B)+ = {D,B,C,E,G,I,H,A} es clave .(E,G,D,C)+ = {D,C,B,E,I,H,A,G} es clave No hay mas, pues si no serian superclaves. => LAS CLAVES SON: (EGDA),(EGDB),(EGDC). EEjercicio 11. F F = { AB -> C, C -> DE, E -> C } a). F1 = { AB -> CDE, E -> CD, C -> D } .No son equivalentes. Sea la siguiente relacion: R(A,B,C,D,E) ------------- .Satisface F1 pero no F. a1 b1 c1 d1 e1 (C -> E) î/ (F1)+ a1 b2 c1 d1 e2 -------------- b). F2 = { AB -> D, D -> C, C -> DE, E -> C } .No son equivalentes. Sea la siguiente relacion: R(A,B,C,D,E) -------------- .Satisface F pero no F2. a1 b1 c1 d1 e1 (D -> C) î/ F+ a1 b2 c2 d1 e2 -------------- c). F3 = { AB -> CDE, C -> D, C -> E, E -> C, E -> D } .Son equivalentes. Para eso verificaremos que cada fd de un conj. esta en la clausura del otro. * F C_ (F3)+: .(AB)S0+TS1F3T = {ABC ...} => (AB -> C) î (F3)+. .(C)S0+TS1F3T = {CDE ...} => (C -> DE) î (F3)+. .(E)S0+TS1F3T = {EC ...} => (E -> C} î (F3)+. * F3 C_ F+: .(AB)S0+TS1FT = {ABCDE} => (AB -> CDE) î F+. .(C)S0+TS1FT = {CDE ...} => {C -> D,C -> E} î F+. .(E -> C) î F. .(E)S0+TS1FT = {ECD} => (E ->D) î F+. ==> Por lo tanto son equivalentes. d). F4 = { A -> C, B -> C, C -> DE, E -> C } .No son equivalentes. Sea la siguiente relacion: R(A,B,C,D,E) -------------- .Satisface F pero no F4. a1 b1 c1 d1 e1 (A -> C, B -> C) î/ F+ a1 b2 c2 d1 e2 -------------- EEjercicio 12. F a) F1={A->XHG, GU->BC, AVC->D, BC->D, GUBC->D, G->D, AG->HB} Cubrimiento minimal. * PRIMER PASO: Obtengo conj. equivalente con un solo atr. a la derecha. .Aplicando la regla de descomposicion queda: F1'= { A->X, A->H, A->G, GU->B, GU->C, AVC->D BC->D, GUBC->D, G->D, AG->H, AG->B} * SEGUNDO PASO: Obtengo conj. eq. sin atrib. redundantes a la izq. .(G)+S1F1'T = { GD } => U no es redundante en (GU -> B). .(U)+S1F1'T = { U } => G no es redundante en (GU -> B). .(G)+S1F1'T = { GD } => U no es redundante en (GU -> C). .(U)+S1F1'T = { U } => G no es redundante en (GU -> C). .(AV)+S1F1'T = { AVXHGBD } => C es redundante en (AVC -> D), sustituyo (AVC -> D) por (AV -> D). .(A)+S1F1'T = { AXHGBD } => V es redundante en (AV -> D), sustituyo (AV -> D) por (A -> D). .(B)+S1F1'T = { B } => C no es redundante en (BC -> D). .(C)+S1F1'T = { C } => B no es redundante en (BC -> D). .(UBC)+S1F1'T = { UBCD } => G es redundante en (GUBC -> D), la sustituyo por (UBC -> D). .(BC)+S1F1'T = { BCD } => U es redundante en (UBC -> D), la sustituyo por (BC -> D),B y C no son redundantes pues ya vimos su clausura. .(A)+S1F1'T = { AXHGBD } => G es redundante en (AG -> H), la sustituyo por (A -> H). .En (AG -> B) no hay redundancia, pues ya calculamos la clausura de A y G. Queda F1" = { A->X, A->H, A->G, GU->B, GU->C, A->D, BC->D, G->D, AG->B} * TERCER PASO: Eliminar fds redundantes. .Para eso calculo XS0+TS1F2-{X->Y}T para toda (X -> Y). .Si Y î a esa clausura, se cumple X -> Y en F2 - {X -> Y}, por lo que X -> Y es redundante en F2. Si ocurre esto tomo un nuevo conj. de fds. F2 - {X -> Y}. .(A)S0+TS1F1"-{A->X}T = {AHGD}, A -> X no es redundante en F1". .(A)S0+TS1F1"-{A->H}T = {AXGD}, A -> H no redund. en F1". .(A)S0+TS1F1"-{A->G}T = {AXHD}, A -> G no es redundante en F1". .(GU)S0+TS1F1"-{GU->B}T = {GUCD}, GU -> B no es red. en F1". .(GU)S0+TS1F1"-{GU->C}T = {GUBD}, GU -> C no es red. en F1". .(A)S0+TS1F1"-{A->D}T = {AHGXD}, A -> D es red. en F1". .(BC)S0+TS1F1"-{BC->D}T = {BC}, BC -> D no es red. en F1". .(G)S0+TS1F1"-{G->D}T = {G}, G -> D no es red. en F1". .(AG)S0+TS1F1"-{AG->B}T = {AGXHD}, AG -> B no es red. en F3. Queda Fmin = { A->X, A->H, A->G, GU->B, GU->C, BC->D, G->D, AG->B } b) F = { AB->C, C->D, DA->F, F->A, CAF->G, CA->F, AB->F, ABF->H } * Luego del primer paso queda : F' = F * Luego del segundo paso queda : F" = { AB->C, C->D, CA->F, AB->H, DA->F, F->A, AB->F } * Luego del tercer paso queda : Fmin = { AB->C, C->D, DA->F, F->A, AB->H } c) F = { AB->C, BC->D, D->E, BE->C, CE->A, C->A, ACD->B, D->G, CG->B, CE->G } * Luego del primer paso queda : F' = F * Luego del segundo paso queda : F" = { AB->C, BE->C, D->G, BC->D, C->A, CG->B, D->E, CD->B, CE->G } * Luego del tercer paso queda : Fmin = { AB->C, D->G, C->A, D->E, BE->C, BC->D, CG->B, CE->G } EEjercicio 13. F a). Si se eliminan fds redundantes antes que atrib. redundantes, el resultado es siempre un conjunto minimal. * No se cumple. Sea F = { A -> B, AB -> C, C -> B } .Ya cumple la primer condicion. .Elimino fds redundantes: .(A)S0+TS1F-{A->B}T = {A} .(AB)S0+TS1F-{AB->C}T = {AB} => No hay fds redud. en F .(C)S0+TS1F-{C->B}T = .Elimino atr. redundantes a la izq. .(A)S0+TS1FT = {ABC}, (A -> B) î F+ => Sustituyo AB -> C por A -> B. => queda F1 = { A -> B, A -> B, C -> B } que claramente tiene fds redundantes. => El resultado de aplicar los pasos en este orden no siempre es un conj. minimal. b). Si se eliminan atrib. redundantes antes que fds redundantes, el resultado es siempre un conjunto minimal. * Para demostrarlo se deberia demostrar que en cada paso no se deja de cumplir propiedades obtenidas en pasos anteriores. .En el segundo paso se mantienen fds con un solo atributo a la derecha. .Lo mismo ocurre con el tercer paso. => La primer condicion se cumple siempre. .En el tercer paso no se generan fds con atributos redundantes a la izq. Efectivamente es asi, porque en el tercer paso no se generan nuevas fds, por lo tanto, si las ya existentes no tenian atrib. redundantes, el conj. resultante estara formado por fds que cumplen esta condicion. => La segunda condicion se cumple siempre. => Al final la tercera se cumple (porque se termina alli). ==> Si se aplican en este orden, se obtienen conjuntos minimales. EEjercicio 14. F .No se cumple porque no todo conjunto de fds acepta como equivalente otro que tiene fds con un unico atributo en la parte izquierda. .Sea F = { AB -> C }. El Fmin debera implicar a F. Para que ocurra esto Fmin debe contener (A -> C) o (B -> C). Pero los posibles Fmin que se pueden construir con alguna o ambas fds no son eq. a F ya que F no los implica. ==> No existe Fmin (superminimal) equivalente a F.