Final de práctica — Bases de Datos

Temas: todo el curso, con énfasis en las partes 3 y 4 (semanas 9 a 16) · Duración: 3 horas

Este es un examen de práctica con el formato del final. Sirve para medir cuánto tiempo les toma cada tipo de pregunta: resuélvanlo en la computadora, con el contenedor del curso, sin internet y con el reloj corriendo. El formato general está en exams/README.md.

Indicaciones

• Muestren los cálculos: un número sin el procedimiento no basta. Si arrastran un error de un inciso al siguiente, sigan con su número.
• En SQL importa la idea: un error menor de sintaxis no la invalida.
• Costos en transferencias de bloques, como en el curso, salvo que la pregunta pida seeks o tiempo. No cuenten la escritura del resultado final.
• B+ trees con la convención de Silberschatz: n es el número máximo de punteros de un nodo; una hoja guarda a lo más n − 1 claves. Al dividir una hoja con n claves, las primeras ⌈n/2⌉ se quedan y la primera clave de la hoja nueva se copia al padre. Al dividir un nodo interno con n claves, las primeras ⌊n/2⌋ se quedan, la siguiente sube al padre y el resto pasa al nodo nuevo.
• Las preguntas de PostgreSQL se refieren a PostgreSQL 18.

Parte A — SQL y diseño

Pregunta 1 — NULL, joins externos y normalización

Una empresa de mensajería guarda a sus mensajeros y sus entregas. Una entrega sin mensajero asignado tiene courier_id en NULL; una entrega cuyo cobro no se registró tiene fee en NULL.

CREATE TABLE courier (
  courier_id integer PRIMARY KEY,
  name       text NOT NULL,
  zone       text
);

CREATE TABLE delivery (
  delivery_id integer PRIMARY KEY,
  courier_id  integer REFERENCES courier,
  kg          numeric(5, 1) NOT NULL,
  fee         numeric(6, 2)
);

 courier_id | name  | zone
------------+-------+-------
          1 | Ana   | Lima
          2 | Beto  | Lima
          3 | Carla | Cusco
          4 | Dante | ∅

 delivery_id | courier_id |  kg  |  fee
-------------+------------+------+-------
         100 |          1 |  2.0 | 15.00
         101 |          1 |  5.5 |     ∅
         102 |          2 |  1.0 | 10.00
         103 |          3 |  8.0 | 30.00
         104 |          ∅ |  3.0 | 12.00
         105 |          3 |  2.5 |     ∅

a) Escriban el resultado de cada consulta y justifiquen cada valor en una línea.

-- (i)
SELECT count(*) AS n, count(fee) AS with_fee, count(DISTINCT courier_id) AS couriers,
  sum(fee), round(avg(fee), 2) AS avg
FROM delivery;

-- (ii)
SELECT name FROM courier
WHERE courier_id NOT IN (SELECT courier_id FROM delivery);

-- (iii) las dos consultas
SELECT c.name, count(d.delivery_id) AS n
FROM courier c LEFT JOIN delivery d
  ON d.courier_id = c.courier_id AND d.fee IS NOT NULL
GROUP BY c.name ORDER BY c.name;

SELECT c.name, count(d.delivery_id) AS n
FROM courier c LEFT JOIN delivery d ON d.courier_id = c.courier_id
WHERE d.fee IS NOT NULL
GROUP BY c.name ORDER BY c.name;

-- (iv)
SELECT zone, count(*) AS n, count(zone) AS z
FROM courier GROUP BY zone ORDER BY zone NULLS LAST;

Para (ii), escriban además una consulta que devuelva lo que probablemente se quería: los mensajeros sin entregas.

b) Sea R = (A, B, C, D, E) con

F = { A → B, BC → D, D → A, E → C }

Calculen A⁺ y (BC)⁺. Encuentren todas las claves candidatas y justifiquen por qué E está en todas. ¿Está R en BCNF? ¿Y en 3NF? Justifiquen con cada dependencia de F. Descompongan R en BCNF con el algoritmo del curso y digan si la descomposición preserva las dependencias.

Parte B — Almacenamiento e índices

Pregunta 2 — B+ tree

a) En un B+ tree vacío con n = 4 se insertan, en este orden, las claves

10, 20, 30, 40, 50, 60, 70, 80

y después

90, 100, 35, 36.

Dibujen el árbol después de insertar 80 y al final. Indiquen en qué inserciones hay un split de hoja, en cuáles un split de un nodo interno y en cuáles crece la altura. ¿Cuántos splits hubo en total? ¿Qué tiene de malo, para la ocupación de las hojas, insertar las claves en orden creciente?

