Gustavo Pinto

Gustavo Pinto

Professor & Researcher

Banco de Dados II

Horário

Terça e Quinta, 7h30 às 9h. De 01/09/2026 a 22/12/2026.

Objetivo

Construir um sistema gerenciador de banco de dados do zero, pequeno mas funcional, para entender por dentro o que acontece entre o momento em que você escreve uma consulta e o momento em que o resultado volta.

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.

O critério de pronto

Devemos construir um minidb, em que podemos executar um SELECT com WHERE, dentro de uma transação que volta ao ar consistente depois de levar um kill -9 no meio do commit. Sacou? :)

Os sete módulos

Cada módulo tem uma aula teórica e duas aulas de laboratório. São sete módulos, e cada um 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, marcação de página suja, escrita no disco.
  3. Árvore B+. Busca e inserção com divisão de nó.
  4. Parser e catálogo. CREATE TABLE, INSERT e SELECT com WHERE de igualdade.
  5. Executor. Modelo iterador, varredura sequencial, varredura por índice e filtro.
  6. Transações. BEGIN, COMMIT, ROLLBACK e log com valor antes e depois.
  7. Recuperação. Log de escrita antecipada, e refazer e desfazer na partida.

O que não implementamos

  • Remoção na árvore B+. Fusão e redistribuição de nós é a parte mais difícil da estrutura, e o critério de pronto só precisa de busca e inserção.
  • Registros de tamanho variável. Nada de página com diretório de slots, campo VARCHAR de tamanho livre ou mapa de nulos. Tudo tem tamanho fixo.
  • Junções e ordenação. Sem JOIN, sem ORDER BY, sem agregação. Uma tabela por consulta.
  • Otimizador. A escolha entre índice e varredura é uma regra de três linhas, não um modelo de custo.
  • Concorrência. O minidb atende uma sessão por vez. Sem bloqueios, sem níveis de isolamento, sem deadlock.
  • Checkpoint e ARIES completo. A recuperação lê o log inteiro desde o começo, sem número de sequência nem registro de compensação.

Nada disso vira aula minha. Concorrência, segurança e bancos não convencionais são exigências da ementa, e são cobertos pelos seminários de novembro, em que cada dupla estuda um desses temas e apresenta para a turma.

Como a disciplina funciona

A linguagem é escolha de vocês. C, Python, Go, Rust, Java, o que preferirem. Eu forneço o contrato, e não é código. Qualquer linguagem que leia da entrada padrão e escreva na saída padrão passa nos mesmos testes.

O protocolo é o mais simples possível. O minidb recebe comandos SQL, 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)

Escolham a linguagem na primeira semana, e não mudem depois. C ensina mais sobre memória e disco, e custa perto do dobro do tempo. Python some do caminho e deixa vocês pensarem em estrutura. Não estamos competindo em desempenho com o PostgreSQL, então a escolha é sobre o que vocês querem aprender, não sobre velocidade.

Repositório e registro de avanços

Cada dupla deve manter um repositório público, no GitHub criado na primeira semana e usado do começo ao fim.

O repositório precisa mostrar o processo. Commits pequenos e frequentes. Um repositório com sete commits gigantes, um por módulo, na véspera de cada prazo, conta a história de um trabalho que não aconteceu.

Cada módulo entra por pull request e traz um NOTES.md com um parágrafo sobre a decisão de projeto mais difícil daquele módulo. É esse parágrafo, somado ao histórico, que eu leio antes da defesa oral.

Nenhuma biblioteca de banco de dados é permitida dentro do minidb, pelo motivo óbvio.

Bibliografia

  • SCIORE, E. Database Design and Implementation: Second Edition. Springer, 2020. Referência principal, porque constrói um SGBD inteiro.
  • 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. Módulos M1 a M7: 60 pontos
  2. Defesa oral individual do código: 20 pontos
  3. Seminário: 10 pontos
  4. Relatório final e apresentação: 10 pontos

Módulos (60 pontos)

Entrega por pull request no fork da dupla, até as 23h59 da data indicada. M3 e M7 valem 10 pontos cada, por serem os dois mais difíceis; os outros cinco valem 8.

A nota de cada módulo se divide em: metade pelos testes de aceitação que passam, um terço pela qualidade do código e do histórico de commits, e o restante pelo NOTES.md.

Módulo entregue depois da publicação da implementação de referência não recebe pontos, porque a referência já está pública.

Defesa oral individual (20 pontos)

Em 01/12 e 03/12, cada aluno explica sozinho um trecho do minidb da própria dupla, escolhido por mim na hora. Em dupla de implementação é comum um escrever e o outro assistir. Aqui é cada um por sí :)

Seminário (10 pontos)

Nos dias 24/11 e 26/11, cada dupla apresenta um dos temas que o minidb não implementa. São dez minutos de apresentação e três de perguntas, sem relatório escrito. A entrega é a apresentação mais uma página de referências consultadas.

