Contributions to the theory of database concurrency control

Abstract

ÖZET VERİ TABANI EŞZAMANLILIK KONTROLÜ TEORİSİNE KATKILAR HALICI, Uğur Doktora Tezi, Elektrik ve Elektronik Mühendisliği Tez Yöneticisi: Doç. Dr. Asuman Dogac Şubat 1988, 158 Sayfa Veritabanı eşzamanlılık kontrolü, kullanıcıların veritabanına eşzamanlı olarak erişimlerini düzenler. Veritabanı eşzamanlılık kontrolü, veritabanında kararlılığının sağlanması acısından önemlidir. Sıralanabiliri ik, eşzamanlı kullanıcı erişimlerinin doğruluğunu deneyen bir ölçüttür. Bir işletim süresince çalışan islembilgilerin veri tabanı üzerinde yaptığı işlemleri sırası ile gösteren diziye günlük denilmektetir. Bir günlüğün sıralanabil iri iğine karar verilmesi polinom zamanda çözülemeyen (NP_complete) bir problemdir. Veritabanlarındaki eşzamanlılık kontrolü sahasındaki teorik araştırmaların önemli bir kısmı elemanları polinom zamanda denenebilen <P> daha büyük sıralanabilir günlük sınıfları geliştirmek üzerinedir. Eşzamanlılık kontrolü sahasındaki diğer bir araştırma sahası ise dağıtık ver itabanları için daha fazla eşzamanlılık sağlayan ve daha az iletişim gerektiren daha basit eşzamanlılık kontrol yöntemleri geliştirilmesidir. Bu tezde, dağıtık veri tabanları için üç yeni eşzamanlılık kontrol yöntemi, isimleriyle Optimistic Method with Dummy Locks -vi-(ODD, Ordering by Serialization Numbers (OSN) ve Write_Read_From_Write Graph Testing (WRFWGT) yöntemleri, tanı ti Imıştır. ODL yöntemi, KO yönteminden daha fazla eşzamanlılık sağlarken, en çok kullanılan veritabanı eşzamanlılık kontrol yOntemi SPL ile aynı günlük sınıfına sahiptir. QDL yöntemi EPL ve KO yöntemlerinden daha basittir ve daha az iletişim gerektirir. SPL yönteminde kilit kullanımı nedeni ile kilitlenme büyük bir problem oluştururken ODL yönteminde kilitlenme sorunu yoktur. OSN yöntemi, Zaman Aralığı tekniği ile kilitleme tekniğini birleştirmektedir. OSN yönteminin günlük sınıfı ODL ve BTO yöntemlerinin günlük sınıflarından daha büyüktür. OSN yöntemi ODL yöntemi ile aynı sayıda mesaj gerektirir ve OSN yönteminde de kilitlenme sorunu yoktur. WRFWGT yöntemi, WRFW adı verilen bir çizgede dönüş olup olmadığına bakarak çalışmaktadır. WRFWGT metoduna karşılık gelen ve PCWRFW adı verilen günlük sınıfı, bir düzenleyici tarafından üretilebilir olarak bilinen en büyük günlük sınıfı CPSR'dan daha büyüktür. PCWRFW günlük sınıfı, WRFW günlük sınıfının önek kapalı alt sınıfıdır ve WRFW günlük sınıfı, P'de bilinen en büyük sıralanabilir günlük sınıfı WRW ile çakışmaktadır. Bu tezin en önemli katkısı, sıralanabil ir lik teorisine yapılan katkıdır. Günlükler üzerine tanımlanan NP 'deki Günlüklerin Sıralanabilirligi problemi, bir Kümenin verilen Sıralama Kısıtlamaları ile Sıralanabilirligi problemine indirgenmiştir. Kümelerin Sıralanabilirligi üzerine geliştirilen teori kullanılarak, -vıı-Kümenin Sıralanabil iri igi Probleminin NP olmadığı durumlar bulunmuştur. Günlüklerin Sıralanabi 1 iri iğinin gerektirdiği şartlar, günlükteki işlembilgi kümesi üzerinde sıralama kısıtlaması olarak ifade edilerek Günlüklerin Sıralanabilirligi ile geliştirilen Kümelerin Sıralanabilirligi Teorisi arasındaki ilişki kurulmuştur. Geliştirilen teori yardımı ile yeni bir sıralanabilir günlük sınıfı HD tanımlanmış ve yine geliştirilen teori yardımıyla HD günlük sınıfının P'de bilinen en büyük sıralanabilir günlük sınıfı olduğu ispatlanmıştır. Final state serial izabil ity (FSR) yi doğruluk ölçütü kabul eden diğer bir günlük sınıfı tanımlanmıştir. Ayrıca HD günlük sınıfının önek kapalı alt sınıfı PCHD'nin bir düzenleyici tarafından üretilebilir en büyük sıralanabilir günlük sınıfı olduğu ispatlanmıştır. Anahtar Kelimeler: dagıtık veritabanı sistemleri, veri tabanı sistemlerinde eşzamanlılık kontrolü, veritabanı günlükleri, veritabanı günlüklerinin sıralanabilirligi, düzenleyiciler -vı ıı-

ABSTRACT CONTRIBUTIONS TO THE THEORY OF DATABASE CONCURRENCY CONTROL HALICI, Ugur Ph.D. in Electrical and Electronics Engineering Supervisor: Assoc. Prof. Dr. Asuman Dogac February 1988, 158 pages Database concurrency control synchronizes the concurrent user accesses to the database. The database concurrency control is important to provide for the consistency of the database. Serializability is a criterion to test the correctness of concurrent user accesses. The sequence representing the order of user accesses to the database during an execution is called a history. To test whether a history is serializable is an NP^complete problem. An important part of the theoretical research on the database concurrency control is on developing larger serializable history classes such that the membership test for that history class is in P. The size of an history class represents the amount of concurrency provided by the class. Another research area in the concurrency control field for distributed database systems is the development of simpler concurrency control methods which provide more concurrency and require less communication. In this thesis, three concurrency control methods, namely the Optimistic Method with Dummy Locks (ODD, the Ordering by Serialization Numbers (OSN) method and the Wr ite_Read_From_Write -in-Graph Testing (WRFWGT) Method are introduced for distributed database systems. The ODL method, has the same history class as the most common database concurrency control method SPL, while it provides more concurrency than KO method. The ODL method is simpler than 2PL and KO methods and it requires less communication than 2PL and KO methods. Since locks are used, deadlock is an important problem to be handled with 2PL method. However the ODL method is deadlock free. The OSN method, combines time interval technique with locking. The history class of the OSN method is larger than the history classes of the ODL and the BTO methods. The OSN method requires the same number of messages as the ODL method and the OSN method is also deadlock free. The WRFWGT method works by explicitly checking the cycles of a graph called the WRFW graph. The history class corresponding to the WRFWGT method, called the class PCWRFW, is larger than the class CPSR, which is the largest known history class applicable for scheduling. The PCWRFW class is the prefix closed subset of the class WRFW and the WRFW class coincides with the class WRW, which is the largest known serial izable history class in P. The major contribution of this thesis is to the theory of serializability. The NP_complete problem of ser ial izabili ty of database histories is reduced to the problem of serializability of a set with a given ordering constraint. The special cases for which the Serializability Problem of Sets is not in NP are found by using the theory developed on the serializability of sets. -iv-The serial izability theory of sets is related to the theory of serializability of database histories by expressing the requirements of the serializability of database histories as ordering constraints on the transaction sets induced by the histories. A new history class, called the HD class, is defined by using the developed theory and it has-been proved that the class HD is the largest known serializable history class in P again by using the developed theory. Also the class FHD, which assumes final state serializability as correctness criterion is defined. Furthermore, it is proved that the prefix closed subclass of the class HD, called the PCHD class, is the largest known history class applicable for schedul ing. Key words: distributed databases system, concurrency control in database systems, database histories, serializability of database histories, schedulers