b) La tabla de envíos de una empresa grande tiene 5·10⁷ filas y un índice B+ tree sobre tracking_code, de 12 bytes. Cada entrada de un nodo es una clave y un puntero de 6 bytes, y cada página es de 8 KiB con 96 bytes de encabezado. Calculen el fan-out máximo y la altura del árbol en el mejor caso (nodos llenos) y en el peor caso (nodos a la mitad). ¿Cuántas páginas se leen para encontrar un envío por su código, contando la del heap file? ¿Y en la práctica, si la raíz y el segundo nivel están en el buffer pool?

Parte C — Procesamiento y optimización de consultas

Pregunta 3 — Ordenamiento externo

Una relación ocupa b = 120 000 páginas y se ordena con external merge sort.

a) Con M = 61 páginas de memoria: ¿cuántos runs genera la primera fase? ¿Cuántas pasadas de fusión hacen falta? ¿Cuántas transferencias de bloques en total? ¿Cuánto tarda, con t_T = 0,1 ms y sin contar los seeks?

b) Repitan con M = 31.

c) ¿Cuál es la menor M con la que basta una sola pasada de fusión? Muestren la desigualdad que usan.

Pregunta 4 — Costo de joins

Se quiere calcular driver ⋈ trip sobre driver.driver_id = trip.driver_id. driver_id es la clave de driver y una clave foránea en trip.

Hay M = 52 páginas de memoria.

a) Costo de block nested loop join en transferencias y en seeks, con driver afuera y con trip afuera. ¿Cuál conviene?

b) Costo de hash join con driver como relación de construcción, sin particionamiento recursivo. ¿Cuántas particiones usan? ¿Qué condición debe cumplir M para no necesitar particionamiento recursivo, y se cumple?

c) Hay un B+ tree secundario sobre trip(driver_id) de altura 3, y cada conductor tiene en promedio el mismo número de viajes. Costo de index nested loop join con driver afuera, suponiendo que cada viaje encontrado está en una página distinta. Repitan si la consulta tiene además WHERE driver.base = 'Arequipa' y solo 100 conductores cumplen esa condición.

d) Costo de merge join si hay que ordenar las dos relaciones (escribiendo cada salida ordenada a disco y leyéndola después en la fusión). Ordenen los cuatro algoritmos del más barato al más caro para la consulta sin filtro. ¿Cuál elegirían con el filtro de (c)?

Pregunta 5 — Estimaciones y planes

a) package tiene 100 000 filas. Su histograma equi-depth de 10 buckets sobre weight_kg tiene estos límites (cada bucket tiene el 10 % de las filas, y dentro de un bucket se supone distribución uniforme):

0,2 · 0,8 · 1,5 · 2,5 · 4 · 6 · 9 · 13 · 20 · 35 · 80

Estimen cuántas filas devuelven weight_kg < 5 y weight_kg BETWEEN 10 AND 25. La columna status tiene 'delivered' con frecuencia 0,9 en la lista de valores más comunes: estimen weight_kg < 5 AND status = 'delivered' y digan qué supuesto usan. ¿Cuánto daría la primera estimación si, en vez del histograma, se supusiera distribución uniforme entre el mínimo (0,2) y el máximo (80)? ¿Por qué el histograma equi-depth es mejor aquí?

b) Este plan es real, de la base de Chasqui (12 000 envíos, 1800 clientes), después de ANALYZE:

EXPLAIN (ANALYZE, TIMING OFF, SUMMARY OFF, BUFFERS OFF)
SELECT c.city, count(*)
FROM shipment s JOIN customer c ON c.customer_id = s.sender_id
WHERE s.status = 'registered' AND s.delivered_at IS NULL
GROUP BY c.city;

                                                     QUERY PLAN
---------------------------------------------------------------------------------------------------------------------
 GroupAggregate  (cost=358.56..359.10 rows=26 width=15) (actual rows=25.00 loops=1)
   Group Key: c.city
   ->  Sort  (cost=358.56..358.65 rows=37 width=7) (actual rows=500.00 loops=1)
         Sort Key: c.city
         Sort Method: quicksort  Memory: 25kB
         ->  Hash Join  (cost=59.50..357.60 rows=37 width=7) (actual rows=500.00 loops=1)
               Hash Cond: (s.sender_id = c.customer_id)
               ->  Seq Scan on shipment s  (cost=0.00..298.00 rows=37 width=4) (actual rows=500.00 loops=1)
                     Filter: ((delivered_at IS NULL) AND (status = 'registered'::text))
                     Rows Removed by Filter: 11500
               ->  Hash  (cost=37.00..37.00 rows=1800 width=11) (actual rows=1800.00 loops=1)
                     Buckets: 2048  Batches: 1  Memory Usage: 97kB
                     ->  Seq Scan on customer c  (cost=0.00..37.00 rows=1800 width=11) (actual rows=1800.00 loops=1)

