Dynamic Programming with Ant Colony Optimization Metaheuristic for Optimization of Distributed Database Queries

Dokeroglu T., COŞAR A.

26th Annual International Symposium on Computer and Information Science, London, Canada, 26 - 28 September 2011, pp.107-113 identifier

  • Publication Type: Conference Paper / Full Text
  • Doi Number: 10.1007/978-1-4471-2155-8_13
  • City: London
  • Country: Canada
  • Page Numbers: pp.107-113
  • Keywords: Query optimization, Dynamic programming, Ant colony, Metaheuristic
  • Middle East Technical University Affiliated: Yes


In this paper, we introduce and evaluate a new query optimization algorithm based on Dynamic Programming (DP) and Ant Colony Optimization (ACO) metaheuristic for distributed database queries. DP algorithm is widely used for relational query optimization, however its memory, and time requirements are very large for the query optimization problem in a distributed database environment which is an NP-hard combinatorial problem. Our aim is to combine the power of DP with heuristic approaches so that we can have a polynomial time approximation algorithm based on a constructive method. DP and ACO algorithms together provide execution plans that are very close to the best performing solutions, and achieve this in polynomial time. This makes our algorithm viable for large multi-way join queries.