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 | Bini, Tarcizio Alexandre | - |
Data de aceite: dc.date.accessioned | 2025-09-01T11:55:57Z | - |
Data de disponibilização: dc.date.available | 2025-09-01T11:55:57Z | - |
Data de envio: dc.date.issued | 2024-10-28 | - |
Data de envio: dc.date.issued | 2024-10-28 | - |
Data de envio: dc.date.issued | 2009 | - |
Fonte completa do material: dc.identifier | https://hdl.handle.net/1884/19476 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/1884/19476 | - |
Descrição: dc.description | Orientador: Marcos Sfair Sunyé | - |
Descrição: dc.description | Inclui apêndice | - |
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, 17/04/2009 | - |
Descrição: dc.description | Inclui bibliografia | - |
Descrição: dc.description | 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. | - |
Descrição: dc.description | 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. | - |
Formato: dc.format | viii, 85f. : il., grafs., tabs. | - |
Formato: dc.format | application/pdf | - |
Formato: dc.format | application/pdf | - |
Relação: dc.relation | Disponível em formato digital | - |
Palavras-chave: dc.subject | Algorítmos | - |
Palavras-chave: dc.subject | Otimização combinatoria | - |
Palavras-chave: dc.subject | Banco de dados | - |
Palavras-chave: dc.subject | Ciência da computação | - |
Título: dc.title | Aplicação do algoritmo de Kruskal na otimização de consultas com múltiplas junções relacionais | - |
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: