Transactional Information Systems

Foreword byGray, Microsoft, Inc.PrefacePART ONE - BACKGROUND AND MOTIVATIONChapter 1 What Is It All About?1.1 Goal and Overview1.2 Application Examples1.2.1 Online Transaction Processing: Debit/Credit Example1.2.2 Electronic Commerce Example1.2.3 Workflow Management: Travel Planning Example1.3 System Paradigms1.3.1 Three-Tier and Two-Tier Architectures1.3.2 Federations of Servers1.4 Virtues of the Transaction Concept1.4.1 Transaction Properties and the Transaction Programming Interface1.4.2 Requirements on Transactional Servers1.5 Concepts and Architecture of Database Servers1.5.1 Architectural Layers of Database Systems1.5.2 How Data Is Stored1.5.3 How Data Is Accessed1.5.4 How Queries and Updates Are Executed1.6 Lessons LearnedExercisesBibliographic NotesChapter 2 Computational Models2.1 Goal and Overview2.2 Ingredients2.3 The Page Model2.4 The Object Model2.5 Road Map of the Book2.6 Lessons LearnedExercisesBibliographic NotesPART TWO - CONCURRENCY CONTROLChapter 3 Concurrency Control: Notions of Correctness for the Page Model3.1 Goal and Overview3.2 Canonical Concurrency Problems3.3 Syntax of Histories and Schedules3.4 Correctness of Histories and Schedules3.5 Herbrand Semantics of Schedules3.6 Final State Serializability3.7 View Serializability3.7.1 View Equivalence and the Resulting Correctness Criterion3.7.2 On the Complexity of Testing View Serializability 3.8 Conflict Serializability3.8.1 Conflict Relations 3.8.2 Class CSR 3.8.3 Conflicts and Commutativity 3.8.4 Restrictions of Conflict Serializability3.9 Commit Serializability3.10 An Alternative Correctness Criterion: Interleaving Specifications3.11 Lessons LearnedExercisesBibliographic NotesChapter 4 Concurrency Control Algorithms4.1 Goal and Overview4.2 General Scheduler Design4.3 Locking Schedulers4.3.1 Introduction 4.3.2 The Two-Phase Locking Protocol 4.3.3 Deadlock Handling 4.3.4 Variants of 2PL 4.3.5 Ordered Sharing of Locks4.3.6 Altruistic Locking4.3.7 Non-Two-Phase Locking Protocols4.3.8 On the Geometry of Locking4.4 Nonlocking Schedulers4.4.1 Timestamp Ordering 4.4.2 Serialization Graph Testing4.4.3 Optimistic Protocols 4.5 Hybrid Protocols4.6 Lessons LearnedExercisesBibliographic NotesChapter 5 Multiversion Concurrency Control5.1 Goal and Overview5.2 Multiversion Schedules5.3 Multiversion Serializability5.3.1 Multiversion View Serializability5.3.2 Testing Membership in MVSR 5.3.3 Multiversion Conflict Serializability5.4 Limiting the Number of Versions5.5 Multiversion Concurrency Control Protocols5.5.1 The MVTO Protocol5.5.2 The MV2PL Protocol 5.5.3 The MVSGT Protocol 5.5.4 A Multiversion Protocol for Read-Only Transactions5.6 Lessons LearnedExercisesBibliographic NotesChapter 6 Concurrency Control on Objects: Notions of Correctness6.1 Goal and Overview6.2 Histories and Schedules6.3 Conflict Serializability for Flat Object Transactions6.4 Tree Reducibility6.5 Sufficient Conditions for Tree Reducibility6.6 Exploiting State Based Commutativity6.7 Lessons LearnedExercisesBibliographical NotesChapter 7 Concurrency Control Algorithms on Objects7.1 Goal and Overview7.2 Locking for Flat Object Transactions7.3 Layered Locking7.4 Locking on General Transaction Forests7.5 Hybrid Algorithms7.6 Locking for Return Value Commutativity and Escrow Locking7.7 Lessons LearnedExercisesBibliographic NotesChapter 8 Concurrency Control on Relational Databases8.1 Goal and Overview8.2 Predicate-Oriented Concurrency Control8.3 Relational Update Transactions8.3.1 Syntax and Semantics 8.3.2 Commutativity and Simplification Rules 8.3.3 Historiesand Final State Serializability 8.3.4 Conflict Serializability 8.3.5 Extended Conflict Serializability 8.3.6 Serializability in the Presence of Functional Dependencies 8.3.7 Summary 8.4 Exploiting Transaction Program Knowledge8.4.1 Motivating Example 8.4.2 Transaction Chopping 8.4.3 Applicability of Chopping 8.5 Lessons LearnedExercisesBibliographic NotesChapter 9 Concurrency Control on Search Structures9.1 Goal and Overview9.2 Implementation of Search Structures by B+ Trees9.3 Key Range Locking at the Access Layer9.4 Techniques for the Page Layer9.4.1 Lock Coupling9.4.2 Link Technique9.4.3 Giveup Technique9.5 Further Optimizations9.5.1 Deadlock-Free Page Latching9.5.2 Enhanced Key Range Concurrency 9.5.3 Reduced Locking Overhead 9.5.4 Exploiting Transient Versioning9.6 Lessons LearnedExercisesBibliographic NotesChapter 10 Implementation and Pragmatic Issues10.1 Goal and Overview10.2 Data Structures of a Lock Manager10.3 Multiple Granularity Locking and Dynamic Escalation10.4 Transient Versioning10.5 Nested Transactions for Intra-transaction Parallelism10.6 Tuning Options10.6.1 Manual Locking10.6.2 SQL Isolation Levels 10.6.3 Short Transactions 10.6.4 Limiting the Level of Multiprogramming10.7 Overload Control10.7.1 Feedback-Driven Method10.7.2 Wait-Depth Limitation10.8 Lessons LearnedExercisesBibliographic NotesPART THREE - RECOVERYChapter 11 Transaction Recovery 11.1 Goal and Overview 11.2 Expanded Schedules with Explicit Undo Operations 11.2.1 Intuition and Overview of Concepts11.2.2 The Formal Model11.3 Correctness Criteria for the Page Model11.3.1 Expanded Conflict Serializability11.3.2 Reducibility and Prefix Reducibility11.4 Sufficient Syntactic Conditions11.4.1 Recoverability11.4.2 Avoiding Cascading Aborts 11.4.3 Strictness 11.4.4 Rigorousness 11.4.5 Log Recoverability11.5 Page Model Protocols for Schedules with Transaction Aborts11.5.1 Extending Two-Phase Locking for Strictness and Rigorousness11.5.2 Extending Serialization Graph Testing for Log Recoverability11.5.3 Extending Other Protocols for Log Recoverability11.6 Correctness Criteria for the Object Model11.6.1 Aborts in Flat Object Schedules11.6.2 Complete and Partial Aborts in General Object Model Schedules11.7 Object Model Protocols for Schedules with Transaction Aborts11.8 Lessons LearnedExercisesBibliographic NotesChapter 12 Crash Recovery: Notion of Correctness12.1 Goal and Overview12.2 System Architecture and Interfaces12.3 System Model12.4 CorrectnessCriterion12.5 Road Map of Algorithms12.6 Lessons LearnedExercisesBibliographic NotesChapter 13 Page Model Crash Recovery Algorithms13.1 Goal and Overview13.2 Basic Data Structures13.3 Redo-Winners Paradigm13.3.1 Actions during Normal Operation13.3.2 Simple Three-Pass Algorithm 13.3.3 Enhanced Algorithm: Log Truncation, Checkpoints, Redo Optimization 13.3.4 The Complete Algorithm: Handling Transaction Aborts and Undo Completion13.4 Redo-History Paradigm13.4.1 Actions during Normal Operation13.4.2 Simple Three-Pass and Two-Pass Algorithms 13.4.3 Enhanced Algorithms: Log Truncation, Checkpoints, and Redo Optimization13.4.4 Complete Algorithms: Handling Transaction Rollbacks and Undo Completion13.5 Lessons Learned13.5.1 Putting Everything TogetherExercisesBibliographic NotesChapter 14 Object Model Crash Recovery14.1 Goal and Overview14.2 Conceptual Overview of Redo-History Algorithms14.3 A Simple Redo-History Algorithm for Two-Layered Systems14.3.1 Actions during Normal Operation 14.3.2 Steps during Restart 14.4 An Enhanced Redo-History Algorithm for Two-Layered Systems14.5 A Complete Redo-History Algorithm for General Object Model Executions14.6 Lessons LearnedExercisesBibliographic NotesChapter 15 Special Issues of Recovery15.1 Goal and Overview15.2 Logging and Recovery for Indexes and Large Objects15.2.1 Logical Log Entries for the Redo of Index Page Splits15.2.2 Logical Log Entries and Flush Ordering for Large-Object Operations15.3 Intra-transaction Savepoints and Nested Transactions15.4 Exploiting Parallelism during Restart15.5 Special Considerations for Main-Memory Data Servers15.6 Extensionsfor Data-Sharing Clusters15.7 Lessons LearnedExercisesBibliographic NotesChapter 16 Media Recovery16.1 Goal and Overview16.2 Log-Based Method16.2.1 Database Backup and Archive Logging during Normal Operation16.2.2 Database Restore Algorithms 16.2.3 Analysis of the Mean Time to Data Loss16.3 Storage Redundancy16.3.1 Techniques Based on Mirroring16.3.2 Techniques Based on Error-Correcting Codes16.4 Disaster Recovery16.5 Lessons LearnedExercisesBibliographic NotesChapter 17 Application Recovery17.1 Goal and Overview17.2 Stateless Applications Based on Queues17.3 Stateful Applications Based on Queues17.4 Workflows Based on Queues17.4.1 Failure-Resilient Workflow State and Context17.4.2 Decentralized Workflows Based on Queued Transactions17.5 General Stateful Application17.5.1 Design Considerations17.5.2 Overview of the Server Reply Logging Algorithm 17.5.3 Data Structures 17.5.4 Server Logging during Normal Operation 17.5.5 Client Logging during Normal Operation 17.5.6 Log Truncation 17.5.7 Server Restart 17.5.8 Client Restart 17.5.9 Correctness Reasoning 17.5.10 Applicability to Multi-tier Architectures17.6 Lessons LearnedExercisesBibliographic NotesPART FOUR - COORDINATION OF DISTRIBUTED TRANSACTIONSChapter 18 Distributed Concurrency Control18.1 Goal and Overview18.2 Concurrency Control in Homogeneous Federations18.2.1 Preliminaries18.2.2 Distributed 2PL 18.2.3 Distributed TO 18.2.4 Distributed SGT 18.2.5 Ootimistic Protocols18.3 Distributed Deadlock Detection18.4 Serializability in Heterogeneous Federations18.4.1 Global Histories18.4.2 Global Serializability 18.4.3 Quasi Serializability18.5 Achieving Global Serializability through Local Guarantees18.5.1 Rigorousness 18.5.2 Commitment Ordering18.6 Ticket-Based Concurrency Control18.6.1 Explicit Tickets for Forcing Conflicts18.6.2 Implicit Tickets 18.6.3 Mixing Explicit and Implicit Tickets18.7 Object Model Concurrency Control in Heterogeneous Federations18.8 Coherency and Concurrency Control for Data-Sharing Systems18.9 Lessons LearnedExercisesBibliographic NotesChapter 19 Distributed Transaction Recovery19.1 Goal and Overview19.2 The Basic Two-Phase Commit Algorithm19.2.1 2PC Protocol19.2.2 Restart and Termination Protocol19.2.3 IndependentvRecovery19.3 The Transaction Tree Two-Phase Commit Algorithm19.4 Optimized Algorithms for Distributed Commit 19.4.1 Presumed-Abort and Presumed-Commit Protocols19.4.2 Read-Only Subtree Optimization 19.4.3 Coordinator Transfer 19.4.4 Reduced Blocking19.5 Lessons LearnedExercisesBibliographic NotesPART FIVE - APPLICATIONS AND FUTURE PERSPECTIVESChapter 20 What Is Next?20.1 Goal and Overview20.2 What Has Been Achieved?20.2.1 Ready-to-Use Solutions for Developers20.2.2 State-of-the-Art Techniques for Advanced System Builders20.2.3 Methodology and New Challenges for Researchers20.3 Data Replication for Ubiquitous Access20.4 E-Services and Workflows20.5 Performance and Availability GuaranteesBibliographic NotesReferencesIndexAbout the Authors