Métodos de busca e junção em Banco de Dados

Prévia do material em texto

Implementação 
de 
Banco de Dados
Ricardo Luis Balieiro
Aula 10
Algoritmos Para 
Processamento 
de Consultas
2
Algoritmos Para 
Operação de Seleção
• Métodos de busca para seleções 
simples.
• Métodos de busca para seleções 
complexas.
3
Métodos de busca para 
seleções simples
• Métodos de busca para seleções 
simples: os métodos de pesquisa mais 
simples são aqueles que não possuem uma 
condição estabelecida ou possuam apenas 
uma condição simples. São conhecidos 
como varreduras de arquivos porque varrem 
registros em busca dos registros que 
cumpram uma determinada condição.
4
Métodos de busca para 
seleções simples
• Busca linear: recupera cada registro do 
arquivo e testado se os valores dos 
atributos correspondem à condição dada.
• Busca binária: se o arquivo é ordenado e a 
condição envolvem a comparação com um 
atributo chave, a pesquisa binária pode ser 
utilizada para agilizar a busca.
5
Métodos de busca para 
seleções simples
• Utilização de um índice primário ou 
chave hash: se a condição de seleção 
envolver a comparação de igualdade com 
um atributo chave, pode ser utilizado o 
índice primário ou uma chave hash para 
recuperar os dados. Esses métodos, no 
entanto, retornam um único registro.
6
Métodos de busca para 
seleções simples
• Utilização de um Índice primário para 
recuperar múltiplos registros: se a 
condição de seleção envolver comparações 
de >, <, <= e >= com um campo chave de 
um índice primário, o índice pode ser 
utilizado para encontrar o registro que 
satisfaz a igualdade e recuperar os registros 
seguintes de acordo com a operação.
7
Métodos de busca para 
seleções simples
• Utilização de um índice (cluster) 
agrupamento para recuperação de 
múltiplos registros: se a condição de 
seleção envolver comparações de igualdade 
com um atributo não chave, um índice de 
agrupamento pode ser utilizado para 
recuperar os registros que atendem a 
condição.
8
Métodos de busca 
para seleções complexas 
• Métodos de busca para seleções 
complexas: os métodos de pesquisa mais 
complexas, isto é, compostas por várias 
condições simples, ligadas por conectivos, 
podem utilizar outras técnicas de busca. 
Quando as ligações entre duas condições 
simples são feitas através de AND, 
chamamos de condição conjuntiva.
9
Métodos de busca 
para seleções complexas 
• Seleção conjuntiva utilizando índice 
individual: se uma condição isolada 
permitir um índice que permita utilizar as 
técnicas anteriores, use a condição para 
recuperar os registros e depois verifique se 
cada registro atende as condições 
restantes.
10
Métodos de busca 
para seleções complexas 
• Seleção conjuntiva utilizando índice 
composto: se dois ou mais atributos 
formam uma chave composta, pode-se 
utilizar um índice diretamente.
11
Algoritmos Para Junção
• A junção é uma das operações mais 
demoradas em uma consulta, pois envolve 
a junção de dois ou mais arquivos, o que é 
mais custoso em termos de busca e 
memória.
12
Algoritmos Para Junção
• Junção de loop (ou bloco 
aninhado): recupera cada registro na tabela 
A e verifica se para cada elemento da tabela 
B a condição da junção é satisfeita.
13
Algoritmos Para Junção
• Junção de loop único: se existe um índice 
ou chave hash para um dos atributos da 
junção na tabela A, recupere todos os 
registros da tabela B, e posteriormente 
utilize o índice ou chave hash para 
recuperar os registros que atendem a 
junção.
14
Algoritmos Para Junção
• Junção ordenação-intercalação: se as 
tabelas A e B estão fisicamente ordenados, 
pode-se correr os registros 
simultaneamente e recuperar os dados que 
atendem a junção. Se não estiverem 
ordenados, eles podem ser através de uma 
ordenação externa.
15
Algoritmos Para Junção
• Junção hash: os registros de A e B são 
separados em arquivos menores utilizando 
a mesma função hash (fase de 
particionamento). Na segunda fase (fase de 
investigação), casa-se os registros 
correspondentes.
16
Otimização de Consultas
• Consultas são representadas internamente 
na forma de: 
–Árvores de consulta: determinam a ordem 
de execução das operações. (Melhor para 
efetuar a otimização). 
–Grafos de consulta: indicam apenas as 
operações e os respectivos operandos 
envolvidos. Para cada consulta existe um 
grafo. 
17
Otimização de Consultas
1) Decompor uma consulta SQL em blocos.
2) Transformar cada bloco em uma expressão 
da álgebra relacional.
3) Cada bloco pode conter um único 
comando:
–SELECT
–FROM
–WHERE (se houver)
–GROUP BY (se houver)
–HAVING (se houver)
18
Otimização de Consultas
19
Heurística de Otimização de Consultas
• A ideia principal é que devem ser 
executadas primeiro as operações que 
reduzem os resultados intermediários de 
uma consulta.
20
Heurística de Otimização de Consultas
• Regras heurísticas são usadas para alterar 
a representação interna (árvore ou grafo) de 
uma consulta de modo a otimizar a sua 
execução.
21
Heurística de Otimização de Consultas
• Inicialmente é importante definir que as 
operações de seleção e projeção devem ser 
aplicadas antes de operação de junção e 
outras operações binárias.
• Executar as operações de seleção e 
projeção o mais cedo possível.
• Operações de seleção e junção mais 
restritivas devem ser realizadas o mais cedo 
possível.
22
Medidas de Custo de Uma Consultas
• Custo de acesso ao armazenamento 
secundário: isto é, o custo de leitura e 
gravação entre os discos e a memória 
principal.
• Custo de armazenamento em disco: isto 
é, o custo de armazenamento de arquivos 
intermediários gerados para uma consulta.
23
Medidas de Custo de Uma Consultas
• Custo de computação: isto é, o custo de 
processamento na CPU.
• Custo de uso de memória: isto é, a 
quantidade de memória a ser utilizada na 
execução de uma consulta.
• Custo de comunicação: isto é, o custo de 
envio de uma consulta e dos seus 
resultados do local onde está armazenado o 
banco de dados até onde a consulta foi 
originada.
24
Medidas de Custo de Uma Consultas
• Custo de computação: isto é, o custo de 
processamento na CPU.
• Custo de uso de memória: isto é, a 
quantidade de memória a ser utilizada na 
execução de uma consulta.
• Custo de comunicação: isto é, o custo de 
envio de uma consulta e dos seus 
resultados do local onde está armazenado o 
banco de dados até onde a consulta foi 
originada.
25
Análise de Plano de Execução
• 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, por exemplo).
• Considera algoritmos predefinidos para 
implementação de passos do 
processamento e estimativas sobre os 
dados.
26
Análise de Plano de Execução
– A geração de expressões é apenas parte do 
processo de otimização de consultas. 
– Um plano de avaliação define exatamente 
qual algoritmo será usado para cada 
operação e como a execução das operações 
é coordenada.
27
Fechamento
• Implementação de Banco de Dados
28
Implementação 
de 
Banco de Dados
Ricardo Luis Balieiro
Atividade 10
Exercício 1
30
I) Busca linear
II) Busca binária
III) Utilização de um índice (cluster) 
IV) Seleção conjuntiva utilizando índice composto
Marque a opção CORRETA relativa aos métodos 
de busca para seleções simples.
a) Itens I, II e III. d) Apenas o item I.
b) Itens II, III e IV. e) Apenas o item III.
c) Itens II e IV.