Questão FC331143
João não sabe fazer consultas em banco de dados e buscou a literatura para fazer uma junção interna otimizada. Um dos pontos observados por João foi que suas relações não tinham se
Linguagens de Programação
FGV · 2024
João não sabe fazer consultas em banco de dados e buscou a literatura para fazer uma junção interna otimizada. Um dos pontos observados por João foi que suas relações não tinham seus registros fisicamente organizados, necessitando de uma ordenação externa. Os atributos de junção são atributos chave. Pares de blocos de arquivo são copiados para buffers de memória na ordem, e os registros de cada arquivo são varridos apenas uma vez cada um, para combinar com o outro arquivo.
O método de implementação da junção utilizado por João foi o(a):
- loop alinhado;
- bloco alinhado;
- ordenação - intercalação;
- único loop;
- partição - hash.
Mostrar resposta e comentário
Gabarito
Certo
Comentário do professor
A técnica descrita é a junção ordenação-intercalação (ou merge join). Ela resolve \(R \bowtie_{A=B} S\) ordenando ambas as relações pelos atributos de junção e, em seguida, fazendo uma varredura conjunta em ordem.
Quando os arquivos não cabem na memória, usa-se ordenação externa: gera-se runs ordenados em memória e depois faz-se intercalações em passes até obter arquivos ordenados pelos atributos de junção.
Com os arquivos ordenados e os atributos sendo atributos chave, o algoritmo lê blocos de cada relação para os buffers, compara os valores atuais e avança o ponteiro da relação com valor menor, produzindo combinações quando houver igualdade. Cada registro é varrido apenas uma vez, minimizando leituras e tornando a operação muito eficiente em I/O.
Conteúdo do catálogo FC Concursos · Atualizado em