Otimização de Processamento de Expressões de Caminho
Autores
|
2034 |
51,867
|
|
|
2035 |
51,867
|
Informações:
Publicações do PESC
A maioria das linguagens de consulta sobre dados estruturados e semi-estruturados apoia a formulação de consultas contendo expressões de caminho. Expressões de caminho permitem especificar uma navegação entre os objetos armazenados em diferentes coleções. Basicamente, a maioria das propostas de algoritmos para o processamento de expressões de caminho concentra-se na adaptação dos algoritmos baseados no operador de junção relacional. Muitos autores descartam o algoritmo clássico Nai've Pointer Chasing (NP) por considerá-lo uma estratégia ingênua e ineficiente no acesso a disco dos objetos do caminho.
Neste trabalho apresentamos um novo algoritmo propondo uma otimização sobre o algoritmo NP. Sua principal contribuição é melhorar o desempenho de EIS ao evitar a execução de caminhos já percorridos. Este novo algoritmo, chamado de Smart Naïve (SN), ainda mantém o baixo custo de CPU característico do NP. Para comprovar sua eficiência, foram realizados experimentos sobre diferentes configurações de base do benchmark 007. Os resultados obtidos com o SN são comparados com o NP e com o melhor algoritmo baseado em junção proposto na literatura. Os experimentos mostraram o comportamento dos algoritmos e diversas situações não exploradas nos trabalhos da literatura. A análise desses resultados nos permitiu propor heurísticas a serem utilizadas por otimizadores de expressões de caminho. Os algoritmos e técnicas de otimizaçao abordados neste trabalho podem ser estçndidos em outros contextos de aplicação, como por exemplo o processamento de consultas sobre documentos XML.
Most query languages for structured and semi-structured data support writing queries with path expressions. Path expressions provide a mean for specifying navigation between objects stored in data collections. Basically, many algorithm proposals for path expressions processing focus on relational join based algorithm.
Their authors discard the Nai've Pointer Chasing (NP) classical algorithm because they consider it a nalve and inefficient disk access strategy for traversing objects in path.
In this work we present a new algorithm based on optimized version algorithm NP. Its main contribution is to increase 1/0 performance by avoinding to traverse paths already evaluated. This new algorithm, called Smart Nai've (SN), still presents the typicallow CPU costs from NP. Different experiments done on 007 benchmark' s base configurations were used for showing its efficiency. The SN results are compared to NP and to the best join based algorithm proposed on literature. The experiments show the algorithms behavior and many scenarios not explored in other works in the literature. The analysis of results allows us to propose heuristics that can be used for path expression optmizers. The algorithms and optimization techinques studied in this work can be extended int other aplication contexts, such as query processing over XML documents, for example.