05_-_processamento_de_consulta

Prévia do material em texto

PROCESSAMENTO E OTIMIZAÇÃO DE 
CONSULTAS 
 (LIVRO BASE: SISTEMAS DE BANCO DE DADOS – ELMASRI & NAVATHE, CAP. 19 – 6 ED.)‏ 
Álgebra Relacional 
 Álgebra relacional 
 Conjunto básico de operações para o modelo relacional 
 
 Expressão da álgebra relacional 
 Sequência de operações da álgebra relacional 
 
Operações relacionais unárias: 
SELEÇÃO e PROJEÇÃO 
 A operação SELEÇÃO 
 Subconjunto das tuplas de uma relação que satisfaça 
uma condição de seleção: 
 
 
• Expressão booleana contém cláusulas da forma 
• <nome atributo> <op comparação> <valor constante> 
ou 
• <nome atributo> <op comparação> <nome atributo> 
Operações relacionais unárias: 
SELEÇÃO e PROJEÇÃO (cont.) 
 Exemplo: 
 
 
 <condição seleção> é aplicada independentemente para 
cada tupla individual t em R 
 Se a condição for avaliada como TRUE, tupla selecionada 
 
 Condições booleanas AND, OR e NOT 
 
A operação PROJEÇÃO 
 Seleciona colunas da tabela e descarta as outras: 
 
 Grau 
 Número de atributos em <lista atributos> 
 Eliminação de duplicatas 
 Resultado da operação PROJEÇÃO como um conjunto de 
tuplas distintas 
 
Sequências de operações e a 
operação RENOMEAR 
 Expressão em linha: 
 
 Sequência de operações: 
 
 
 Renomear atributos nos resultados intermediários 
 Operação RENOMEAR 
 
A operação PRODUTO CARTESIANO 
ou PRODUTO CRUZADO 
 PRODUTO CARTESIANO 
 PRODUTO CRUZADO ou JUNÇÃO CRUZADA 
 Indicada por × 
 Operação de conjunto binária 
 Relações que não precisam ser compatíveis na união 
 Útil quando seguida por uma seleção que combina 
valores de atributos 
 
Operações relacionais binárias: 
JUNÇÃO 
 A operação JUNÇÃO 
 Indicada por 
 Combina tuplas relacionadas de duas relações em uma 
única tupla 'maior' 
 Condição de junção geral tem a forma <condição> AND 
<condição> AND... AND <condição> 
 Exemplo: 
 
Principais operações algébricas 
 
Processamento de Consultas 
 Extração de informações do BD 
 Consulta SQL 
 adequada para uso humano 
 não adequada para processamento pelo SGBD 
 não descreve uma seqüência de passos (procedimento) a 
ser seguida 
 não descreve uma estratégia eficiente para a 
implementação de cada passo no que diz respeito ao 
acesso a nível físico (arquivos do BD) 
 O SGBD deve se preocupar com este 
processamento! 
módulo Processador de Consultas 
Módulo Processador de Consultas 
 Objetivo 
 otimização do processamento de uma consulta 
 tradução, transformação e geração de uma estratégia (plano) 
de execução 
 estratégia de acesso 
 leva em conta algoritmos predefinidos para implementação de 
passos do processamento e estimativas sobre os dados 
 Vale a pena todo este esforço? Sim! 
 Tx = tempo para definir e executar uma estratégia 
otimizada de processamento 
 Ty = tempo para executar uma estratégia não-
otimizada de processamento 
 Quase sempre: Tx  Ty 
Etapas de Processamento 
Tradução 
Transformação 
Definição do 
Plano de Execução 
Consulta em linguagem 
de alto nível 
(consulta SQL, p. ex.) 
Representação interna 
(árvore algébrica da consulta) 
Representação transformada 
(árvore otimizada algebricamente) 
Plano de Execução 
(árvore com indicação de 
estratégias de acesso) 
Processador Run-time 
Gerador de Código 
Código de 
Execução 
Resultado da 
Consulta 
Etapas de Processamento 
Tradução 
Transformação 
Definição do 
Plano de Execução 
Consulta em linguagem 
de alto nível 
(consulta SQL, p. ex.) 
Representação interna 
(árvore algébrica da consulta) 
Representação transformada 
(árvore otimizada algebricamente) 
Plano de Execução 
(árvore com indicação de 
estratégias de acesso) 
Processador Run-time 
Gerador de Código 
Código de 
Execução 
Resultado da 
Consulta 
• análise léxica 
 - cláusulas SQL e nomes válidos 
• análise sintática 
 - validação da gramática 
• análise semântica 
 - nomes usados de acordo com a estrutura do 
esquema 
• conversão para uma árvore algébrica 
 da consulta 
Árvore (Algébrica) da Consulta 
 Estrutura que representa o mapeamento da 
consulta para a álgebra relacional 
 uma‏expressão‏da‏álgebra‏relacional‏“estendida” 
 pode indicar alguma computação (função agregação, atributo calculado, 
...) 
 
 nodos folha: relações (do BD ou resultados intermediários) 
 
 nodos internos: operações da álgebra 
Exemplo de Árvore da Consulta 
select m.CRM, m.nome, a.número, a.andar 
from Médicos m, Ambulatórios a 
where m.especialidade = ‘ortopedia’ 
and a.andar = 2 
and m.número = a.número 
Consulta 
Exemplo de Árvore da Consulta 
select m.CRM, m.nome, a.número, a.andar 
from Médicos m, Ambulatórios a 
where m.especialidade = ‘ortopedia’ 
and a.andar = 2 
and m.número = a.número 
Médicos Ambulatórios 
X 
 m.especialidade = ‘ortopedia’ 
  a.andar = 2 
  m.número = a.número 
 m.CRM, m.nome, 
 a.número, a.andar 
Árvore Algébrica 
de Consulta 
Consulta 
Árvore (Algébrica) da Consulta 
 Processamento da árvore 
 nodos internos são executados quando seus operandos 
estão disponíveis 
 
 são substituídos pela relação resultante 
 
 a execução termina quando o nodo raiz é executado 
Etapas de Processamento 
Tradução 
Transformação 
Definição do 
Plano de Execução 
Consulta em linguagem 
de alto nível 
(consulta SQL, p. ex.) 
Representação interna 
(árvore algébrica da consulta) 
Representação transformada 
(árvore otimizada algebricamente) 
Plano de Execução 
(árvore com indicação de 
estratégias de acesso) 
Processador Run-time 
Gerador de Código 
Código de 
Execução 
Resultado da 
Consulta 
• definição de uma árvore de 
 consulta equivalente 
- chega ao mesmo resultado 
- processa de forma mais 
eficiente 
• também chamada de 
 Otimização Algébrica 
Exemplo de Árvore Equivalente 
Médicos Ambulatórios 
X 
 m.especialidade = ‘ortopedia’ 
  a.andar = 2 
  m.número = a.número 
 m.CRM, m.nome, 
 a.número, a.andar 
Médicos Ambulatórios 
X 
 m.número = a.número 
 m.CRM, m.nome, 
 a.número, a.andar 
 m.especialidade 
 = ‘ortopedia’ 
 
a.andar = 2 
 
Exemplo de Árvore Equivalente 
Médicos Ambulatórios 
X 
 m.especialidade = ‘ortopedia’ 
  a.andar = 2 
  m.número = a.número 
 m.CRM, m.nome, 
 a.número, a.andar 
Médicos Ambulatórios 
X 
 m.número = a.número 
 m.CRM, m.nome, 
 a.número, a.andar 
 m.especialidade 
 = ‘ortopedia’ 
 
a.andar = 2 
 
Quantas Tuplas temos ? Quantas Tuplas temos ? 
50 tuplas 10 tuplas 
5 tuplas 
1 tupla 
Etapas de Processamento 
Tradução 
Transformação 
Definição do 
Plano de Execução 
Consulta em linguagem 
de alto nível 
(consulta SQL, p. ex.) 
Representação interna 
(árvore algébrica da consulta) 
Representação transformada 
(árvore otimizada algebricamente) 
Plano de Execução 
(árvore com indicação de 
estratégias de acesso) 
Processador Run-time 
Gerador de Código 
Código de 
Execução 
Resultado da 
Consulta 
análise de alternativas de definição de 
estratégias de acesso 
- escolha de algoritmos para 
implementação de operações 
- existência de índices 
- estimativas sobre os dados 
 (tamanho de tabelas, seletividade, ...) 
