Query preoptimization in data sources with limited capabilities

Abstract:

Emerging technologies such as Semantic Web, P2P and Semantic Grid have made available a huge number of sources, usually characterized by properties that touch on the complexity of traditional query optimization and processing tasks. In this paper, the effect of limited query capabilities during the process of identifying a good plan to evaluate a query is described. This problem has been found to be NP-Complete and different approaches have been proposed to generate an approximated solution to the problem. The WebSrcMed project, which implements a two-step cost-based optimization strategy to identify a good and safe execution plan, is considered. In a first step, descriptions of the limited query capabilities are considered to partition the space of plans into sets of pre-plans where the query capabilities of the selected sources are satisfied and a good pre-plan is selected among them. In a second step, the space of plans induced by the selected pre-plan is explored, and a good execution plan produced. Since the size of the pre-plans' solution space may be large, efficient exploration techniques to solve the problem are required. An evolutive algorithm that finds good and safe pre-plans efficiently is presented. An experimental study led to observe that the solution is able to efficiently identify good pre-plans for complex queries. The efficiency of the algorithm used (number of different solutions related to the total number of solutions found) is better than the efficiency shown by existing randomized techniques.

Año de publicación:

2008

Keywords:

Fuente:

scopus