Dynamic Programming with Ant Colony Optimization Metaheuristic for Optimization of Distributed Database Queries
26th International Symposium on Computer and Information Sciences, ISCIS 2011, London, İngiltere, 26 - 28 Eylül 2011, ss.107-113, (Tam Metin Bildiri)
- 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: İngiltere
- Sayfa Sayıları: ss.107-113
- Anahtar Kelimeler: Ant colony, Dynamic programming, Metaheuristic, Query optimization
- TED Ü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.