Trabajo Práctico 3
Estructuras de Almacenamiento de
Datos
ÍNDICE:
Ejercicio 1
Ejercicio 2
Ejercicio 3
Ejercicio 4
Ejercicio 5
Ejercicio 6
Ejercicio 7
Enunciado A
Enunciado B
Ejercicio 1
R = (A, B, C, D, E)
DF = {A → B; B → D; C → E; E → B}
(1) (2) (3) (4)
a. Instancia 1
t1 = <a1, b1, c1, d1, e1>
t2 = <a2, b2, c2, d1, e1>
DF#1: t1[A] =/= t2[A] el determinante es distinto entre las tuplas. No hace falta mirar
el determinado. CUMPLE
DF#2: t1[B] =/= t2[B] el determinante es distinto entre las tuplas. No hace falta mirar
el determinado. CUMPLE
DF#3: t1[C] =/= t2[C] el determinante es distinto entre las tuplas. No hace falta mirar
el determinado. CUMPLE
DF#4: t1[E] = t2[E] el determinante tiene el mismo valor entre las tuplas. Por lo tanto,
hay que verificar que el determinado tenga el mismo valor para que cumpla con DF:
t1[B] =/= t2[B] el determinado tiene distintos valores entre las tuplas, es decir, NO
CUMPLE.
NO SATISFACE
b. Instancia 2
t1 = <a1, b1, c1, d1, e1>
t2 = <a2, b2, c2, d1, e2>
DF#1: t1[A] =/= t2[A] el determinante es distinto entre las tuplas. No hace falta mirar
el determinado. CUMPLE
DF#2: t1[B] =/= t2[B] el determinante es distinto entre las tuplas. No hace falta mirar
el determinado. CUMPLE
DF#3: t1[C] =/= t2[C] el determinante es distinto entre las tuplas. No hace falta mirar
el determinado. CUMPLE
DF#4: t1[E] =/= t2[E] el determinante es distinto entre las tuplas. No hace falta mirar
el determinado. CUMPLE
SATISFACE
c. Instancia 3
t1 = <a1, b1, c1, d1, e1>
t2 = <a2, b1, c1, d2, e1>
DF#1: t1[A] =/= t2[A] el determinante es distinto entre las tuplas. No hace falta mirar
el determinado. CUMPLE
DF#2: t1[B] = t2[B] el determinante tiene el mismo valor entre las tuplas.
t1[D] =/= t2[D] el determinado tiene distintos valores entre las tuplas, es decir, NO
CUMPLE.
DF#3: t1[C] = t2[C] el determinante tiene el mismo valor entre las tuplas.
t1[D] = t2[D] el determinado tiene el mismo valor entre las tuplas, es decir, CUMPLE.
DF#4: t1[E] = t2[E] el determinante tiene el mismo valor entre las tuplas.
t1[B] = t2[B] el determinado tiene el mismo valor entre las tuplas, es decir, CUMPLE.
NO SATISFACE
d. Instancia 4
t1 = <a1, b1, c1, d1, e1>
t2 = <a1, b1, c2, d1, e1>
DF#1: t1[A] = t2[A] el determinante tiene el mismo valor entre las tuplas.
t1[B] = t2[B] el determinado tiene el mismo valor entre las tuplas, es decir, CUMPLE.
DF#2: t1[B] = t2[B] el determinante tiene el mismo valor entre las tuplas.
t1[D] = t2[D] el determinado tiene el mismo valor entre las tuplas, es decir, CUMPLE.
DF#3: t1[C] =/= t2[C] el determinante es distinto entre las tuplas. No hace falta mirar
el determinado. CUMPLE
DF#4: t1[E] = t2[E] el determinante tiene el mismo valor entre las tuplas.
t1[B] = t2[B] el determinado tiene el mismo valor entre las tuplas, es decir, CUMPLE.
SATISFACE
Ejercicio 2
R = (A, B, C, D, E, G, H, I)
DF = {A, B → C, H; C, D → B; B → G, A, E; H → D, I}
a. A+
Paso 1: A+ = {A}
Paso 2: Iteraciones
Iteración 1: Buscamos las DF tal que su determinante esté en el conjunto A+, pero
su determinado no. No existe ninguna.
No hay más iteraciones.
A+ = {A}
b. B+
Paso 1: B+ = {B}
Paso 2: Iteraciones
Iteración 1: Buscamos las DF tal que su determinante esté en el conjunto B+, pero
su determinado no. Existe una: B → G, A, E. Ahora hacemos unión entre el
determinado y el conjunto B+.
B+ = {B, G, A, E}
Iteración 2: Existe: A, B → C, H.
B+ = {B, G, A, E, C, H}
Iteración 3: Existe: H → D, I.
B+ = {B, G, A, E, C, H, D, I}
Iteración 4: No existe ninguna.
No hay más iteraciones.
B+ = {B, G, A, E, C, H, D, I}
{B} es superclave, ya que: B → esq(R), osea B+ = esq(R)
{B} es clave candidata ya que, además de ser superclave, también cumple con: no
existe un subconjunto estricto de atributos K de B (K ⊂ B) tal que
K → esq(R)
c. (CD)+
Paso 1: (CD)+ = {C, D}
Paso 2: Iteraciones
Iteración 1: Existe: C, D → B. Hacemos unión entre determinado y conjunto (CD)+.
(CD)+ = {C, D, B}
Iteración 2: Existe: B → G, A, E.
(CD)+ = {C, D, B, G, A, E}
Iteración 3: Existe: A, B → C, H.
(CD)+ = {C, D, B, G, A, E, H}
Iteración 4: Existe: H → D, I.
(CD)+ = {C, D, B, G, A, E, H, I}
Iteración 5: No existe ninguna.
No hay más iteraciones.
(CD)+ = {C, D, B, G, A, E, H, I}
{C, D} es superclave, ya que: C, D → esq(R), osea (CD)+ = esq(R)
d. (BEI)+
Paso 1: (BEI)+ = {B, E, I}
Paso 2: Iteraciones
Iteración 1: Existe: B → G, A, E
(BEI)+ = {B, E, I, G, A}
Iteración 2: Existe: A, B → C, H.
(BEI)+ = {B, E, I, G, A, C, H}
Iteración 3: Existe: H → D, I.
(BEI)+ = {B, E, I, G, A, C, H, D}
Iteración 4: No existe ninguna.
No hay más iteraciones.
(BEI)+ = {B, E, I, G, A, C, H, D}
{B, E, I} es superclave, ya que: B, E, I → esq(R), osea (BEI)+ = esq(R)
e. (HA)+
Paso 1: (HA)+ = {H, A}
Paso 2: Iteraciones
Iteración 1: Existe: H → D, I.
(HA)+ = {H, A, D, I}
Iteración 2: No existe ninguna.
No hay más iteraciones.
(HA)+ = {H, A, D, I}
f. (ABH)+
Paso 1: (ABH)+ = {A, B, H}
Paso 2: Iteraciones
Iteración 1: Existe: A, B → C, H; H → D, I; B → G, A, E.
(ABH)+ = {A, B, H, C, D, I, G, E}
Iteración 2: No existe ninguna.
No hay más iteraciones.
(ABH)+ = {A, B, H, C, D, I, G, E}
{A, B, H} es superclave, ya que: A, B, H → esq(R), osea (ABH)+ = esq(R)
Ejercicio 3
R = (A, B, C, D, E, F)
DF = {A → B, C; F, C → D; E → A}
a. Grafo de dependencias funcionales
b. (AF)+
(AF)+ = {A, F}
= {A, F, B, C}
= {A, F, B, C, D}
{A, F} NO es superclave, ya que (AF)+ =/= esq(R)
(EF)+
(EF)+ = {E, F}
= {E, F, A}
= {E, F, A, B, C}
= {E, F, A, B, C, D}
{E, F} SI es superclave, ya que (EF)+ = esq(R)
{E, F} SI es clave candidata ya que, además de ser superclave, también cumple
con: no existe un subconjunto estricto de atributos K de {E, F} (K ⊂ {E, F}) tal que
K → esq(R)
Ejercicio 4
a. Si A → B y B,C → D entonces A,C → D
Haciendo aumentación en la primera DF:
A, C → B, C
Sabemos que BC → D, por lo tanto por transitividad:
A, C → B, C → D
A, C → D - CORRECTO
b. Si A,B → C entonces A → C y B → C
t1 = <a1, b3, c4>
t2 = <a1, b1, c1>
t3 = <a2, b1, c3>
t4 = <a1, b1, c1>
A, B → C se cumple. Es decir, no existen dos tuplas (t y t’) tal que:
t[A] = t’[A] ^ t[B] = t’[B] ⇒ t[C] =/= t’[C]
En otras palabras, para toda tupla t y t’ se cumple:
t[A] = t’[A] ^ t[B] = t’[B] ⇒ t[C] = t’[C]
Pero A → C (1) y B → C (2) no son correctas, ya que no se cumple lo siguiente:
Para toda tupla t y t’:
(1) t[A] = t’[A] ⇒ t[C] = t’[C]
Contraejemplo:
t1 = <a1, b3, c4>
t2 = <a1, b1, c1>
(2) t[B] = t’[B] ⇒ t[C] = t’[C]
Contraejemplo:
t2 = <a1, b1, c1>
t3 = <a2, b1, c3>
A → C y B → C - INCORRECTO
Conclusión: es incorrecto hacer descomposición de determinantes. Solo es correcto
descomponer determinados.
Pero SI es correcto hacer unión de determinantes. Ej:
X → Y; Z → Y
Luego hacemos aumentación en cualquiera de las dos:
ZX → ZY
Aplicamos reflexividad:
ZY → Z
Finalmente, por transitividad:
ZX → ZY → Z → Y
ZX → Y
X → Y; Z → Y ⇒ ZX → Y
c. Si A,B → C y A,Z → C,D entonces A,B,Z → D
Haciendo aumentación en la segunda DF:
A, Z, B → C, D, B
Aplicando reflexividad en el determinado:
C, D, B → D (ya que D ⊆ CDB)
Por último nos queda:
A, Z, B → C, D, B → D
Por transitividad decimos que:
A, Z, B → D
A, B, Z → D - CORRECTO
Ejercicio 5
1. ANIMAL=(IdAnimal, NombreZoo, EspecieAnimal, Sexo, AñoNacim, PaísZool,
CiudadZoo, PaisOrigenAnimal)
Un animal tiene características propias y únicas:
IdAnimal → EspecieAnimal
IdAnimal → Sexo
IdAnimal → AñoNacim
IdAnimal → PaisOrigenAnimal
Un animal está en un único zoológico:
IdAnimal → NombreZoo
Aclarando que NombreZoo es único entre todos los Zoológicos
Un zoológico está en una ciudad y país específico:
NombreZoo → CiudadZoo
NombreZoo → PaisZool
Una ciudad pertenece a un único país:
CiudadZoo → PaisZool
Hacemos aditividad:
IdAnimal → EspecieAnimal, Sexo, AñoNacim, PaisOrigenAnimal, NombreZoo
NombreZoo → CiudadZoo, PaisZool
CiudadZoo → PaisZool
DF = {IdAnimal → EspecieAnimal, Sexo, AñoNacim, PaisOrigenAnimal, NombreZoo;
NombreZoo → CiudadZoo, PaisZool; CiudadZoo → PaisZool}
Esta instancia cumple con todas las DF:
t1 = <28, ZooTandil, Yacare, Macho, 2013, Argentina, Tandil, Argentina>
t2 = <124, ZooTandil, Boa, Hembra, 2016, Argentina, Tandil, Brasil>
Esta instancia no cumple con las DF:
t1 = <28, ZooTandil, Yacare, Macho, 2013, Argentina, Tandil, Argentina>
t2 = <55, ZooSol, Boa, Hembra, 2016, Argentina, S. de Chile, Brasil>
t3 = <56, ZooSol, Boa, Macho, 2017, Chile, S. de Chile, Brasil>
t4 = <28, ZooTandil, Yacare, Hembra, 2013, Argentina, Necochea, Argentina>
Un mismo animal está registrado como macho y hembra.
t1 = <28, ZooTandil, Yacare, Macho, 2013, Argentina, Tandil, Argentina>
t4 = <28, ZooTandil, Yacare, Hembra, 2013, Argentina, Necochea, Argentina>
Una misma ciudad pertenece a diferentes países.
t2 = <55, ZooSol, Boa, Hembra, 2016, Argentina, S. de Chile, Brasil>
t3 = <56, ZooSol, Boa, Macho, 2017, Chile, S. de Chile, Brasil>
Un zoológico pertenece a dos ciudades distintas.
t1 = <28, ZooTandil, Yacare, Macho, 2013, Argentina, Tandil, Argentina>
t4 = <28, ZooTandil, Yacare, Hembra, 2013, Argentina, Necochea, Argentina>
2. ACADEMIA=(LegajoInstructor, DNI_Instructor, Id_Curso, Nombre_Curso,
DNI_Alumno, NombreAlumno, emailAlumno, Cant_ClasexCurso)
Un instructor tiene un DNI y un Legajo:
LegajoInstructor → DNI_Instructor
DNI_Instructor → LegajoInstructor
Un curso tiene nombre y un cantidad de clases fija:
Id_Curso → NombreCurso, Cant_ClasesxCurso
Un alumno tiene sus datos propios:
DNI_Alumno → NombreAlumno, emailAlumno
Todo alumno para cada curso tiene un instructor:
DNI_Alumno, Id_Curso → LegajoInstructor
DF = {LegajoInstructor → DNI_Instructor; DNI_Instructor → LegajoInstructor;
Id_Curso → NombreCurso, Cant_ClasesxCurso; DNI_Alumno → NombreAlumno,
emailAlumno; DNI_Alumno, Id_Curso → LegajoInstructor}
Esta instancia cumple con todas las DF:
t1 = <1000, 200, 2, Algebra, 400, Leandro, lean@[Link], 8>
t2 = <1000, 200, 2, Algebra, 432, Azul, azul@[Link], 8>
t3 = <1400, 233, 3, Analisis Matematico, 432, Azul, azul@[Link], 10>
t4 = <1000, 200, 5, Ciencias de la Computacion, 451, Cristian, cris@[Link], 8>
t5 = <1350, 212, 3, Analisis Matematico, 395, Belen, belu@[Link], 10>
Esta instancia no cumple con las DF:
t1 = <1000, 200, 2, Algebra, 400, Leandro, lean@[Link], 8>
t2 = <1000, 200, 2, Algebra Lineal, 432, Azul, azul@[Link], 8>
t3 = <1400, 233, 3, Analisis Matematico, 432, Celeste, cel@[Link], 10>
t4 = <1230, 200, 2, Algebra, 400, Leandro, lean@[Link], 8>
t5 = <1350, 212, 3, Analisis Matematico, 395, Belen, belu@[Link], 9>
Para un curso y un alumno hay dos instructores distintos asignados.
Además para un mismo DNI hay dos Legajos distintos asociados.
t1 = <1000, 200, 2, Algebra, 400, Leandro, lean@[Link], 8>
t4 = <1230, 200, 2, Algebra, 400, Leandro, lean@[Link], 8>
Para un mismo curso se le asigno distintos nombres y cantidad de clases.
t1 = <1000, 200, 2, Algebra, 400, Leandro, lean@[Link], 8>
t2 = <1000, 200, 2, Algebra Lineal, 432, Azul, azul@[Link], 8>
t3 = <1400, 233, 3, Analisis Matematico, 432, Celeste, cel@[Link], 10>
t5 = <1350, 212, 3, Analisis Matematico, 395, Belen, belu@[Link], 9>
Para un DNI de alumno hay informacion que difiere.
t2 = <1000, 200, 2, Algebra Lineal, 432, Azul, azul@[Link], 8>
t3 = <1400, 233, 3, Analisis Matematico, 432, Celeste, cel@[Link], 10>
Ejercicio 6
a. Grafo de dependencias funcionales
1. R = (L, U, V, X, Y, Z)
DF = {XY → Z; Z → U; XY → V; X → L}
2. R = (M,N,P,Q,S,T)
DF = { M,N→P,Q,S,T; T→Q; M→P; Q→S}
b. Claves de las relaciones
1. Claves = {<X, Y>}
2. Claves = {<M, N>}
Las claves las obtuve sumando los atributos que no están implicados/determinados
(no tienen flechas de llegada).
De todas maneras, el procedimiento consta de más pasos. Se explica en el libro
“Diseño de bases de datos relacionales; de Adoración de Miguel Castaño, Mario
Gerardo Piattini Velthuis, Esperanza Marcos Martínez” Pag. 140. Titulo: “Obtención
de las claves candidatas de un esquema”.
c. Normalización:
1. R = (L, U, V, X, Y, Z)
DF = {XY → Z; Z → U; XY → V; X → L}
Nuestro conjunto de dependencias es minimal.
Claves = {<X, Y>} (solo una en este caso)
ATP = {X, Y}
ATNP = {L, U, V, Z}
1FN
En un principio, el esquema de relación está en 1FN ya que sus atributos son
simples/atómicos (no compuestos).
2FN
No se encuentra en 2FN, debido a que L depende parcialmente de la clave
(solo depende de X).
Transformamos la relación en:
R1 = {X, Y, V, Z, U}
DF1 = {XY → Z; Z → U; XY → V}
Claves1 = {<X, Y>}
R2 = {X, L}
DF2 = {X → L}
Claves2 = {<X>}
R1 y R2 están en 2FN.
Transformación realizada sin pérdidas.
3FN
R2 está en 3FN ya que los atributos no-clave dependen no-transitivamente
de la clave. Por lo tanto, queda igual:
R2 = {X, L}
DF2 = {X → L}
Claves2 = {<X>}
R1 no está en 3FN, ya que el atributo no-clave U depende transitivamente de
la clave <X, Y>. La transformación sería la siguiente:
R11 = {X, Y, V, Z}
DF11 = {XY → Z; XY → V}
Claves11 = {<X, Y>}
R12 = {Z, U}
DF12 = {Z → U}
Claves12 = {<Z>}
R2, R11 y R12 están en 3FN.
Transformación realizada sin pérdidas.
FNBC
R2, R11 y R12 están en FNBC, ya que cada determinante en el conjunto
minimal de dependencias funcionales es una clave candidata en la relación
correspondiente.
2. R = (M,N,P,Q,S,T)
DF = { M,N→P,Q,S,T; T→Q; M→P; Q→S}
Claves = {<M, N>}
El DF no es minimal, ya que existe una dependencia que no es elemental.
Más específicamente tiene más de un atributo en su determinado:
M,N→P,Q,S,T
Para eso lo descomponemos:
M, N → P
M, N → Q
M, N → S
M, N → T
El atributo P no tiene dependencia funcional plena/completa, ya que depende
de M, N y a su vez depende de M (M es un subconjunto de M, N). Por lo
tanto podemos decir que la dependencia M, N → P no es plena.
Otra manera de comprobar que esa dependencia no es necesaria:
Se puede decir que M, N → P es derivable a través de las demás
dependencias (redundancia). Si aplicamos aumentación en M → P:
M, N → P, N
Luego reflexividad y transitividad:
M, N → P, N → P ⇒ M, N → P
Por lo tanto, podemos desechar M, N → P
También tenemos redundancia en otras dependencias:
M, N → S y M, N → Q
Ya que aplicando transitividad:
M, N → T → Q → S
Podemos obtener las dependencias marcadas con rojo.
Las desechamos.
Nos queda:
R = (M,N,P,Q,S,T)
DF = {M,N → T; T→Q; M→P; Q→S}
Claves = {<M, N>}
1FN
En un principio, el esquema de relación está en 1FN ya que sus atributos son
simples/atómicos (no compuestos).
2FN
La relación R no está en 2FN, ya que el atributo P no depende plenamente
de la clave candidata.
Transformando la relación:
R1 = (M, P)
DF1 = {M → P}
Claves1 = {<M>}
R2 = (M,N,Q,S,T)
DF2 = {M,N → T; T→Q; Q→S}
Claves2 = {<M, N>}
R1 y R2 están en 2FN.
Transformación realizada sin pérdidas.
3FN
R2 no está en 3FN ya que existen atributos no principales que dependen
plenamente de las claves pero usando transitividad. En otras palabras, hay
atributos no principales que dependen de atributos no principales.
Transformando R2:
R21 = (S, Q)
DF21 = {Q → S}
Claves21 = {<Q>}
R22 = (M, N, T, Q)
DF22 = {M, N → T; T → Q}
Claves22 = {<M, N>}
R21 está en 3FN, pero R22 no.
Transformando R22:
R221 = (Q, T)
DF221 = {T → Q}
Claves221 = {<T>}
R222 = (M, N, T)
DF222 = {M, N → T}
Claves222 = {<M, N>}
R221 y R222 están en 3FN.
Transformación realizada sin pérdidas.
FNBC
Todas las proyecciones están en FNBC (R1, R21, R221, R222).
Ejercicio 7
Enunciado A
En un principio identifiquemos las dependencias funcionales:
“Los representantes tienen un código (CR) y un conjunto de atributos (AR). Análogamente
las áreas tienen CA y AA y los productos CP y AP.”
CR → AR
CA → AA
CP → AP
“En cada área hay varios representantes y cada representante trabaja en varias áreas.”
CA ↛ CR
CR ↛ CA
“En todas las áreas se venden todos los productos.”
CA ↛ CP
CP ↛ CA
“Un representante puede vender varios productos y cada producto se vende por varios
representantes.”
CR ↛ CP
CP ↛ CR
“Nunca dos representantes venden el mismo producto en la misma área.”
CA, CP → CR
“Todo representante vende el mismo conjunto de productos en cada área donde trabaja.”
En este caso podemos suponer que tenemos un conjunto de productos, set de productos
(SP) que es determinado por el representante.
CR → SP
Vamos a suponer también que un producto puede pertenecer a varios sets/conjuntos.
CP ↛ SP
Nos queda de la siguiente manera:
R = (CR, AR, CP, AP, CA, AA, SP)
DF = {CP → AP; CR → AR; CA → AA; CA, CP → CR; CR → SP}
Claves = {<CA, CP>}
El conjunto de dependencias funcionales es minimal.
1FN
La relación se encuentra en 1FN ya que podemos suponer que sus atributos son atómicos.
2FN
La relación no se encuentra en 2FN ya que los atributos no principales AA y AP son
determinados parcialmente por la clave.
Transformamos la relación:
R1 = {CA, AA}
DF1 = {CA → AA}
Claves = {<CA>}
R2 = {CP, AP}
DF2 = {CP → AP}
Claves = {<CP>}
R3 = {CA, CP, CR, AR, SP}
DF3 = {CA, CP → CR; CR → AR; CR → SP}
Claves = {<CA, CP>}
Las relaciones R1, R2 y R3 están en 2FN.
Transformación realizada sin pérdidas.
3FN
La relación R3 no está en 3FN ya que los atributos SP y AR son determinados
transitivamente por la clave.
Transformamos la relación:
R31 = (CR, SP, AR)
DF31 = {CR → SP; CR → AR}
Claves = {<CR>}
R32 = (CA, CP, CR)
DF32 = {CA, CP → CR}
Claves = {<CA, CP>}
Las relaciones R31 y R32 están en 3FN.
Transformación realizada sin pérdidas.
FNBC
Todas las relaciones están en FNBC ya que todos sus determinantes son claves de sus
relaciones correspondientes.
Enunciado B
Identifiquemos las dependencias funcionales a partir del texto:
“Un profesor se identifica por un código de profesor (CP) y todos los profesores tienen un
nombre (NP). Un profesor puede tener un título(T) y trabajar en un único proyecto(P)”
CP → NP
CP → T
CP → P
“Cada asignatura (A) tiene un único profesor como responsable, si bien un mismo profesor
puede ser responsable de más de una asignatura. Las asignaturas se dividen en una o más
comisiones (C).”
A → CP
CP ↛ A
A↛ C
C → A (Una comisión pertenece a una única asignatura)
“Todo alumno (AL), en cada asignatura pertenece a una única comisión.”
AL, A → C
“Cada profesor pertenece a un único departamento (D). Asimismo, toda asignatura está
ligada a un único departamento, el del profesor responsable de la misma.”
CP → D
A→D
Nos quedaría:
R = (CP, NP, T, A, C, AL, D)
DF = {CP → NP; CP → T; CP → P; A → CP; C → A; AL, A → C; CP → D; A → D}
Nuestro conjunto DF no es minimal ya que existe una dependencia que puede derivarse de
las demás. Es decir, si quitamos esa dependencia el conjunto es equivalente.
A→D
Utilizando otras dos dependencias y la propiedad de transitividad podemos derivarla:
A → CP
CP → D
A → CP → D ⇒ A → D
Podemos quitarla:
R = (CP, NP, T, A, C, AL, D)
DF = {CP → NP; CP → T; CP → P; A → CP; C → A; AL, A → C; CP → D}