En pg_stats, status = 'registered' tiene frecuencia 0,041666668 y delivered_at tiene null_frac = 0,07375.

• ¿Qué algoritmo de join usa? ¿Cuál es la relación de construcción y cuál la de prueba? ¿Por qué hay un Sort antes de agrupar?
• Calculen a mano la estimación rows=37 del Seq Scan on shipment. ¿Por qué la cifra real es 500? ¿Qué supuesto del estimador falla y por qué falla con estas dos columnas?
• Den un ejemplo de cómo un error así podría llevar a un plan malo en una consulta con más joins. ¿Qué comando de PostgreSQL le enseña al planificador la relación entre las dos columnas?

Parte D — Transacciones, concurrencia y recuperación

Pregunta 6 — Serializabilidad y recuperabilidad

S1 = r1(A) r2(B) w2(A) r3(C) r1(C) w3(B) w1(C) c2 r3(A) c3 c1
S2 = r1(A) w1(A) r2(B) r3(A) w3(C) c3 r2(C) w2(B) c2 w1(D) c1

a) Para cada schedule, listen los pares de operaciones en conflicto, dibujen el grafo de precedencia y digan si es conflict serializable. Si lo es, den todos los órdenes seriales equivalentes.

b) Para cada schedule, ¿es recuperable? ¿Es cascadeless? Justifiquen con las lecturas que hace cada transacción de datos escritos por otra.

c) Uno de los dos es serializable pero no recuperable. Expliquen con un ejemplo concreto qué podría salir mal si la transacción que escribió el dato abortara en lugar de hacer commit al final.

Pregunta 7 — Strict 2PL y deadlocks

Tres transacciones con strict 2PL (locks S y X; un lock S se puede subir a X si nadie más tiene S sobre el ítem) hacen estos pedidos, en este orden:

a) Sin prevención de deadlocks: digan qué pedidos se conceden y cuáles esperan, y a quién. Dibujen el waits-for graph después del paso 7. ¿Hay deadlock? ¿Qué víctima elegirían y qué pasa después?

b) Los timestamps son T1 = 10, T2 = 20 y T3 = 30 (T1 es la más antigua). Repitan el ejercicio con wait-die y con wound-wait: en cada paso, digan si la transacción espera, muere o hiere a otra, y qué locks se liberan. Supongan que una transacción abortada no vuelve a empezar durante el ejercicio. ¿Con qué timestamp se reinicia después, y por qué?

Pregunta 8 — Niveles de aislamiento en PostgreSQL

La tabla stock(item, qty) tiene las filas ('caja', 10) y ('sobre', 3). Dos sesiones, A y B, ejecutan esto en el orden de la tabla. En los pasos 4 y 7, la aplicación calcula el valor nuevo con lo que leyó en los pasos 1 y 2 (10 − 3 y 10 − 4) y lo manda como un número.

a) Si las dos sesiones usan READ COMMITTED, ¿qué devuelve cada SELECT de B y cuál es el qty final de la caja? Repitan con REPEATABLE READ. Nombren cada anomalía que aparece (o que se evita) en los pasos 6 y 7.

b) ¿Qué tendría que hacer la aplicación cuando recibe el error del paso 7? Den dos maneras de escribir el paso 7 para que READ COMMITTED no pierda la actualización de A.

Pregunta 9 — Recuperación con ARIES

El log, en el momento de la caída:

LSN  registro                                              prevLSN
10   T1 update P1                                          –
20   T2 update P2                                          –
30   T1 update P3                                          10
40   begin_checkpoint
50   end_checkpoint  TT = {T1: 30, T2: 20}  DPT = {P1: 10, P2: 20}
60   T2 update P3                                          20
70   T3 update P4                                          –
80   T1 commit                                             30
90   T2 update P1                                          60
100  T1 end                                                80
110  T3 update P2                                          70
---- caída ----
En disco: pageLSN(P1) = 10, pageLSN(P2) = 0, pageLSN(P3) = 60, pageLSN(P4) = 0

