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:

  1. Página e arquivo de dados. Registros de tamanho fixo em páginas de tamanho fixo.
  2. Cache de páginas. Páginas em memória, página suja, escrita no disco.
  3. Árvore B+. Busca e inserção com divisão de nó.
  4. Tokenizador, parser e catálogo. CREATE TABLE, INSERT e SELECT * 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

Avaliação

  1. Avaliação 1, módulos M1 a M4: 30 pontos
  2. 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.