ΠΡΟΒΛΗΜΑΤΑ ΣΥΝΤΟΝΙΣΜΟΥ ΤΑΥΤΟΧΡΟΝΩΝ ΠΡΟΣΠΕΛΑΣΕΩΝ ΣΕ ΒΑΣΕΙΣ ΔΕΔΟΜΕΝΩΝ

Abstract

THIS THESIS DEALS WITH SOME ISSUES IN CONCURRENCY CONTROL OF DATABASE ACCESSES. MULTIVERSION SCHEDULERS ARE NOW A WIDELY ACCEPTED METHOD FOR ENHANCING THE PERFORMANCE OF THE CONCURRENCY CONTROL COMPONENT OF A DATABASE. IN THE 2ND CHAPTER OF THE THESIS WE INTRODUCE A NEW NOTION OF MULTIVERSION SERIALIZABILITY (MVSR) BASED ON CONFLICTS (MVCSR) AND DISCUSS ITS RELATION WITH THE WELL KNOWN SINGLE VERSION CONFLICT SERIALIZABILITY (CSR). WE PROVE THAT IT IS NP-COMPLETE TO DECIDE WHETHER A SET OF SCHEDULES IS ON-LINE SCHEDULABLE (OLS). WE INTRODUCE THE CONCEPT OF MAXIMAL OLS SETS AND SHOW THAT NO EFFICIENT SCHEDULER CAN BEDESGNED THAT RECOGNIZES MAXIMAL SUBSETS OF MVSR OR MVCSR. FINALLY A GENERAL FRAMEWORK FOR ALGORITHMS BASED ON MVCSR IS PRESENTED. IN CHAPTER 3 WE SOLVE AN OPEN PROBLEM FOR THE WELL KNOWN CONFLICT GRAPH SCHEDULER: WHEN CAN A NODE BE DELETED FROM THE GRAPH AFTER THE COMPLETION OF THE CORRESPONDING TRANSACTION? WE GIVE A SUFFICIENT AND NECESSARY CONDITION FOR THIS. WE EXAMINE THE DYNAMIC PROBLEM, I.E. REPEATEDLY DELETING NODES AS THE SCHEDULE PROCEEDS AND WE STUDY THE PROBLEM UNDER SEVERAL VARIATIONS OF THE TRANSACTIONS MODEL.