Exemplo de Plano de Execução 
Médicos AmbulatóriosX 
 m.número = a.número 
 m.CRM, m.nome, 
 a.número, a.andar 
 m.especialidade 
 = ‘ortopedia’ 
 
a.andar = 2 
(pesquisa linear) 
(pesquisa indexada) 
(loop-aninhado) 
(processamento pipeline) 
Etapas de Processamento 
Tradução 
Transformação 
Definição do 
Plano de Execução 
Consulta em linguagem 
de alto nível 
(consulta SQL, p. ex.) 
Representação interna 
(árvore algébrica da consulta) 
Representação transformada 
(árvore otimizada algebricamente) 
Plano de Execução 
(árvore com indicação de 
estratégias de acesso) 
Processador Run-time 
Gerador de Código 
Código de 
Execução 
Resultado da 
Consulta 
Etapas de Processamento 
Tradução 
Transformação 
Definição do 
Plano de Execução 
Consulta em linguagem 
de alto nível 
(consulta SQL, p. ex.) 
Representação interna 
(árvore algébrica da consulta) 
Representação transformada 
(árvore otimizada algebricamente) 
Plano de Execução 
(árvore com indicação de 
estratégias de acesso) 
Processador Run-time 
Gerador de Código 
Código de 
Execução 
Resultado da 
Consulta 
FOCO: 
OTIMIZADOR DE 
CONSULTA 
Otimização Algébrica 
 Objetivo do passo de Transformação 
 entrada: árvore da consulta inicial 
 saída: árvore da consulta otimizada (pode manter a 
mesma árvore) 
 Base 
 regras de equivalência algébrica 
 devem ser conhecidas pelo otimizador para que possam 
ser geradas transformações válidas 
 algoritmo de otimização algébrica 
 indica a ordem de aplicação das regras e de outros 
processamentos de otimização 
Regras de Equivalência Algébrica 
1. Cascata de Seleções 
c1  c2  ... cn (R)  c1 (c2 (... (cn (R)))) 
2. Comutatividade de Seleções 
c1 (c2 (R))  c2 (c1 (R)) 
3. Cascata de Projeções 
listaAtributos1 (R)  listaAtributos1 (listaAtributos2 (...(listaAtributosN (R)))) 
Regras de Equivalência Algébrica 
4. Comutatividade de Seleções e Projeções 
a1, a2 , ..., an (c (R))  c (a1, a2 , ..., an (R)) 
5. Comutatividade de Operações Produtórias (“X”) 
R “X” S  S “X” R 
- por “X” entenda-se: X ou X  ou 
 
- a ordem dos atributos e tuplas do resultado não é relevante 
 
Regras de Equivalência Algébrica 
6. Comutatividade de Seleções e Operações Produtórias 
(a) c (R “X” S)  (c (R)) “X” S ou 
 
(b) c (R “X” S)  (c1 (R)) “X” (c2 (S)) 
 
- válidas em quais situações? 
Regras de Equivalência Algébrica 
7. Comutatividade de Projeções e Operações Produtórias 
(a) L (R “X” S)  (r1,...rn (R)) “X” (s1,...sm (S)) ou 
 
- válidas em quais situações? 
Regras de Equivalência Algébrica 
8. Comutatividade de Operações de Conjunto 
R  S  S  R e 
 
R  S  S  R 
 
- por quê a “” não é comutativa? 
 
9. Associatividade de Operações Produtórias e de Conjunto (“”) 
(R “” S) “” T  R “” (S “” T) 
 
 
- por “X” entenda-se: X ou ou  ou  
- por quê a “” não é associativa? 
Regras de Equivalência Algébrica 
10. Comutatividade de Seleção e Operações de Conjunto (“”) 
 
11. Comutatividade de Projeção e União 
c (R “” S)  (c (R)) “” (c (S)) 
 
- por “” entenda-se:  ou  ou  
listaAtributos (R  S)  (listaAtributos (R))  (listaAtributos (S)) 
 
