Dağıtık veri tabanı sistemlerinde veri dilimleme algoritmaları

Abstract

ÖZET DAĞITIK VERİ TABANI SİSTEMLERİNDE VERİ DİLİMLEME ALGORİTMALARI Dağıtık veritabanı sistemlerinde veri dağıtımı bazı statik veri erişim kalıplarına göre veri tabam tasarımından önce yapılmaktaydı. Ancak veri erişim kalıplan değiştiği zaman statik yöntemler veritabanı sisteminin performansım oldukça düşürmektedir. Bu çalışmada, tekrarsız dağıtık veritabanı sistemleri için daha önce literatürde mevcut olmayan dinamik bir veri dağıtım algoritması önerilmiştir, önerilen algoritmada bir düğüm, o an kendisinde bulunan bir veritabanı parçasını, parçaya hiç yerel erişim yapılmaksızın ardarda yapılan uzak erişimler belli bir eşik değerini aştığında son erişim yapan düğüme gönderir. Bu algoritma her düğümde bağımsız olarak işleme yaptığından dolayı dağıtık olarak çalışmaktadır. önerilen eşik algoritması herhangi bir parçanın veritabanındaki durumunu göstermek için sonlu Markov zinciriyle modellenmiştir. Modelde düğümlerin parçaya erişim olasılıkları sabit olarak alınmıştır. Literatürde ilk kez oluşturulan bu modelde parçaya erişim olasılığı diğerlerinden farklı olan bir düğüm haricinde bütün düğümlerin parçaya erişim olasılıklarının eşit olduğu özel bir durum çözümlenmiştir. Bu özel durum için, eşik değeri ve düğümlerin parçaya erişim olasılıkları cinsinden, parçanın düğümlerde bulunma denge olasılıklarını gösteren genel formüller çıkarılmıştır. Daha sonra bu formüller kullanılarak pozitif eşik değerleri için parçanın büyük olasılıkla erişen düğümde, bu düğümün erişim olasılığından daha büyük bir olasılıkla kaldığı gösterilmiştir. Ayrıca eşik değeri büyüdükçe parçanın büyük olasılıkla erişen düğümde kalmaya daha fazla meyilli olduğu gösterilmiştir. Eşik algoritması özellikle, her parça için bir düğümün parçaya erişim olasılığının diğerlerinden büyük olduğu dağıtık veritabanı sistemleri için oldukça uygundur. VI

ABSTRACT DATA ALLOCATION ALGORITHMS IN DISTRIBUTED DATABASE SYSTEMS Data allocation in distributed database systems (DDS) has been done prior to the design of database depending on some static data access patterns. But the performance of these systems degrades drastically due to the changing data access patterns over time. In this dissertation, a new dynamic data allocation algorithm for non-replicated DDSs is proposed to reallocate data continuously for changing data access patterns. In the suggested algorithm, each node autonomously decides whether to transfer the ownership of a fragment in database to another node depending on the past accesses on the fragment. Each fragment continuously migrates from the node where it is not accessed locally more than a certain number of past accesses, namely the threshold value. The algorithm based on threshold values is modeled for a fragment of database as unite Markov chain with constant node access probabilities. In the model, a special case, where all nodes have equal access probabilities except one with a different access probability, is analyzed. General formulas, which show the steady-state probabilities that a fragment is in each node in terms of threshold value and access probabilities of nodes, are obtained for this special case. It has been shown mat for positive threshold values fragment will remain at the node with the higher access probability with a probability higher than the access probability. It has also been shown that the greater the threshold values are, the greater the tendency of the fragment to remain at the node with higher access probability will be. The algorithm is especially suitable for a DDS where for each fragment the access probability of one node is larger than the other nodes. vn