Os temas são sorteados em 10/11, um por dupla:

  • Controle de concorrência e bloqueio em duas fases
  • Níveis de isolamento e as anomalias que cada um permite
  • Algoritmos de junção: laço aninhado, ordenação e fusão, hash
  • Otimização baseada em custo: estatísticas e estimativa de cardinalidade
  • Segurança: injeção de SQL, privilégios e segurança em nível de linha
  • Armazenamento colunar e por que ele domina análise de dados
  • LSM-trees e os bancos chave-valor
  • Bancos distribuídos: replicação e particionamento

A pergunta que toda apresentação precisa responder é a mesma: o que precisaria mudar no minidb para ter isso? Não quero um resumo de capítulo de livro. Quero que vocês liguem o tema ao código que escreveram.

Quem apresenta lendo material de consulta recebe zero.

Relatório final e apresentação (10 pontos)

Relatório de 3 a 4 páginas respondendo a três perguntas: como o minidb de vocês está organizado, qual decisão de projeto vocês tomaram diferente do que o livro sugere e por quê, e o que fariam diferente recomeçando.

A apresentação é de 10 minutos em 10/12, e o centro dela é a demonstração ao vivo do critério de pronto: a consulta com índice, dentro da transação, e o kill -9. Ensaiem.

Cronograma

Passível de alterações. Verificar o calendário acadêmico oficial da UFPA para feriados estaduais e municipais.

# Data Dia Conteúdo
T0 01/09 Ter Apresentação. A anatomia de um SGBD, o critério de pronto e o que não vamos construir
T1 03/09 Qui Armazenamento: por que a página é a unidade, registro de tamanho fixo, heap file
— 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. Entrega M2
T3 01/10 Qui Árvore B+: nós internos e folhas, busca, inserção com divisão, altura e I/O
I3 06/10 Ter Laboratório: busca e inserção sem divisão
I3 08/10 Qui Laboratório: divisão de nó. Entrega M3
T4 13/10 Ter Parser e catálogo: do texto à árvore sintática. Injeção de SQL
I4 15/10 Qui Laboratório: tokenizador e parser (confirmar Dia do Professor)
I4 20/10 Ter Laboratório: catálogo de tabelas. Entrega M4
T5 22/10 Qui Executor: modelo iterador, varredura sequencial, varredura por índice, seletividade
I5 27/10 Ter Laboratório: varredura sequencial e filtro
I5 29/10 Qui Laboratório: varredura por índice e a regra de escolha. Entrega M5
T6 03/11 Ter Transações: ACID, log com valor antes e depois, atomicidade por desfazer
I6 05/11 Qui Laboratório: BEGIN, COMMIT e o log
I6 10/11 Ter Laboratório: ROLLBACK. Entrega M6 e sorteio dos temas de seminário
T7 12/11 Qui Recuperação: escrever o log antes do dado, fsync no commit, refazer e desfazer
I7 17/11 Ter Laboratório: log de escrita antecipada
I7 19/11 Qui Laboratório: recuperação após o kill -9. Entrega M7
S1 24/11 Ter Seminários, primeira metade das duplas
S2 26/11 Qui Seminários, segunda metade das duplas
DO 01/12 Ter Defesa oral individual, parte 1
DO 03/12 Qui Defesa oral individual, parte 2
— 08/12 Ter Nossa Senhora da Conceição, sem aula (feriado municipal em Belém)
PF 10/12 Qui Apresentações finais, 15 minutos por dupla
— 15/12 Ter Buffer
— 17/12 Qui Buffer
— 22/12 Ter Buffer, fechamento e notas

Atividades Assíncronas

Na semana de 08 a 11/09 estarei no CBSoft 2026, no IME-USP, e não haverá aula em 08/09 e 10/09. Entregas para 15/09:

  • Criar o repositório da dupla, escolher a linguagem, rodar o script de testes e enviar a saída, que deve mostrar todos os testes falhando.
  • Responder em um parágrafo: por que o SGBD gerencia as próprias páginas em vez de deixar isso para o sistema operacional?

Sobre o uso de ferramentas de LLM

Um agente escreve uma árvore B+ inteira em trinta segundos, e ela até passa nos testes. Se vocês fizerem isso, terão um repositório bonito e nenhum aprendizado, e a defesa oral de dezembro vai deixar isso evidente para todo mundo, inclusive para vocês. Ela vale 20 pontos por esse motivo.

A regra prática: use a ferramenta para explicar, não para produzir. Peça para ela desenhar o que acontece quando um nó divide, peça outro exemplo, peça para revisar o código que vocês escreveram. O NOTES.md de cada módulo existe para registrar a decisão que vocês tomaram, e não sai de código que vocês não entenderam.

Entrega atrasada

Entregas após o prazo serão aceitas, mas os pontos referentes não serão contabilizados. No caso dos módulos, o prazo é a publicação da implementação de referência.

Política de plágio

Os módulos devem ser implementados pela dupla. Duplas são encorajadas a discutir ideias entre si, mas copiar código de outra dupla, ou do fork de outra dupla, configura plágio, e nesse caso as duplas envolvidas não receberão os pontos do módulo.