ΣΤΗ ΔΙΑΤΡΙΒΗ ΑΥΤΗ ΜΕΛΕΤΟΥΜΕ ΠΡΟΒΛΗΜΑΤΑ ΣΥΝΤΟΝΙΣΜΟΥ ΤΑΥΤΟΧΡΟΝΩΝ ΠΡΟΣΠΕΛΑΣΕΩΝ ΣΕΒΑΣΕΙΣ ΔΕΔΟΜΕΝΩΝ. ΟΙ ΣΥΝΤΟΝΙΣΤΕΣ ΜΕ ΑΝΤΙΓΡΑΦΑ ΕΙΝΑΙ ΗΔΗ ΕΝΑΣ ΠΛΑΤΙΑ ΑΠΟΔΕΚΤΟΣΜΗΧΑΝΙΣΜΟΣ ΓΙΑ ΒΕΛΤΙΩΣΗ ΤΗΣ ΑΠΟΔΟΣΗΣ ΤΟΥ ΣΥΝΤΟΝΙΣΜΟΥ. ΣΤΟ ΚΕΦΑΛΑΙΟ 2 ΤΗΣ ΔΙΑΤΡΙΒΗΣ ΕΙΣΑΓΟΥΜΕ ΜΙΑ ΝΕΑ ΕΝΝΟΙΑ ΣΕΙΡΙΟΠΟΙΗΣΙΜΟΤΗΤΑΣ ΜΕ ΑΝΤΙΓΡΑΦΑ (MVSR) ΠΟΥ ΒΑΣΙΖΕΤΑΙ ΣΤΗΝ ΕΝΝΟΙΑ ΤΗΣ ΑΝΤΙΘΕΣΗΣ (MVCSR) ΚΑΙ ΜΕΛΕΤΟΥΜΕ ΤΗ ΣΧΕΣΗ ΤΗΣ ΜΕ ΤΗΝ ΚΛΑΣΣΙΚΗ ΕΝΝΟΙΑ ΤΗΣ ΑΝΤΙΘΕΣΗΣ ΧΩΡΙΣ ΑΝΤΙΓΡΑΦΑ (CSR). ΑΠΟΔΕΙΚΝΥΟΥΜΕ ΟΤΙ ΤΟ ΠΡΟΒΛΗΜΑ ΤΟΥ ΑΝ ΕΝΑ ΣΥΝΟΛΟ ΧΡΟΝΙΚΩΝ ΕΙΝΑΙ ΕΠΙΤΟΠΟΥ ΣΥΝΤΟΝΙΣΙΜΟ (ΕΤΣ) ΕΙΝΑΙ ΠΛΗΡΕΣ ΣΤΟΝΡ. ΕΙΣΑΓΟΥΜΕ ΤΗΝ ΕΝΝΟΙΑ ΤΩΝ ΜΕΓΙΣΤΩΝ ΕΤΣ ΣΥΝΟΛΩΝ ΧΡΟΝΙΚΩΝ ΚΑΙ ΑΠΟΔΕΙΚΝΥΟΥΜΕΟΤΙ ΕΙΝΑΙ ΑΔΥΝΑΤΗ Η ΚΑΤΑΣΚΕΥΗ ΑΠΟΔΟΤΙΚΩΝ ΣΥΝΤΟΝΙΣΤΩΝ ΠΟΥ ΝΑ ΑΝΑΓΝΩΡΙΖΟΥΝ ΜΕΓΙΣΤΑ ΕΤΣ ΥΠΟΣΥΝΟΛΑ ΤΟΥ MVSR # ΤΟΥ MVCSR. ΤΕΛΟΣ ΠΑΡΟΥΣΙΑΖΟΥΜΕ ΕΝΑ ΓΕΝΙΚΟ ΑΛΓΟΡΙΘΜΙΚΟ ΠΛΑΙΣΙΟ ΓΙΑ ΣΥΝΤΟΝΙΣΤΕΣ MVCSR. ΣΤΟ 3 ΚΕΦΑΛΑΙΟ ΛΥΝΟΥΜΕ ΤΟ ΠΡΟΒΛΗΜΑ ΤΟΥ ΚΛΕΙΣΙΜΑΤΟΣ ΔΟΣΟΛΗΨΙΩΝ ΓΙΑ ΤΟ ΓΝΩΣΤΟ ΣΥΝΤΟΝΙΣΤΗ ΓΡΑΦΟΥ ΑΝΤΙΘΕΣΕΩΝ. ΤΟ ΠΡΟΒΛΗΜΑ ΕΙΝΑΙ: ΠΟΤΕ ΜΠΟΡΕΙ ΝΑ ΔΙΑΓΡΑΦΕΙ ΕΝΑΣ ΚΟΜΒΟΣ ΑΦΟΥ Η ΑΝΤΙΣΤΟΙΧΗ ΔΟΣΟΛΗΨΙΑ ΕΧΕΙ ΟΛΟΚΛΗΡΩΘΕΙ; ΒΡΙΣΚΟΥΜΕ ΜΙΑ ΑΝΑΓΚΑΙΑ ΚΑΙ ΙΚΑΝΗ ΣΥΝΘΗΚΗ ΓΙ'ΑΥΤΟ. ΜΕΛΕΤΟΥΜΕ ΤΟ ΔΥΝΑΜΙΚΟ ΠΡΟΒΛΗΜΑ ΤΗΣ ΚΑΤΕΠΑΝΑΛΗΨΗ ΔΙΑΓΡΑΦΗΣ ΚΟΜΒΩΝ ΟΣΟ ΠΡΟΧΩΡΕΙ ΤΟ ΧΡΟΝΙΚΟ ΚΑΙ ΜΕΛΕΤΟΥΜΕ ΤΟ ΠΡΟΒΛΗΜΑ ΤΟΥ ΚΛΕΙΣΙΜΑΤΟΣ ΓΙΑ ΟΡΙΣΜΕΝΕΣ ΠΑΡΑΛΛΑΓΕΣ ΤΟΥ ΜΟΝΤΕΛΟΥ ΤΩΝ ΔΟΣΟΛΗΨΙΩΝ.