Concurrency Control in Distributed Database Systems (eBook)

W. Cellary, E. Gelenbe, T. Morzy (Autoren)

eBook Download: PDF

2014 | 1. Auflage
365 Seiten
Elsevier Science (Verlag)
978-1-4832-9464-3 (ISBN)

Infos

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.

Inhalt

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

Produkt-Details

• Erscheint lt. Verlag: 28.6.2014
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Betriebssysteme / Server
• Themenwelt: Mathematik / Informatik ► Informatik ► Datenbanken
• Themenwelt: Informatik ► Theorie / Studium ► Künstliche Intelligenz / Robotik
• Themenwelt: Sozialwissenschaften ► Kommunikation / Medien ► Buchhandel / Bibliothekswesen
• ISBN-10: 1-4832-9464-1 / 1483294641
• ISBN-13: 978-1-4832-9464-3 / 9781483294643