|
Digital Library of the
European Council for Modelling and Simulation |
Title: |
Improved A* Algorithm For Query Optimization |
Authors: |
Amit
Goyal, Ashish Thakral, G.K. Sharma |
Published in: |
(2006).ECMS
2006 Proceedings edited by: W. Borutzky, A. Orsoni, R. Zobel. European
Council for Modeling and Simulation. doi:10.7148/2006 ISBN:
0-9553018-0-7 20th
European Conference on Modelling and Simulation, Bonn,
May 28-31, 2006 |
Citation
format: |
Goyal, A., Thakral,
A., & Sharma, G. K. (2006). Improved A* Algorithm For Query Optimization.
ECMS 2006 Proceedings edited by: W. Borutzky, A. Orsoni, R. Zobel
(pp. 472-478). European Council for Modeling and Simulation. doi:10.7148/2006-0472 |
DOI: |
http://dx.doi.org/10.7148/2006-0472 |
Abstract: |
Exponential
growth in number of possible strategies with the increase in number of
relations in a query has been identified as a major problem in the field of
query optimization of relational databases. Present database systems use
exhaustive search to find the best possible strategy. But as the size of a
query grows, exhaustive search method itself becomes quite expensive. Other algorithms like A* algorithm, Simulated Annealing etc. have
been suggested as a solution. However, all these algorithms fail to produce
the best results; necessarily required for query execution. We did some modifications to the A* algorithm to
produce a randomized form of the algorithm and compared it with the original
A* algorithm and exhaustive search. The comparison results have shown
improved A* algorithm to be almost equivalent in output quality along with a colossal
decrease in search space in comparison to exhaustive search method. |
Full
text: |