Banco de Dados II
Horário
Terça e Quinta, 7h30 às 9h. De 01/09/2026 a 22/12/2026.
Objetivo
Construir do zero um sistema gerenciador de banco de dados pequeno, mas funcional. Em Banco de Dados I aprendemos a escrever SQL. Aqui escrevemos o programa que executa o SQL.
Ementa
Revisão dos conceitos básicos de bancos de dados. Aspectos operacionais em sistemas de banco de dados: armazenamento e indexação, processamento e otimização de consultas, controle de concorrência, recuperação de falhas, segurança e integridade. Bancos de dados não convencionais.
As duas partes
Parte 1, de 03/09 a 03/11: quatro módulos. Cada módulo adiciona uma peça ao minidb:
- Página e arquivo de dados. Registros de tamanho fixo em páginas de tamanho fixo.
- Cache de páginas. Páginas em memória, página suja, escrita no disco.
- Árvore B+. Busca e inserção com divisão de nó.
- Tokenizador, parser e catálogo.
CREATE TABLE,INSERTeSELECT *de ponta a ponta, com o catálogo em disco.
Parte 2, de 05/11 a 03/12: um tópico por dupla. Em 05/11 apresento uma implementação de referência, e cada dupla escolhe um dos dez tópicos abaixo, partindo do próprio minidb ou da referência.
Como a disciplina funciona
A linguagem é escolha de vocês, e não muda depois da primeira semana. O contrato é o protocolo: o minidb lê comandos SQL da entrada padrão, um por linha, e imprime o resultado em formato definido.
$ ./minidb dados.db < consultas.sql
CREATE TABLE aluno (id INT, matricula INT);
OK
INSERT INTO aluno VALUES (1, 20260001);
OK 1
SELECT * FROM aluno WHERE id = 1;
1|20260001
(1 linha)
Cada dupla mantém um repositório público no GitHub, com commits pequenos e frequentes. Cada módulo entra por pull request com um NOTES.md de um parágrafo sobre a decisão de projeto mais difícil. Nenhuma biblioteca de banco de dados é permitida dentro do minidb.
Bibliografia
- SCIORE, E. Database Design and Implementation: Second Edition. Springer, 2020. Referência principal.
- ELMASRI, R.; NAVATHE, S. B. Sistemas de Banco de Dados. 7ª edição. Pearson, 2018.
- PETROV, A. Database Internals. O’Reilly, 2019.
Material extra
- CMU 15-445, Intro to Database Systems, aulas em vídeo abertas
- Let’s Build a Simple Database, um clone do SQLite construído em C, passo a passo
- Algorithms Behind Modern Storage Systems, CACM
- A Critique of ANSI SQL Isolation Levels
Avaliação
- Avaliação 1, módulos M1 a M4: 30 pontos
- Avaliação 2, implementação e apresentação de um tópico: 70 pontos
Não haverá outras avaliações na disciplina.
Avaliação 1: módulos M1 a M4 (30 pontos)
Pull request até as 23h59 de 03/11, 7,5 pontos por módulo: metade pelos testes de aceitação, um terço pela qualidade do código e do histórico de commits, e o restante pelo NOTES.md. Módulo entregue depois de 05/11, quando a referência fica pública, não recebe pontos.
Avaliação 2: o tópico (70 pontos)
Cada dupla escolhe um tópico em 05/11, no máximo duas duplas por tópico:
| # | Tópico | O que o minidb passa a fazer |
|---|---|---|
| 1 | Executor e filtro | WHERE com modelo iterador, varredura sequencial e varredura por índice |
| 2 | Transações | BEGIN, COMMIT e ROLLBACK com log de valor antes e depois |
| 3 | Recuperação | Log de escrita antecipada; volta consistente depois de um kill -9 no meio do commit |
| 4 | Remoção e atualização | DELETE e UPDATE, com fusão e redistribuição de nós na árvore B+ |
| 5 | Junções | JOIN por laço aninhado e por hash |
| 6 | Ordenação e agregação | ORDER BY com ordenação externa; COUNT, SUM e GROUP BY |
| 7 | Registros de tamanho variável | VARCHAR e nulos em página com diretório de slots |
| 8 | Concorrência | Várias sessões, bloqueio em duas fases e detecção de deadlock |
| 9 | Otimizador por custo | ANALYZE, estimativa de cardinalidade e EXPLAIN |
| 10 | LSM-tree | Motor de armazenamento alternativo: memtable, SSTables e compactação |
- Implementação (40 pontos). Pull request até as 23h59 de 30/11, com testes escritos pela dupla para o tópico, histórico de commits e
NOTES.md. - Apresentação (30 pontos). Em 01/12 e 03/12. Na semana de 08/12 estarei viajando para um evento, por isso as apresentações foram antecipadas. A ordem das duplas é definida por sorteio na hora, então todas as duplas devem estar prontas já em 01/12.
A apresentação é em dupla e não tem slides: é a execução do minidb, em particular da parte nova que a dupla implementou. A demonstração vale 15 pontos. Os outros 15 vêm das perguntas: cada integrante responde sozinho sobre um trecho do código, escolhido por mim na hora. As duas pessoas precisam demonstrar domínio do tópico e responder à pergunta: o que precisou mudar no minidb para ter isso?
Cronograma
Passível de alterações. Verificar o calendário acadêmico oficial da UFPA para feriados estaduais e municipais.
| # | Data | Dia | Conteúdo |
|---|---|---|---|
| — | 01/09 | Ter | Sem aula |
| T1 | 03/09 | Qui | Apresentação e armazenamento: o critério de pronto, o que não vamos construir, e por que a página é a unidade |
| — | 08/09 | Ter | CBSoft 2026, sem aula (atividade assíncrona) |
| — | 10/09 | Qui | CBSoft 2026, sem aula (atividade assíncrona) |
| I1 | 15/09 | Ter | Laboratório: leitura e escrita de páginas |
| I1 | 17/09 | Qui | Laboratório: serialização de registros. Entrega M1 |
| T2 | 22/09 | Ter | Cache de páginas: por que existe, página suja, política de substituição |
| I2 | 24/09 | Qui | Laboratório: cache de páginas |
| I2 | 29/09 | Ter | Laboratório: escrita no disco e integração com M1 |
| I2 | 01/10 | Qui | Laboratório extra: fechamento do M2. Entrega M2 |
| T3 | 06/10 | Ter | Árvore B+: nós internos e folhas, busca, inserção com divisão, altura e I/O |
| I3 | 08/10 | Qui | Laboratório: busca e inserção sem divisão |
| I3 | 13/10 | Ter | Laboratório: divisão de nó. Entrega M3 |
| — | 15/10 | Qui | Dia do Professor, sem aula |
| T4 | 20/10 | Ter | Parser e catálogo, parte 1: do texto à árvore sintática. Injeção de SQL |
| T4 | 22/10 | Qui | Parser e catálogo, parte 2: o catálogo em disco e o primeiro SELECT * |
| I4 | 27/10 | Ter | Laboratório: tokenizador e parser |
| I4 | 29/10 | Qui | Laboratório: catálogo de tabelas e o primeiro SELECT * |
| I4 | 03/11 | Ter | Laboratório: fechamento do tokenizador, do parser e do catálogo, com INSERT e SELECT rodando. Entrega da Avaliação 1 (M1 a M4) |
| MVP | 05/11 | Qui | Solução mínima viável: apresentação da implementação de referência e dos dez tópicos. Escolha dos tópicos |
| P2 | 10/11 | Ter | Laboratório: implementação do tópico |
| P2 | 12/11 | Qui | Laboratório: implementação do tópico |
| P2 | 17/11 | Ter | Laboratório: implementação do tópico |
| P2 | 19/11 | Qui | Laboratório: implementação do tópico |
| P2 | 24/11 | Ter | Laboratório: implementação do tópico |
| P2 | 26/11 | Qui | Laboratório: implementação do tópico. Entrega da implementação até 30/11, 23h59 |
| A2 | 01/12 | Ter | Apresentações, duplas por sorteio. Todas devem estar prontas |
| A2 | 03/12 | Qui | Apresentações, duplas restantes |
| — | 08/12 | Ter | Sem aula (viagem para evento) |
| — | 10/12 | Qui | Sem aula (viagem para evento) |
| — | 15/12 | Ter | Buffer |
| — | 17/12 | Qui | Buffer |
| — | 22/12 | Ter | Buffer, fechamento e notas |
Sobre o uso de ferramentas de LLM
Um agente escreve uma árvore B+ inteira em trinta segundos, e ela até passa nos testes. Mas as perguntas individuais da apresentação vão deixar evidente quem não entendeu o próprio código. Use a ferramenta para explicar, não para produzir: peça para ela desenhar o que acontece quando um nó divide, ou para revisar o código que vocês escreveram.
Entrega atrasada e plágio
Entregas após o prazo são aceitas, mas não pontuam. Duplas podem discutir ideias entre si, mas copiar código de outra dupla configura plágio, e as duplas envolvidas não recebem os pontos daquela entrega.