- por quê a “” e a “” não são comutativas? 
Regras de Equivalência Algébrica 
12. Fusão de Seleções e Operações Produtórias 
c (R X S)  R S c 
Algoritmo de Otimização Algébrica 
 Algoritmo de alto (altíssimo!) nível (heurístico) 
 Composto de 6 grandes passos 
 Passo 1 
 aplicar a regra 1 
 desmembrar operações de seleção 
 maior flexibilidade para mover seleções 
1. Cascata de Seleções 
c1  c2  ... cn (R)  c1 (c2 (... (cn (R)))) 
Algoritmo de Otimização Algébrica 
 Passo 2 
 aplicar as regras 2, 4, 6 e 10 
 objetivo 
 mover seleções para níveis inferiores da árvore o máximo 
possível 
Algoritmo de Otimização Algébrica 
 Passo 2 
 aplicar as regras 2, 4, 6 e 10 
 objetivo 
 mover seleções para níveis inferiores da árvore o máximo 
possível 
2. Comutatividade de Seleções 
c1 (c2 (R))  c2 (c1 (R)) 
4. Comutatividade de Seleções e Projeções 
a1, a2 , ..., an (c (R))  c (a1, a2 , ..., an (R)) 
6. Comutatividade de Seleções e Operações Produtórias 
c (R “X” S)  (c (R)) “X” S ou c (R “X” S)  (c1 (R)) “X” (c2 (S)) 
10. Comutatividade de Seleção e Operações de Conjunto (“”) 
c (R “” S)  (c (R)) “” (c (S)) 
Algoritmo de Otimização Algébrica 
 Passo 3 
 aplicar a regra 9 
mudar de posição sub-árvores envolvidas em operações 
produtórias 
 objetivos 
 combinar prioritariamente sub-árvores com menor número de 
dados 
 investigar sub-árvores com seleções mais restritivas 
 evitar produtos cartesianos 
 combinações sem atributos de junção 
9. Associatividade de Operações Produtórias e de Conjunto (“”) 
(R “” S) “” T  R “” (S “” T) 
 
 
Algoritmo de Otimização Algébrica 
 Passo 4 
 aplicar a regra 12 
 otimizar operações produtórias 
 
 Passo 5 
 aplicar as regras 3, 4, 7 e 11 
 desmembrar e mover projeções para níveis inferiores da árvore, 
tanto quanto possível, definindo novas projeções conforme se faça 
necessário 
 
 Passo 6 
 identificar sub-árvores que representem grupos de 
operações que possam ser executados por um único 
algoritmo 
 defina-os uma única vez (uma única sub-árvore)‏na‏“árvore” 
 
Exemplo 
 Ache o sobrenome dos funcionários nascidos após 
1957 que trabalham em um projeto chamado 
‘Aquarious’ 
 Essa consulta pode ser especificada em SQL da 
seguinte forma: 
 SELECT Unome 
 FROM FUNCIONARIO, TRABALHA_EM, PROJETO 
 WHERE projnome=‘Aquarius’ AND Projnumero=Pnr 
AND FCpf=Cpf AND Data_nasc>’31-12-1957’ 
Otimização da consulta 
Algoritmos básicos que implementam 
operações relacionais 
 Ordenação Interna 
 Ordenação Externa 
 Seleção 
 Projeção 
 Junção 
 
Algoritmos básicos que implementam 
operações relacionais 
 Utilizados para ordenação de grandes arquivos 
armazenados no disco 
 Estratégia MERGE-SORT: 
Ordena subarquivos menores(runs) 
 Faz a fusão de runs ordenados, criando assim um novo 
subarquivo ordenado 
 
MergeSort 
 
MergeSort 
 
MergeSort 
 
MergeSort 
 
MergeSort 
 Considerações: 
 O arquivo a ser ordenado está armazenado no Disco 
 Existem Nb blocos disponíveis no buffer 
 Nb blocos (runs) são lidos do disco e armazenados no 
buffer 
 Os runs são ordenado por um algoritmo de ordenação 
interna 
 Os runs ordenados são escritos em arquivos temporários no 
disco 
 É feita a fusão dos runs ordenados para obtenção do 
