Proyecto Chasqui

Un solo proyecto que crece durante todo el semestre: Chasqui, la base de datos de una empresa de encomiendas que recibe paquetes en sus agencias y los lleva por carretera a cualquier ciudad del Perú. Empieza como un conjunto de consultas sobre datos que ya existen y termina con quipu, un motor de almacenamiento propio, pequeño, que guarda esos mismos datos en páginas, los indexa, ejecuta consultas y controla transacciones concurrentes.

El proyecto tiene dos mitades, como el curso:

• P0–P2, usar una base de datos. Consultas SQL, un esquema que protege sus datos con restricciones, un diseño E-R normalizado y una aplicación de línea de comandos en Node.js que usa PostgreSQL con consultas parametrizadas y transacciones.
• P3–P5, construir un motor. quipu, escrito en Node.js: páginas con slots en un archivo, un buffer pool, un índice B+ tree, operadores de consulta con iteradores y, al final, un lock manager y un log de recuperación. Los datos de prueba son los de Chasqui, así que los resultados de quipu se pueden comparar con los de PostgreSQL.

Cada entrega se construye sobre la anterior y debe seguir pasando las pruebas de todas las entregas previas de su mitad.

Las semanas de publicación y entrega están en el calendario del SYLLABUS. Cada entrega tiene su enunciado detallado en su carpeta:

Qué agrega cada entrega

P0 · Calentamiento. Diez consultas SQL sobre los datos de ejemplo de Chasqui, desde un SELECT con WHERE hasta la primera agregación con GROUP BY, y un script en Node.js que imprime las rutas con más envíos. Sirve para conocer los datos, el contenedor y la forma en que se revisan las entregas.

P1 · Esquema y consultas. El esquema que les damos acepta datos absurdos: un viaje con más carga que la capacidad del vehículo, un envío que se entrega antes de salir. Lo endurecen con restricciones (CHECK, UNIQUE, claves foráneas con la acción adecuada para ON DELETE) y escriben consultas con joins externos, agregación, subconsultas correlacionadas y vistas: las que la gerencia pide todos los lunes.

P2 · Diseño y aplicación. Chasqui crece: tarifas por zona y por peso, empleados y conductores, pagos en efectivo y con tarjeta, reclamos. Diseñan el modelo E-R de la ampliación, lo traducen a tablas, justifican con dependencias funcionales que el resultado está en BCNF (o en 3NF, explicando por qué) y escriben la migración que pasa del esquema de P1 al nuevo sin perder datos. Encima construyen chasqui, una aplicación de línea de comandos en Node.js que registra envíos y los asigna a viajes dentro de una transacción.

P3 · Motor: almacenamiento. Empieza quipu. Un archivo de páginas de 4 KiB, páginas con slots para registros de largo variable, un heap file que guarda la tabla de envíos, un buffer pool con política clock y pin counts, y un índice B+ tree sobre una clave entera con búsqueda puntual y por rango.

P4 · Motor: consultas. Operadores con la interfaz de iteradores (open/next/close): sequential scan, index scan, filtro, proyección, block nested loop join, index nested loop join, hash join, ordenamiento externo y agregación con hash. Para tres consultas dadas, arman el plan a mano, miden las páginas leídas y comparan con el plan que elige PostgreSQL.

P5 · Motor: transacciones. Un lock manager con locks compartidos y exclusivos por registro, 2PL estricto, upgrade de locks, cola de espera y detección de deadlocks con un waits-for graph. Además, un log write-ahead con registros de redo y undo y una recuperación que deja la base de datos consistente después de una caída simulada. Se presenta en el laboratorio de la semana 16.

Reglas de entrega

• P0 es individual. P1–P5 se hacen en parejas; la pareja se mantiene durante el semestre salvo acuerdo con el docente.
• Cada entrega es el mismo repositorio con un tag: p0, p1, …, p5. Se revisa el commit de ese tag, y el tag tiene que estar publicado antes del plazo.
• Todo debe pasar make test dentro del contenedor del curso (env/run.sh). El código en Node.js corre sin warnings y sin dependencias adicionales a las que trae el contenedor.
• Las consultas leen de las tablas: un resultado escrito a mano (por ejemplo, con VALUES) cuenta como no entregado.
• Identificadores en inglés y comentarios en español, según la guía de estilo. Palabras clave de SQL en mayúsculas.
• Incluir un README.md corto: integrantes, qué funciona, qué no, cómo se ejecuta y las decisiones principales (con el diagrama E-R desde P2).
• Cualquier integrante debe poder explicar de forma oral cualquier consulta o parte del código entregado; puede haber una defensa breve durante el laboratorio.

Cómo se corren las pruebas

Cada enunciado trae su Makefile (el de cada entrega reemplaza al de la anterior), pruebas públicas (p0.public.test.mjs, p1.public.test.mjs, …) y, si hacen falta, los resultados esperados en la carpeta expected/. Todo se copia a la carpeta del proyecto sin modificarlo, y se queda ahí en las entregas siguientes. Las pruebas que escriben ustedes van en archivos aparte, con nombre *.test.mjs.

/ruta/al/curso/env/run.sh      # desde la carpeta del proyecto
make test                      # crea la base de datos de pruebas y corre todas las pruebas

make test crea, cada vez, una base de datos nueva con los datos de ejemplo de Chasqui (que vienen dentro del contenedor) y corre los archivos *.test.mjs de la mitad del proyecto en que están (P0–P2 o P3–P5) con el runner de pruebas de Node.js (node --test). No hace falta npm install: el driver pg ya está en el contenedor.

La revisión corre make test en el contenedor con las pruebas públicas de todas las entregas de su mitad hasta la actual, más pruebas privadas que verifican los mismos requisitos con otros datos: los mismos tipos de agencias, clientes y envíos, generados con otra semilla. Una consulta que solo funciona con los datos de ejemplo no pasa las pruebas privadas. Ver la guía del laboratorio.