Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/30134
Título: | Melhorando o processamento de consultas espaciais usando aproximações consertivas |
Título(s) alternativo(s): | Improving spatial query processing using conservative approximations |
Autor(es): | Bertella, Pedro Gabriel Kohl |
Orientador(es): | Oliveira, Rafael Alves Paes de |
Palavras-chave: | Banco de dados SQL (Computer program language) Engenharia de software Data bases SQL (Linguagem de programação de computador) Software engineering |
Data do documento: | 27-Ago-2021 |
Editor: | Universidade Tecnológica Federal do Paraná |
Câmpus: | Dois Vizinhos |
Citação: | BERTELLA, Pedro Gabriel Kohl. Melhorando o processamento de consultas espaciais usando aproximações conservativas. 2021. Trabalho de Conclusão de Curso (Bacharelado em Engenharia de Software) - Universidade Tecnológica Federal do Paraná, Dois Vizinhos, 2021. |
Resumo: | A utilização de informações geográficas está em constante crescimento em diversos ramos de aplicações. Estas informações são representadas como instâncias dos tipos de dados espaciais ponto, linha ou região. Bancos de dados espaciais (BDE) são responsáveis por armazenar estas informações, além de possibilitar seu acesso e manipulação de maneira ágil. O acesso de dados espaciais em um BDE é realizado por meio de consultas espaciais que, geralmente, utilizam aproximações espaciais para reduzir seu tempo de execução. As aproximações espaciais são representações geométricas simplificadas dos objetos espaciais. Assim, o processamento destas consultas é feito em duas etapas: filtragem e refinamento. Na filtragem são verificados os critérios da consulta sobre as aproximações dos objetos espaciais e, devido a isso, seu conjunto de resultados positivos é imperfeito. Logo, é necessária a etapa de refinamento, que validará os critérios da consulta sobre o objeto real pertencente ao conjunto resposta da filtragem. Deste modo, obtém-se o resultado final da consulta. A etapa de filtragem possui custo de processamento baixo por realizar validações apenas com aproximações, entretanto, a etapa de refinamento possui um custo de processamento alto, devido à complexidade das geometrias dos objetos espaciais por ela processados. Como forma de agilizar a execução de consultas espaciais, este TCC propõe o desenvolvimento, utilização e validação de etapas intermediárias de processamento (entre a filtragem e o refinamento) que façam uso de aproximações espaciais distintas para reduzir o número de objetos espaciais candidatos para processamento na etapa de refinamento. Foram desenvolvidas implementações que realizam o cálculo de aproximações espaciais, validação de relacionamentos topológicos, armazenamento em arquivo e permitem que estas aproximações sejam utilizadas em etapas intermediárias por meio da integração com o FESTIval. Para validação, um experimento foi realizado com consultas espaciais e diferentes combinações de aproximações, permitindo a obtenção de uma combinação que possui melhor desempenho dentre as testadas. A combinação das aproximações MBC e 4-corner se destacou pelo seu ótimo equilíbrio entre tempo necessário para construção e tempo de consulta. |
Abstract: | The use of spatial information is getting progressively more attention in many fields of applications. This information is represented as instances of the spatial data types point, line, or region. Spatial databases are responsible for storing this information while offering both its access and manipulation in an agile manner. Spatial data access in a spatial database is accomplished through spatial queries which, in general, use spatial approximations to reduce their execution time. Spatial approximations are simpler geometric representations of spatial objects. Therefore, spatial query processing is done using two steps: filter and refinement. In the filter step, the query criteria are verified on the approximations of the spatial objects, due to this, the positive result set is imperfect. This way, the refinement step is necessary, because it will validate the query criteria on the original spatial object which belongs to the result set of the filter step. Thus, the final query result is obtained. The filter step has a low processing cost by only performing validations on approximations, whereas the refinement step has a high processing cost, due to the complexity of the geometries of the spatial objects processed by it. As a way to accelerate the execution of spatial queries, this project proposes the development, utilization, and validation of intermediary steps of processing (between filter and refinement) which use distinct spatial approximations to reduce the number of spatial objects that need to be processed in the refinement step. Implementations were developed that perform the calculation of spatial approximations, topological predicate checks, file storage and allow these approximations to be used in intermediate steps through the integration with FESTIval. For validation, an experiment was made using spatial queries and different combinations of approximations, which resulted in a combination that has the best performance among those tested. The combination of the MBC and 4-corner approximations stood out for its great balance of build time and query time. |
URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/30134 |
Aparece nas coleções: | DV - Engenharia de Software |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
processamentoconsultasespaciaisaproximacoesconservativas.pdf | 5,25 MB | Adobe PDF | ![]() Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons