Bancos de Dados_ Algoritmos Para Processamento e Otimização de Consultas @Revistabw

Bancos de Dados: Algoritmos para processamento e otimização de consultas Uma consulta escrita em uma linguagem de consulta, como SQL, é lida pelo SGBD, analisada e validada. As técnicas utilizadas são as mesmas que são aprendidas em Teoria dos Compiladores. Inicialmente são verificados os tokens (símbolos), enquanto o analisador sintático verifica se o código está escrito de acordo com as regras da linguagem. A consulta validada é, então, traduzida para uma expressão em álgebra relacional estendida, representada por uma árvore de consulta, que então é otimizada pelo otimizador de consultas. Um SGBD implementa diversos métodos de acesso para realizar uma consulta, e ao se escrever um código e executá-lo, o otimizador de consultas estimará o custo de cada método de acesso e aplicará aquele com o menor custo previsto. Algoritmos para Seleção Existem diversos algoritmos para executar um comando SELECT, que é uma operação de pesquisa para localizar arquivos em disco que atendam a uma determinada condição proposta. Os métodos de pesquisa mais simples são aqueles que não possuem uma condição estabelecida ou que possuem apenas uma condição simples. São conhecidos como varreduras de arquivos porque varrem registros em busca daqueles que cumpram uma determinada condição. Pesquisa Linear: recupera cada registro do arquivo e testado se os valores dos atributos correspondem a condição dada. Pesquisa 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. Índice primário ou chave hash para um único registro: 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 hsh para recuperar os dados. Estes métodos, no entanto, retornam um único registro. Índice primário para diversos 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. Índice de agrupamento: 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. 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. As seguintes técnicas podem ser utilizadas: 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. Seleção conjuntiva utilizando índice composto: se dois ou mais atributos formam uma chave composta, pode-se utilizar um índice diretamente. Quando as ligações entre as condições são feitas através do conectivo OR, chamamos a condição de disjuntiva. Este tipo de condição é mais difícil de ser otimizada pois demanda que cada condição disjuntiva possua atributos indexados (para utilizar as técnicas anteriores), senão a técnica da pesquisa linear será geralmente utilizada. Algoritmos de Junção A junção é uma das operações mais demoradas em uma consulta, pois envolve a união de dois ou mais arquivos, o que é mais custoso em termos de busca e memória. Os principais algoritmos para implementar junção sã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 (semelhante a um for dentro de for). Junção de loop único: se existe um índice ou chave hash para um dos atributos da junção na tabela A, recupera todos os registros da tabela B, e posteriormente utilize o índice ou chave hash para recuperar os registros que atendem a 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. 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. Técnicas heurísticas de otimização de consulta Existem técnicas que permitem modificar a representação interna de uma consulta de modo a melhorar o seu desempenho. Um SGBD pode gerar diversas estruturas diferentes de árvores para uma mesma consulta e as técnicas heurísticas buscam criar uma reordenação da árvore de modo a obter uma estrutura otimizada. A ideia principal é que primeiro devem ser executadas as operações que reduzem os resultados intermediários de uma consulta. 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. Introdução à Informática Conteúdos Gerais Bancos de Dados Engenharia de Requisitos Engenharia de Software Introdução à Internet Probabilidade e Estatística UML Programação Lógica de Programação Linguagem C Linguagem Java Linguagem Python Linguagem R Sistemas Operacionais Linux Matemática Álgebra Linear Cálculo Diferencial e Integral Outros Sites Revista Brasileira de Web- Tecnologia Escreva Certo Index Cristão REVISTA BRASILEIRA DE WEB - TECNOLOGIA Bancos de Dados: Algoritmos para processamento e otimização de con... http://www.revistabw.com.br/revistabw/algoritmos-para-processament... 1 de 2 07/06/2015 15:46

Documents

Bancos de Dados_ Algoritmos Para Processamento e Otimização de Consultas @Revistabw