
Atenção:
O eduCAPES é um repositório de objetos educacionais, não sendo responsável por materiais de terceiros submetidos na plataforma. O usuário assume ampla e total responsabilidade quanto à originalidade, à titularidade e ao conteúdo, citações de obras consultadas, referências e outros elementos que fazem parte do material que deseja submeter. Recomendamos que se reporte diretamente ao(s) autor(es), indicando qual parte do material foi considerada imprópria (cite página e parágrafo) e justificando sua denúncia.
Caso seja o autor original de algum material publicado indevidamente ou sem autorização, será necessário que se identifique informando nome completo, CPF e data de nascimento. Caso possua uma decisão judicial para retirada do material, solicitamos que informe o link de acesso ao documento, bem como quaisquer dados necessários ao acesso, no campo abaixo.
Todas as denúncias são sigilosas e sua identidade será preservada. Os campos nome e e-mail são de preenchimento opcional. Porém, ao deixar de informar seu e-mail, um possível retorno será inviabilizado e/ou sua denúncia poderá ser desconsiderada no caso de necessitar de informações complementares.
| Metadados | Descrição | Idioma |
|---|---|---|
| Autor(es): dc.contributor | Sunye, Marcos Sfair, 1964- | - |
| Autor(es): dc.contributor | Universidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática | - |
| Autor(es): dc.creator | Guttoski, Pryscila Barvick | - |
| Data de aceite: dc.date.accessioned | 2025-09-01T10:25:39Z | - |
| Data de disponibilização: dc.date.available | 2025-09-01T10:25:39Z | - |
| Data de envio: dc.date.issued | 2024-10-16 | - |
| Data de envio: dc.date.issued | 2024-10-16 | - |
| Data de envio: dc.date.issued | 2006 | - |
| Fonte completa do material: dc.identifier | https://hdl.handle.net/1884/7868 | - |
| Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/1884/7868 | - |
| Descrição: dc.description | Orientador : Marcos Sfair Sunye | - |
| Descrição: dc.description | Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 2006 | - |
| Descrição: dc.description | Inclui bibliografia | - |
| Descrição: dc.description | Resumo: O papel da otimização de consultas é promover a recuperação dos dados desejados no menor tempo possível. Diversos algoritmos são utilizados nos atuais Sistemas Gerenciadores de Bancos de Dados (SGBD) para realizar a otimização de consultas e determinar a melhor ordem de execução das junções. Os algoritmos de programação dinâmica possuem um custo computacional elevado para determinar a solução ótima, enquanto os algoritmos heurísticos e aleatórios possuem custo computacional menor mas podem alcançar como resultado soluções que estão longe de serem ótimas. Encontrar um algoritmo que seja executado em um tempo razoável e que indique como resultado ao menos uma solução próxima da ótima significa obter um otimizador de consultas extremamente eficiente. Este trabalho apresenta a implementação do algoritmo de Kruskal no processo de otimização de consultas do PostgreSQL. Esse é um algoritmo guloso bottom-up que sempre executa primeiro a junção com maior ganho para formar a árvore geradora mínima do grafo. Dentre os algoritmos existentes foi escolhido o algoritmo de Kruskal por sua simplicidade de implementação e possibilidade de adequação da sua definição ao processo de otimização de consultas. O SGBD escolhido para a realização dos experimentos foi o PostgreSQL por possuir um conjunto complexo de recursos e por ser um software de código aberto. Na maioria dos experimentos realizados o algoritmo de Kruskal retornou os resultados esperados em tempos bastante próximos dos obtidos com os algoritmos implementados no PostgreSQL, com a vantagem da simplicidade de implementação do algoritmo de Kruskal e do seu espaço de busca reduzido enquanto apenas uma árvore de execução é gerada como solução ótima. Os resultados demonstram que o algoritmo de Kruskal é um algoritmo viável para a técnica de otimização de consultas, faltando no futuro definir quais conjuntos de consultas são beneficiados por este algoritmo. | - |
| Descrição: dc.description | Abstract: The query optimization purpose is to retrieve the information as quickly as possible. Many different algorithms are implemented on the modern Database Management Systems (DBMS) aiming the query optimization and in order to define the optimizing join order. The optimization by Dynamic programming finds optimal solutions but has high costs of execution. On the other hand, heuristcs and randomized algorithms have lower execution costs, however there is no guarantee a good solution will be found using this methods. Therefore, developing an algorithm able to find a sub-optimal solution in are asonable time means to have an extremely efficient query optimizer. This work presents Kruskal’s algorithm in query optimization process, which is a bottom-up greedy algorithm that always performs most profitable joins first to reduce query graph to its minimal spanning tree. Kruskal’s algorithm has been chosen because of its easy implementation and because it is possible to apply its defition on query optimization process. PostgreSQL DBMS has been chosen to perform the experiments because it offers full support for many sophisticated features, is an open source relational database systemand performs its query optimization by using Dynamic programming and heuristics algorithms. These features allow a concrete comparison between our approach and the existing ones. On most of tests, Kruskal’s algorithm got the expected results in almost the same time as the results reached by default PostgreSQL’s optimization algorithms, with the advantage on the simplicity of Kruskal’s algorithm implementation and its reduced search space necessary in order to generate only one optimal execution query tree. The results confirm us that Kruskal’s algorithm is a viable method for query optimization while a future work is to perform a broad test to determine, more precisely, witch set of queries would be benefited by this algorithm. | - |
| Formato: dc.format | 94f. : il. | - |
| Formato: dc.format | application/pdf | - |
| Formato: dc.format | application/pdf | - |
| Relação: dc.relation | Disponível em formato digital | - |
| Palavras-chave: dc.subject | SQL (Linguagem de programação de computador) | - |
| Palavras-chave: dc.subject | Recuperação de dados (Computação) | - |
| Palavras-chave: dc.subject | Algorítmos de computador | - |
| Palavras-chave: dc.subject | Ciência da computação | - |
| Título: dc.title | Otimização de consultas no PostgreSQL utilizando o algoritmo de Kruskal | - |
| Tipo de arquivo: dc.type | livro digital | - |
| Aparece nas coleções: | Repositório Institucional - Rede Paraná Acervo | |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: