
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:
0955301807 20^{th}
European Conference on Modelling and Simulation, Bonn,
May 2831, 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. 472478). European Council for Modeling and Simulation. doi:10.7148/20060472 
DOI: 
http://dx.doi.org/10.7148/20060472 
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: 