Baixe o app para aproveitar ainda mais
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.
Compartilhar