• Entrar
    Ver item 
    •   Página inicial
    • BIBLIOTECA DIGITAL: Teses & Dissertações
    • Teses & Dissertações
    • Ver item
    •   Página inicial
    • BIBLIOTECA DIGITAL: Teses & Dissertações
    • Teses & Dissertações
    • Ver item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Aplicação do algoritmo de Kruskal na otimização de consultas com múltiplas junções relacionais

    Thumbnail
    Visualizar/Abrir
    dissertacao.pdf (775.5Kb)
    Data
    2009
    Autor
    Bini, Tarcizio Alexandre
    Metadata
    Mostrar registro completo
    Resumo
    Resumo: A busca por planos ótimos de execução de consultas em SGDBs relacionais é certamente um problema da classe NP. Em virtude disso, a aplicação de algoritmos de programação dinâmica para esta finalidade fica restrita a certo limite de relações. Dessa forma, vários algoritmos foram propostos na tentativa de se encontrar planos aceitáveis em tempo hábil e com baixo consumo de recursos. Dentre estas soluções, podemos citar os algoritmos genéticos que apresentam a solução para o problema de otimização de consultas em tempo polinomial. Porém, por se tratar de um método aleatório, que exibe muitas variações em seus resultados, planos de execução impráticáveis podem ser escolhidos. Neste trabalho apresentaremos o algoritmo de Kruskal em conjunto com algumas regras de geração de sub-planos como alternativa para a geração de planos de execução de consultas. Tal algoritmo apresenta vantagens como código de implementação simples, tempo de execução polinomial e espaço de busca reduzido. Nós implementamos o algoritmo de Kruskal no SGBD PostgreSQL, o que permitiu confrontar seus resultados como algoritmo de programação dinâmica em consultas simples ou algoritmos genéticos em consultas complexas. Para os testes de performance, nossa metodologia de avaliação, tomou por base os benchmarks TPC-H e TPC-E. Os resultados obtidos demonstram que o algoritmo de Kruskal aplicado a otimização de consultas é uma solução viável que exibe bons resultados em consultas que apresentam múltiplas junções.
     
    Abstract: The search for optimal plans in order to execute queries in relational DBMS is certainly an NP-complete problem. In virtue of this, the applicability of dynamic programming algorithms to the search of the optimal plans is restricted to a certain limit of relations. Because of this problem, severals alternative algorithms were proposed in order to find satisfactory plans in an acceptable time and with low consumption of resources. Among these solutions, we can cite the genetic algorithms which that present the solution to the queries optimization problem in polynomial time. However, it is a random method, which displays many variations in their results, and impractical execution plans can be chosen. This document presents the Kruskal’s algorithm together with some rules for generation of sub-plans as an alternative to the query plan generation. This algorithm has advantages as simple code implementation, polynomial run-time and reduced search space. We implemented this algorithm in PostgreSQL DBMS, which allowed comparetheir results with the dynamic programming in simple queries, or the genetic algorithmin complex queries. In performance tests, our evaluation method based on benchmarksTPC-H and TPC-E. The results show that Kruskal’s algorithm applied to the queries optimization is a viable solution that shows good results for queries that have multiplejoins.
     
    URI
    https://hdl.handle.net/1884/19476
    Collections
    • Teses & Dissertações [10544]

    DSpace software copyright © 2002-2022  LYRASIS
    Entre em contato | Deixe sua opinião
    Theme by 
    Atmire NV
     

     

    Navegar

    Todo o repositórioComunidades e ColeçõesPor data do documentoAutoresTítulosAssuntosTipoEsta coleçãoPor data do documentoAutoresTítulosAssuntosTipo

    Minha conta

    EntrarCadastro

    Estatística

    Ver as estatísticas de uso

    DSpace software copyright © 2002-2022  LYRASIS
    Entre em contato | Deixe sua opinião
    Theme by 
    Atmire NV