a) Analysis: den la transaction table (estado y lastLSN) y la dirty page table (recLSN) al final de la fase, y el LSN donde empieza el redo. ¿Por qué P3 no estaba en la DPT del checkpoint?

b) Redo: para cada registro desde el inicio del redo, digan si se rehace o se salta, y si para decidirlo hace falta leer la página.

c) Undo: escriban los registros que se agregan al log (CLR con su undoNextLSN, y los end), con LSN 120, 130, … en el orden en que se escriben. Usen la convención del curso (sin registros abort al final de analysis).

d) El sistema vuelve a caer justo después de escribir el CLR 130. ¿Qué cambia en el segundo arranque? ¿Por qué el update 110 no se deshace dos veces?

Parte E — Preguntas cortas

Respondan cada una en tres o cuatro líneas.

Pregunta 10

¿Por qué un DBMS no deja el caché de páginas al sistema operativo? Den dos razones concretas.

Pregunta 11

shipment tiene 2·10⁶ filas en 33 000 páginas y un índice B+ tree secundario de altura 3 sobre weight_kg. La condición weight_kg > 20 devuelve el 5 % de las filas. Con t_S = 4 ms y t_T = 0,1 ms, comparen el costo de usar el índice (una página del heap por fila encontrada) con el de un sequential scan. ¿Qué haría PostgreSQL en su lugar?

Pregunta 12

¿Qué garantiza COMMIT sobre lo que está en el disco cuando responde? ¿Qué no garantiza? ¿Por qué eso basta para la durabilidad?

Pregunta 13

En two-phase commit, un participante respondió ready T y el coordinador dejó de responder. ¿Puede el participante abortar T por su cuenta? ¿Puede hacer commit? ¿Qué hace con sus locks mientras tanto? ¿En qué se diferencia de lo que resuelve 2PL?

Pregunta 14

Un key-value store guarda cada clave en N = 5 réplicas. Si las escrituras esperan W = 3 confirmaciones, ¿cuál es el menor R que garantiza que una lectura vea la última escritura confirmada? ¿Cuántas réplicas caídas tolera entonces una lectura? ¿Y una escritura?

Lista de comprobación: resultados de aprendizaje

Después de resolver el final de práctica, marquen lo que ya pueden hacer. Cada línea es uno de los resultados de aprendizaje del programa, con las semanas que lo trabajan y las preguntas de este examen que lo ejercitan. Si una línea no se puede marcar, vuelvan a esas semanas antes del examen.

• 1. Puedo explicar el modelo relacional (relaciones, esquemas, claves, integridad referencial) y escribir consultas en álgebra relacional y en SQL, incluidas joins, agregación, subconsultas, vistas y funciones de ventana. Semanas 1 a 5 · Pregunta 1 a).
• 2. Puedo diseñar una base de datos a partir de requisitos con el modelo E-R, traducirla a tablas y normalizarla con dependencias funcionales hasta BCNF o 3NF, justificando cada decisión. Semanas 6 y 7 · Pregunta 1 b). El modelo E-R no entra en este examen: practíquenlo con las preguntas 7 y 8 del parcial de práctica.
• 3. Puedo escribir aplicaciones en Node.js que usan PostgreSQL de forma segura (consultas parametrizadas, transacciones, manejo de errores) y reconocer una inyección SQL. Semanas 5 y 13 · Pregunta 8 b). La inyección SQL se practica con la pregunta 6 del parcial de práctica.
• 4. Puedo describir cómo un DBMS organiza los datos en disco y en memoria (páginas, registros, buffer pool) e implementar estructuras de índice como B+ trees y tablas hash. Semanas 9 y 10 · Preguntas 2 y 10.
• 5. Puedo estimar el costo de los algoritmos de selección, ordenamiento externo y join, leer un plan de ejecución (EXPLAIN ANALYZE) y elegir los índices adecuados para una carga de trabajo. Semanas 10 a 12 · Preguntas 3, 4, 5 y 11.
• 6. Puedo explicar las propiedades ACID, decidir si un schedule es serializable, comparar 2PL, MVCC y los niveles de aislamiento de SQL, y explicar cómo el log y ARIES recuperan la base de datos después de una caída. Semanas 13 a 15 · Preguntas 6, 7, 8 a), 9 y 12. Las preguntas 13 y 14 (semana 16: two-phase commit y réplicas) llevan estas ideas a varias máquinas.