Tez No İndirme Tez Künye Durumu
255256
Genetic algorithms for distributed database design and distributed database query optimization / Dağınık veritabanı tasarımı için genetik algoritma ve dağınık veritabanı sorgu optimizasyonu
Yazar:ENDER SEVİNÇ
Danışman: DOÇ. DR. AHMET COŞAR
Yer Bilgisi: Orta Doğu Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin:Dağıtık veri tabanı sistemleri = Distributed database systems ; Genetik algoritmalar = Genetic algorithms ; Mutasyon = Mutation ; Sorgu optimizasyonu = Query optimization ; Çaprazlama = Crossing
Onaylandı
Doktora
İngilizce
2009
96 s.
Bilgisayarların artan performansı, düşen fiyatlar, ucuz ATM geniş alan ağlarına ve gibabit Ethernet'li yerel alan ağlarına bağlanabilen sistemler dağınık veritabanı sistemlerini dikkat çekici kılmaktadır. Bununla birlikte, dağınık veritabanı sorgu optimizasyonu hala kısıtlayıcı bir faktördür. Merkezi veritabanı sorgu optimizasyonunda kullanılan dinamik programlama gibi en iyiyi bulan teknikler artan problem boyutu sebebiyle efektif değildir. Yeni geliştirilen genetik algoritma (GA) tabanlı optimizasyon teknikleri gelecek vaadeden bir alternatiftir. En iyi bilinen GA'yı rasgele çalışan bir teknikle kıyasladık ve bunun, neredeyse eşit sayıda üretilen rasgele çözümlerden daha iyiyi başaramadığının gösterdik. Sonrasında, GA'nın kullandığı parametre setini inceledik ve deneysel olarak, hangi parametrelerin bütün performansta etkili olduğunu gösterdik.Bizim GA'da tanımlanan yeni mutasyon ve çaprazlama operatörleri deneysel olarak artan sayıda tabloların ve sitelerin olduğu suni dağınık veritabanında analiz edildi. Bu suni veritabanında tabloların kopyaları olmakla beraber, yatay/dikey bölümleme yoktu. N sayıda bölümlü bir tabloyu ihtive eden bir select-project-join sorgusu, N sayıda tabloyu ihtiva eden bir sorguya dönüştürülebilir. Tüm olasılıkların hesaplandığı en iyi sonuçlar, bizim yeni GA formülasyonumuzdan %20 daha iyiyken, önceden bilinen GA tabanlı çözümden %50 daha iyidir.
The increasing performance of computers, reduced prices and ability to connect systems with low cost gigabit ethernet LAN and ATM WAN networks make distributed database systems an attractive research area. However, the complexity of distributed database query optimization is still a limiting factor. Optimal techniques, such as dynamic programming, used in centralized database query optimization are not feasible because of the increased problem size. The recently developed genetic algorithm (GA) based optimization techniques presents a promising alternative. We compared the best known GA with a random algorithm and showed that it achieves almost no improvement over the random search algorithm generating an equal number of random solutions. Then, we analyzed a set of possible GA parameters and determined that two-point truncate technique using GA gives the best results.New mutation and crossover operators defined in our GA are experimentally analyzed within a synthetic distributed database having increasing the numbers of relations and nodes. The designed synthetic database replicated relations, but there was no horizontal/vertical fragmentation. We can translate a select-project-join query including a fragmented relation with N fragments into a corresponding query with N relations. Comparisons with optimal results found by exhaustive search are only 20% off the results produced by our new GA formulation showing a 50% improvement over the previously known GA based algorithm.