FUNDAMENTOS DE BASES DE DATOS
SEGUNDO PARCIAL 2001
NOMBRE: _______________________________________________________
CEDULA DE IDENTIDAD: _________________________________________
CANTIDAD DE HOJAS ADICIONALES: _____________________________
Presentar la resolución del parcial:
• Con las hojas adicionales numeradas y escritas de un solo lado.
• Con las hojas escritas a lápiz.
• Poner cédula de identidad y nombre en cada hoja (incluidas estas).
• Escrito en forma prolija.
• Las opciones elegidas se deben marcar poniendo el identificador de la opción en un
círculo claramente identificado.
• Poner la cantidad de hojas adicionales entregadas en la primer hoja.
• Debe entregar la letra.
Ejercicio 1
La STC es una asociación que nuclea a “tiempos compartidos” a nivel mundial y lo ha
contratado a Ud. para que trabaje con la base de datos de la asociación. El área informática de
la empresa se había empezado a desarrollar pero por diferentes motivos quedó sin personal y
Ud. va descubriendo la información de a poco. Por ejemplo, encuentra que empleados que ya
se fueron de la empresa dejaron un relevamiento pero fraccionado:
“Un tiempo compartido, es una sociedad que tiene diversos complejos vacacionales
distribuidos en varias partes del mundo con una administración común. Estas sociedades están
compuestas por socios que compraron al menos una semana al año en determinada
temporada (baja, media o alta) en determinado complejo de los administrados por la sociedad.
Estas semanas que tiene cada socio, son móviles (la coordina con una determinada
anticipación) dentro de la temporada.
Cada tiempo compartido, tiene un código que lo identifica dentro de la asociación (C_TC).
De cada complejo vacacional se conoce además del tiempo compartido que lo administra, su
dirección (D_C), un nombre (N_C), un conjunto de teléfonos administrativos (Tel_C) ubicados
físicamente en el complejo y un código que lo identifica dentro del tiempo compartido (C_C).
Se sabe que hay complejos de diferentes tiempos compartidos que pueden tener el mismo
código.
Se sabe además que un mismo nombre puede ser usado por diferentes complejos y que
incluso, pueden existir diferentes complejos con la misma dirección pero nunca con un teléfono
es compartido entre varios complejos. Cada complejo dispone de apartamentos de
determinadas capacidades (CapAP) (2, 4 o 6) y para cada capacidad se conoce cuantos
apartamentos tiene el complejo (CantAP_C). “
1
a) Marque aquellas dependencias funcionales que se cumplen de acuerdo a la
realidad anterior:
a. C_C→ D_C, N_C f. C_C,C_TC→
CapAP,CantAP_C
b. N_C→ C_C
g. C_C, C_TC, CapAP→
c. C_C, C_TC→ D_C,N_C CantAP
d. C_C→Tel_C h. No hay ninguna
e. Tel_C→ C_C, C_TC dependencia funcional
Posteriormente, Ud. encuentra la siguiente información sobre la realidad de STC:
“Además para cada complejo, se conoce qué temporadas maneja (Temp) dado que hay
complejos (p.e. en el caribe) que no tienen temporada baja o incluso puede haber algunos que
les falte alguna otra temporada. Para cada complejo y cada temporada se conoce la fecha de
inicio y una fecha de fin (FIT_C, FFT_C) de esa temporada. No hay temporadas superpuestas
en el mismo complejo.
De cada socio, se conoce un código asignado por la STC (y que por lo tanto, lo identifica
independientemente de cualquier tiempo compartido) (C_S). Además se conoce su dirección
actual (D_S), un teléfono de contacto (Tel_S), las temporadas en las que el socio compro
alguna semana en algún complejo determinado, las capacidades de apartamento que compró
y para cada temporada y capacidad, la cantidad de semanas que compró (CantS_S). Mediante
una análisis de los registros manuales de inscripción, se constató que hay socios diferentes con
el mismo domicilio y teléfono. De la misma forma se constató que hay varios socios que
compraron varias semanas en temporadas diferentes en el mismo complejo e incluso en
diferentes complejos de distintos tiempos compartidos.”
b) Marque aquellas dependencias funcionales que se cumplen de acuerdo a la
realidad anterior:
a. C_C→Temp h. C_C,C_TC,Temp→
FIT_C,FFT_C
b. C_C,C_TC→Temp
i. FIT_C,FFT_C→ C_C,Temp
c. C_S → D_S,Tel_S
j. C_S→C_C,C_TC,Temp
d. C_S→Temp
k. C_S,C_C,C_TC,Temp, CapAP→
e. FIT_C,FFT_C,C_C→ CantS_S
Temp
l. No hay ninguna dependencia
f. FIT_C,FFT_C,C_C, funcional
C_TC→ Temp
g. C_S,C_C,Temp→CapAP
Varias semanas después, Ud. encuentra aún más información:
“Los socios hacen reservas para alguno de los complejos administrados por STC. Estas
reservas pueden ser incluso en complejos en los que el socio no es propietario. De cada
reserva en un complejo, se conoce el complejo en el cual se hace la reserva, el socio que hace
la reserva, la temporada (con respecto a ese complejo) para la cual se hace la reserva, la
capacidad de apartamento para la que se hace la reserva, un entero que identifica la semana
dentro de la temporada (ST_R) y un identificador de reserva (C_R) que lo asigna el complejo.
Un mismo identificador puede ser usado para diferentes reservas por diferentes complejos.
Cada reserva es válida para una única semana. Por este motivo, si un socio quiere reservar
más de un apartamento (aunque sea con la misma capacidad) en una misma semana o más de
una semana determinada, entonces se debe asignar un nuevo código de reserva.”
2
A partir de la ultima informacion recibida se deduce la siguiente dependencia functional.
C_R,C_C,C_TC→ C_S,Temp,ST_R,CapAp
Asuma que las anteriores son todas las dependencias que se cumplen en la realidad.
De esta forma, y para que tenga una referencia de trabajo, la tabla universal de esta realidad
tiene los siguientes atributos:
R(C_C, C_TC, D_C, N_C, Tel_C, CapAP, CantAP_C, Temp, FIT_C, FFT_C, C_S, D_S,
Tel_S, CantS_S, C_R, ST_R)
Sugerencia: Transcriba con cuidado todas las dependencias funcionales que encontró en la
letra en el siguiente espacio.
c) Indique cuáles de las siguientes dependencias multivaluadas se cumplen en la
realidad anterior.
a. C_C,C_TC→→C_S d. C_C,C_TC→→ C_S|Tel_C
b. C_C,C_TC→→Tel_C e. Ninguna de las anteriores.
c. C_S→→ Tel_C|C_C,C_TC
3
d) Debajo de la primer columna escriba los atributos que no pertencen a ninguna
clave y debajo de la segunda los que deberían pertenecer a todas las claves.
Atts. en ninguna clave. Atts. en todas las claves
__________, __________, __________, __________,
__________, __________, __________, __________,
__________, __________, __________, __________,
__________, __________, __________, __________,
__________, __________ __________, __________
e) Complete los blancos.
a. Coloqué esos atributos en la primer columna porque
________________________________________________________________
________________________________________________________________
b. Coloqué esos atributos en la segunda columna porque
________________________________________________________________
________________________________________________________________
f) Indique cuántas claves hay de 3 atributos.
a. 1. c. Más de 2.
b. 2. d. Ninguna.
g) Explique porqué respondió eso en la parte anterior.
_________________________________________________________________________
_________________________________________________________________________
h) Escriba todas las claves.
__________________________________, __________________________________,
__________________________________, __________________________________,
i) Explique por qué esas son todas las claves.
_________________________________________________________________________
_________________________________________________________________________
4
Considere las siguientes tablas sobre los atributos anteriores.
Comp(C_C,C_TC,D_C,N_C,Tel_C,CapAP,CantAP_C,Temp,FIT_C, FFT_C)
Socios(C_S,D_S,Tel_S,C_C,C_TC,Temp,CapAP,CantS_S)
Reservas(C_R,C_C,C_TC,C_S,Temp,CapAP,ST_R)
j) Proyecte las dependencias sobre estas tablas.
Comp(C_C,C_TC,D_C,N_C,Tel_C,CapAP,CantAP_C,Temp,FIT_C, FFT_C)
Socios(C_S,D_S,Tel_S,C_C,C_TC,Temp,CapAP,CantS_S)
Reservas(C_R,C_C,C_TC,C_S,Temp,CapAP,ST_R)
5
k) Comp y Socios, tienen join sin pérdida?
SI NO
l) Justifique su respuesta anterior.
m) Determine en qué forma normal está cada tabla. Justifique sus afirmaciones.
Comp(C_C,C_TC,D_C,N_C,Tel_C,CapAP,CantAP_C,Temp)
_________________________________________________________________________
_________________________________________________________________________
_________________________________________________________________________
Socios(C_S,D_S,Tel_S,C_C,C_TC,Temp,CapAP)
_________________________________________________________________________
_________________________________________________________________________
_________________________________________________________________________
Reservas(C_R,C_C,C_TC,C_S,Temp,CapAP,ST_R)
_________________________________________________________________________
_________________________________________________________________________
_________________________________________________________________________
n) Aplique el algoritmo para llevar a 3NF a la tabla Comp.
o) Aplique el algoritmo para llevar a 4NF a la tabla Socios.
6
Ejercicio 2
Sea el siguiente esquema relacional:
Empleado (cod-emp, cod-depto, salario, hobby)
Departamento (cod-depto, nom-depto, piso, telefono)
Finanzas (cod-depto, presupuesto, ventas, gastos)
Sea la siguiente consulta sobre dicho esquema:
SELECT [Link]-depto, [Link]
FROM Empleado E, Departamento D, Finanzas F
WHERE [Link]-depto = D. Cod-depto AND [Link]-depto = [Link]-depto AND [Link] = 1
AND [Link] = 59000 AND [Link] = ‘pesca’
a) Construir un plan lógico mejorado para la consulta, utilizando las heurísticas y teniendo
en cuenta los tamaños.
b) Construir un plan físico para la consulta que le parezca adecuado y dar la estimación
de su costo. (Sugerencia: los valores que le queden con cifras decimales, redondearlos
hacia arriba)
DATOS:
EMPLEADO DEPARTAMENTO FINANZAS EMP |><|
DEPTO
Cantidad tuplas 25000 500 500
Indices cod-depto cod-depto
primarios (niveles: 1) (niveles: 1)
Indices cod-depto y salario piso
secundarios (niveles: 3) (niveles: 3)
(B+)
Cantidad de 50 30 20
tuplas por
bloque
Observaciones - Salarios: entre Hay 2 pisos en la
10000 y 60000 compañía
(múltiplos de 1000)
- Hobbies: 20 ≠s
- Los empleados se
distrib.
uniformemente en
los deptos.
7
Fórmulas de cálculo de costo:
Selección (R) Búsqueda lineal b
Búsqueda binaria log2b + s/fblR - 1
Indice primario x+1
Indice secundario (B+) x + |R| * s
Join (R,S) Nested Loop (ciclo anidado) sin utilizar bR + bR * bS
índices
Nested Loop (ciclo anidado) utilizando bR + |R| * (x + s)
índice secundario para recuperar tuplas
que matchean
Nested Loop (ciclo anidado) utilizando bR + |R| * (x + 1)
índice primario para recuperar tuplas que
matchean
Escribir Selección (R) (|R| * s) / fblR
resultados en
disco
Join (R,S) (js * |R| * |S|)/ fblRS
Selectividad Selección (atrib. A) 1 / V(A,R)
Join (atrib. A) 1/ Max (V(A,R),
V(A,S))
Notación: b – cantidad de bloques
fbl – factor de bloqueo
x – cantidad de niveles del índice
|R| - cantidad de tuplas de R
s – selectividad de la selección
js – selectividad del join
V(A,R) - cantidad de valores distintos del atributo A en R
Ejercicio 3
Considere las siguientes transacciones:
T1: r1(X) w1(X) r1(Y) c1
T2: r2(X) w2(X) r2(Y) w2(Y) c2
a) Dada la siguiente historia de T1 y T2:
H: r1(X) r2(X) w2(X) w1(X) r2(Y) w2(Y) c2 r1(Y) c1
Decir si H es serializable, recuperable, si evita abortos en cascada y si es estricta. En cada
caso justificar.
b) Dar una historia con bloqueos y desbloqueos de lectura y escritura donde se siga el
protocolo 2PL. Decir si es serializable justificando.
c) Si es posible, dar una historia con bloqueos y desbloqueos de lectura y escritura donde
no se siga el protocolo 2PL y que sea serializable.
8
Ejercicio 4
a) Indique que procedimiento de recuperación se seguiría en la siguiente historia en caso
de falla siguiendo una estrategia de manejo de logging de actualización inmediata.
H: r1(x) w1(x) r2(y) w2(y) r2(x) w2(x) r1(y) w1(y) r1(z) w1(z) c1 r2(z) w2(z) <falla>
b) Indique que sucede si ocurre una falla durante la recuperación. Justifique.