ecms_neu_mini.png

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: