Cellary / Morzy / Gelenbe Concurrency Control in Distributed Database Systems

1. Auflage 2014
ISBN: 978-1-4832-9464-3
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band Volume 3, 365 Seiten, Web PDF

Reihe: Studies in Computer Science and Artificial Intelligence

Distributed Database Systems (DDBS) may be defined as integrated database systems composed of autonomous local databases, geographically distributed and interconnected by a computer network.The purpose of this monograph is to present DDBS concurrency control algorithms and their related performance issues. The most recent results have been taken into consideration. A detailed analysis and selection of these results has been made so as to include those which will promote applications and progress in the field. The application of the methods and algorithms presented is not limited to DDBSs but also relates to centralized database systems and to database machines which can often be considered as particular examples of DDBSs.The first part of the book is devoted to basic definitions and models: the distributed database model, the transaction model and the syntactic and semantic concurrency control models. The second discusses concurrency control methods in monoversion DDBSs: the locking method, the timestamp ordering method, the validation method and hybrid methods. For each method the concept, the basic algorithms, a hierarchical version of the basic algorithms, and methods for avoiding performance failures are given. The third section covers concurrency control methods in multiversion DDBSs and the fourth, methods for the semantic concurrency model. The last part concerns performance issues of DDBSs.The book is intended primarily for DDBMS designers, but is also of use to those who are engaged in the design and management of databases in general, as well as in problems of distributed system management such as distributed operating systems and computer networks.

Autoren/Hrsg.

Cellary, W.

Morzy, T.

Gelenbe, E.

Inhaltsverzeichnis

1;Front Cover;1
2;Concurrency Control in Distributed Database Systems;4
3;Copyright Page;5
4;Table of Contents;8
5;Preface;12
6;Part I: Basic Definitions and Models;18
6.1;Chapter 1. Distributed Database System Model;20
6.1.1;1.1 Distributed Database Model;20
6.1.2;1.2 Distributed Database Consistency;23
6.1.3;1.3 Transaction Model;25
6.1.4;1.4 Distributed Database System Architecture;31
6.2;Chapter 2. Concurrency Control Models;38
6.2.1;2.1 Serializability;39
6.2.2;2.2 Multiversion Serializability;49
6.2.3;2.3 Multilevel Atomicity;61
6.2.4;2.4 Relationships Between Concurrency Control Models;78
6.3;Chapter 3. DDBS Performance Failures;84
7;Part II: Concurrency Control Method s for the Serializability Mode l;94
7.1;Chapter 4. Locking Method;96
7.1.1;4.1 Locking Concept;96
7.1.2;4.2 Two-Phase Locking Algorithm;99
7.1.3;4.3 Non Two-Phase Locking Algorithms;101
7.1.4;4.4 Hierarchical Locking Algorithms;119
7.1.5;4.5 Performance Failures in the Locking Method;128
7.2;Chapter 5. Timestamp Ordering Method;142
7.2.1;5.1 Timestamp Ordering Concept;142
7.2.2;5.2 Basic Timestamp Ordering Algorithm;144
7.2.3;5.3 Conservative Timestamp Ordering Algorithm;151
7.2.4;5.4 Hierarchical Timestamp Ordering Algorithm;160
7.2.5;5.5 Performance Failures in the Timestamp Ordering Method;163
7.3;Chapter 6. Validation Method;166
7.3.1;6.1 Validation Concept;166
7.3.2;6.2 Kung-Robinson Validation Algorithm;168
7.3.3;6.3 Snapshot Validation Algorithm;173
7.3.4;6.4 Hierarchical Validation Algorithm;177
7.3.5;6.5 Performance Failures in the Validation Method;180
7.4;Chapter 7. Hybrid Methods;184
7.4.1;7.1 Basic concepts;184
7.4.2;7.2 The SABRE System Algorithm;184
7.4.3;7.3 Bi-ordering Locking Algorithm;190
7.4.4;7.4 Performance Failures in Hybrid Methods;197
8;Part III: Concurrency Control Method s for the Multiversion Serializability Model;198
8.1;Chapter 8. Multiversion Locking Method;200
8.1.1;8.1 Multiversion Locking Algorithm;200
8.1.2;8.2 Non-Two-Phase Multiversion Locking Algorithms;216
8.1.3;8.3 Performance Failures in the Multiversion Locking Method;226
8.2;Chapter 9. Multiversion Timestamp Ordering Method;228
8.2.1;9.1 Reed's Algorithm;228
8.2.2;9.2 Timepad Algorithm;231
8.2.3;9.3 Hierarchical Multiversion Timestamp Ordering Algorithm;238
8.2.4;9.4 Performance Failures in the Multiversion Timestamp Ordering Method;243
8.3;Chapter 10. Multiversion Validation Method;246
8.3.1;10.1 Multiversion Validation Algorithm;246
8.3.2;10.2 Performance Failures in the Multiversion Validation Method;255
9;Part IV: Concurrency Control Methods for the Multilevel Atomicity Model;256
9.1;Chapter 11. Garcia-Molina's Locking Method;258
9.1.1;11.1 Concept;258
9.1.2;11.2 Algorithm;259
9.2;Chapter 12. Abstract Dat a Type Synchronization Method;274
9.2.1;12.1 Concept;274
9.2.2;12.2 Algorithm;286
10;Part V: Performance Issues in the Concurrent Access to Data;292
10.1;Chapter 13. Introduction to Performance Issues in DDBSs;294
10.2;Chapter 14. A Global Approach to the Evaluation of Overload Caused by Concurrency Control Algorithms in DDBSs;298
10.2.1;14.1 The Mathematical Model of Global Performance;300
10.2.2;14.2 Analysis of the Effect of the Transaction Arrival Rate on;301
10.2.3;14.3 The Effect of the Concurrency Control Algorithm on the Transaction Processing Capacity;303
10.3;Chapter 15. Performance Evaluation of a Global Locking Policy;306
10.3.1;15.1 The Model Assumptions;306
10.3.2;15.2 The Exponential Model;308
10.4;Chapter 16. Modelling the Parallel Access of Transactions to Common Granular Data;312
10.4.1;16.1 An Isolated Transaction;313
10.4.2;16.2 Equations for F and F;319
10.4.3;16.3 Existence of a Solution;321
10.4.4;16.4 Comparison with Simulation Results;322
10.4.5;16.5 Non-uniform Access Probabilities to Granules;322
10.5;Chapter 17. Performance Evaluation of Resequencing Algorithms;328
10.5.1;17.1 The Mathematical Model;329
10.5.2;17.2 Analysis of the Model;330
10.5.3;17.3 Practical Implications of the Analysis;335
10.5.4;17.4 The Total Delay Equation of the Resequencing Algorithm;337
10.5.5;17.5 Total Delay Analysis;339
11;Bibliography;348