arquivo ordenado 
 
 
M
e
r
g 
- 
S
o
r
t 
Exemplo: 
 Número de buffers disponíveis da memória principal: nB=5 blocos 
 Tamanho do arquivo b=1.024 blocos de disco, 
 Então, m=b/nB = 205 pedaços iniciais com tamanho de cinco blocos, 
 exceto o último. 
M
e
r
g 
- 
S
o
r
t 
M
e
r
g 
- 
S
o
r
t 
M
e
r
g 
- 
S
o
r
t 
Algoritmos para operação SELECT 
 Considerações: 
 Diversas formas de implementação: 
 Dependência da forma de organização do arquivo 
 Dependência da existência de arquivos de índices 
 
Algoritmos para operação SELECT 
 Exemplo 
Operação de 
Seleção 
Simples 
Algoritmos para operação SELECT 
 Exemplo 
Operação de 
Seleção 
ComplexasOperação de 
Seleção 
Simples 
Algoritmos para operação SELECT 
 Exemplo 
Métodos de Busca para Seleções Simples 
Métodos de Busca para Seleções Complexas 
 
Operação de 
Seleção 
Complexas 
Operação de 
Seleção 
Simples 
Algoritmos para operação SELECT 
 Métodos de Busca para Seleções Simples 
 Algoritmos que realizam a varredura de um arquivo 
(scan files) em busca do registro desejado com base em 
um único atributo. 
 Índices podem ser utilizados (índice de varredura) 
 
Algoritmos para operação SELECT - 
Métodos de Busca para Seleções Simples 
 
 Métodos de Busca para Seleções Simples 
 S1 → Busca Linear (força bruta): 
 recupera TODOS os registros no arquivo de dados no disco 
e testa a condição. 
 
Algoritmos para operação SELECT - 
Métodos de Busca para Seleções Simples 
 
 Métodos de Busca para Seleções Simples 
 S1 → Busca Linear (força bruta): 
 recupera TODOS os registros no arquivo de dados no disco 
e testa a condição. 
 S2 → Busca Binária: 
 a condição de seleção envolve igualdade sobre o atributo 
utilizado na ordenação do arquivo. Busca no arquivo de 
dados no disco. 
 
Algoritmos para operação SELECT - 
Métodos de Busca para Seleções Simples 
 
 Métodos de Busca para Seleções Simples 
 S1 → Busca Linear (força bruta): 
 recupera TODOS os registros no arquivo de dados no disco 
e testa a condição. 
 S2 → Busca Binária: 
 a condição de seleção envolve igualdade sobre o atributo 
utilizado na ordenação do arquivo. Busca no arquivo de 
dados no disco. 
 S3 → Utilizar arquivo de índice primário/hash: 
 a condição de seleção envolve igualdade sobre campo 
utilizado para criação de arquivo de índice primário/hash. 
 
Algoritmos para operação SELECT 
 Métodos de Busca para Seleções Simples 
 S4 → Utilizar arquivo de índice primário para recuperar múltiplos 
registros: 
 Caso a condição de seleção for do tipo >, >=, < e =< sobre um campo 
chave para o qual existe um arquivo de índice primário, executa seleção de 
igualdade e em seguida, recupera os registros seguintes no arquivo de 
dados ordenado (no disco). 
Algoritmos para operação SELECT 
 Métodos de Busca para Seleções Simples 
 S4 → Utilizar arquivo de índice primário para recuperar 
múltiplos registros: 
 Caso a condição de seleção for do tipo >, >=, < e =< sobre um 
campo chave para o qual existe um arquivo de índice primário, 
executa seleção de igualdade e em seguida, recupera os registros 
seguintes no arquivo de dados ordenado (no disco). 
 S5 → Utilizar arquivo de índice de cluster para recuperar 
múltiplos registros: 
 Caso a condição de seleção envolva comparação de igualdade 
sobre atributo utilizado na criação de índice de cluster. Busca no 
índice, encontra o ponteiro para o bloco e busca nos blocos 
consecutivos do arquivo de dados. 
Algoritmos para operação SELECT 
 Métodos de Busca para Seleções Simples 
 S4 → Utilizar arquivo de índice primário para recuperar 
múltiplos registros: 
 Caso a condição de seleção for do tipo >, >=, < e =< sobre um 
