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, Kanada, 26 - 28 Eylül 2011, ss.107-113 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Doi Numarası: 10.1007/978-1-4471-2155-8_13
  • Basıldığı Şehir: London
  • Basıldığı Ülke: Kanada
  • Sayfa Sayıları: ss.107-113
  • Anahtar Kelimeler: Query optimization, Dynamic programming, Ant colony, Metaheuristic
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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.