campo chave para o qual existe um arquivo de índice primário, 
executa seleção de igualdade e em seguida, recupera os registros 
seguintes no arquivo de dados ordenado (no disco). 
 S5 → Utilizar arquivo de índice de cluster para recuperar 
múltiplos registros: 
 Caso a condição de seleção envolva comparação de igualdade 
sobre atributo utilizado na criação de índice de cluster. Busca no 
índice, encontra o ponteiro para o bloco e busca nos blocos 
consecutivos do arquivo de dados. 
 S6 → Utilização de índice secundário: 
 Caso a condição de seleção envolva um atributo para o qual um 
arquivo de índice secundário foi criado. Busca no índice e determina 
o(s) ponteiro(s) para o(s) bloco(s) que respondem a condição de 
seleção. 
Algoritmos para operação SELECT 
Estratégia Descrição Dependência 
S1 Busca Linear (força bruta) 
Busca em qualquer tipo de arquivo 
S2 Busca Binária 
S3 
Utilizar arquivo de índice 
primário/hash 
Dependem da existência de índices 
e/ou da ordenação do arquivo 
S4 
 
Utilizar arquivo de índice 
primário para recuperar 
múltiplos registros 
S5 
 
Utilizar arquivo de índice 
de cluster para recuperar 
múltiplos registros 
S6 
 
Utilização de índice 
secundário 
Algoritmos para operação SELECT 
 Métodos de Busca para Seleções Complexas 
 Aplicável às Operações Conjuntivas → operações formadas 
pela concatenação de diversas condições de seleção (AND) 
 S7 → Utilizar índice individual: 
 S8 → Utilizar índice composto: 
 S9 → Realizar interseção de registros: 
 
 
Algoritmos para operação SELECT 
 Métodos de Busca para Seleções Complexas 
 S7 → Utilizar índice individual: 
 Caso exista um arquivo de índice para alguma das condições 
simples individual, utilize a estratégia apropriada (S2, S3,..., S6) 
para recuperar os registros e em seguida teste as demais 
condições sobre estes registros. 
 
Algoritmos para operação SELECT 
 Métodos de Busca para Seleções Complexas 
 S7 → Utilizar índice individual: 
 Caso exista um arquivo de índice para alguma das condições simples 
individual, utilize a estratégia apropriada (S2, S3,..., S6) para recuperar os 
registros e em seguida teste as demais condições sobre estes registros. 
 
 S8 → Utilizar índice composto: 
 Caso exista um arquivo de índice composto sobre os atributos envolvidos na 
condição conjuntiva, utilize este para recuperar os registros. 
 
 
Algoritmos para operação SELECT 
 Métodos de Busca para Seleções Complexas 
 S7 → Utilizar índice individual: 
 Caso exista um arquivo de índice para alguma das condições simples 
individual, utilize a estratégia apropriada (S2, S3,..., S6) para recuperar os 
registros e em seguida teste as demais condições sobre estes registros. 
 
 S8 → Utilizar índice composto: 
 Caso exista um arquivo de índice composto sobre os atributos envolvidos na 
condição conjuntiva, utilize este para recuperar os registros. 
 
 S9 → Realizar interseção de registros: 
 Caso exista um arquivo de índice secundário (com ponteiro para registros) 
para dois ou mais atributos envolvidos na condição de busca utilize estes 
índices e encontre os ponteiros resultantes. Determine a interseção do 
conjunto de ponteiros resultantes de cada busca individual. Teste estes 
registros para as condições que não possuem índice de busca. 
 
 
 
Algoritmos para operação SELECT 
 Condições para execução dos algoritmos de seleção 
 Métodos de Busca para Seleções Simples 
 Existe arquivo de índice? 
 NÃO → faça busca sequencial 
 SIM → utilize sempre que possível 
 Métodos de Busca para Seleções Complexas 
 Existe arquivo de índice? 
 NÃO → faça busca sequencial 
 SIM → utilize sempre que possível 
 
 Como otimizar? Executar primeiro as operações que 
retornam o menor número de registros... 
 
 
Algoritmos para operação PROJECT 
 A operação envolve um atributo chave: 
 Todas as tuplas da relação serão mostradas no 
resultado, já que não existe repetição do atributo 
chave 
 A operação não envolve um atributo chave: 
 As tuplas repetidas devem ser eliminadas 
 COMO ELIMINAR ??? 
 
Algoritmos para operação PROJECT 
 Implementação da operação project 
Algoritmos para operação UNIÃO 
 Implementação da operação união: T RUS 
Algoritmos para operação 
INTERSECÇãO 
 Implementação da operação Intersecção: T RS 
Algoritmos para operação DIFERENÇA 
 Implementação da operação diferença: T R-S 
Algoritmos para operação JOIN 
 Operação de Junção Junção em duas vias → junção em dois arquivos 
 Junção em múltiplas vias → junção em três ou mais 
arquivos 
 
Algoritmos para operação JOIN 
 Operação de Junção 
 Junção em duas vias → junção em dois arquivos 
 Junção em múltiplas vias → junção em três ou mais 
arquivos 
 
 J1 → Junção de laços aninhados (força bruta): 
 para cada registro t em R, recupere todos os registros s 
em S e teste se a condição de junção é satisfeita por 
eles: t[A] = s[B] 
 
Algoritmos para operação JOIN 
 J2 → Junção de laço único utilizando estrutura de índice: 
 caso exista um índice para o atributo B de S. Primeiro recupere todos os 
registros t da relação R. Em seguida, para cada registro recuperado t de R, 
busque, na estrutura de índice de S pelos registros correspondentes à entrada 
t[A] = s[B] 
 DEPARTAMENTO |X| GERSSN = SSN EMPREGADO 
 1. recupere todos as tuplas di de DEPARTAMENTO ( i = 1,2,3,..., n ) 
 2. para i = 1,2,3,...n faça 
 3. busque no arquivo de índice primário de EMPREGADO a entrada 
di (GERSSN) 
 se di (GERSSN) existir, retorne a tupla de EMPREGADO 
 correspondente 
 
Algoritmos para operação JOIN 
 J3 → Junção Merge-sort: 
Ordene os arquivos pelo atributo de junção 
 Percorra os arquivos simultaneamente fazendo a 
correspondência dos registros que possuem o mesmo 
valor para A em R e B em S. 
 J3 → Junção 
Merge-sort: 
3 5 9 12 13 19 27 32 
7 8 9 9 12 13 13 15 27 39 
R 
S 
i 
j 
Algoritmos para operação JOIN 
 J4 → Junção-Hash: 
 Escolha o menor arquivo, digamos R; 
 Fase de particionamento: 
 Distribua os registros do arquivo R em buckets de um arquivo de 
hash TEMP segundo uma função de hash F sobre o atributo de 
junção A; 
 Fase de investigação: 
 Verifique utilizando a função de hash F, em qual bucket cada um 
dos registros do arquivo S deve ser mapeado. Combine cada 
registro de S com os demais registros de R armazenados no 
mesmo bucket. 
Algoritmos para operação JOIN 
 J1 → Junção de laços aninhados (força bruta): 
 Considerando: 
 Tamanho do buffer disponível na MP = nB = 7 blocos 
 Tamanho arquivo Departamento = bD = 10 blocos 
 Tamanho arquivo Departamento = rD = 50 registros 
 Tamanho arquivo Empregado = bE = 2.000 blocos 
 Tamanho arquivo Empregado = rE = 6.000 registros 
 Qual arquivo deve ser utilizado no laço externo? 
Exercícios 
1- Dadas as consultas SQL abaixo, escreva a consulta equivalente em álgebra 
relacional e construa a árvore de consulta algébrica otimizada para cada 
uma: 
 
SELECT p.codp, p.nome, c.data 
FROM Pacientes p, Consultas c 
WHERE 
 NOT (p.doença = ‘cancer’ OR c.hora < ’14:00’) 
 AND p.codp = c.codp 
 
SELECT Empregado.Nome_Emp 
FROM Empregado, Trabalha, Projeto 
WHERE Projeto.Nome_Proj = “Infra” 
 AND Projeto.Proj_Num = Trabalha.Proj_Num 
 AND Trabalha.Num_Emp = Empregado.Num_Emp 
 AND Empregado.Data_Nasc = “15/11/91”;