Transactional Information Systems, 1st Edition
Foreword by
Gray, Microsoft, Inc.
Preface
PART ONE - BACKGROUND AND MOTIVATION
Chapter 1 What Is It All About?
1.1 Goal and Overview
1.2 Application Examples
1.2.1 Online Transaction Processing: Debit/Credit Example
1.2.2 Electronic Commerce Example
1.2.3 Workflow Management: Travel Planning Example
1.3 System Paradigms
1.3.1 Three-Tier and Two-Tier Architectures
1.3.2 Federations of Servers
1.4 Virtues of the Transaction Concept
1.4.1 Transaction Properties and the Transaction Programming Interface
1.4.2 Requirements on Transactional Servers
1.5 Concepts and Architecture of Database Servers
1.5.1 Architectural Layers of Database Systems
1.5.2 How Data Is Stored
1.5.3 How Data Is Accessed
1.5.4 How Queries and Updates Are Executed
1.6 Lessons Learned
Exercises
Bibliographic Notes
Chapter 2 Computational Models
2.1 Goal and Overview
2.2 Ingredients
2.3 The Page Model
2.4 The Object Model
2.5 Road Map of the Book
2.6 Lessons Learned
Exercises
Bibliographic Notes
PART TWO - CONCURRENCY CONTROL
Chapter 3 Concurrency Control: Notions of Correctness for the Page Model
3.1 Goal and Overview
3.2 Canonical Concurrency Problems
3.3 Syntax of Histories and Schedules
3.4 Correctness of Histories and Schedules
3.5 Herbrand Semantics of Schedules
3.6 Final State Serializability
3.7 View Serializability
3.7.1 View Equivalence and the Resulting Correctness Criterion
3.7.2 On the Complexity of Testing View Serializability
3.8 Conflict Serializability
3.8.1 Conflict Relations
3.8.2 Class CSR
3.8.3 Conflicts and Commutativity
3.8.4 Restrictions of Conflict Serializability
3.9 Commit Serializability
3.10 An Alternative Correctness Criterion: Interleaving Specifications
3.11 Lessons Learned
Exercises
Bibliographic Notes
Chapter 4 Concurrency Control Algorithms
4.1 Goal and Overview
4.2 General Scheduler Design
4.3 Locking Schedulers
4.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 Locks
4.3.6 Altruistic Locking
4.3.7 Non-Two-Phase Locking Protocols
4.3.8 On the Geometry of Locking
4.4 Nonlocking Schedulers
4.4.1 Timestamp Ordering
4.4.2 Serialization Graph Testing
4.4.3 Optimistic Protocols
4.5 Hybrid Protocols
4.6 Lessons Learned
Exercises
Bibliographic Notes
Chapter 5 Multiversion Concurrency Control
5.1 Goal and Overview
5.2 Multiversion Schedules
5.3 Multiversion Serializability
5.3.1 Multiversion View Serializability
5.3.2 Testing Membership in MVSR
5.3.3 Multiversion Conflict Serializability
5.4 Limiting the Number of Versions
5.5 Multiversion Concurrency Control Protocols
5.5.1 The MVTO Protocol
5.5.2 The MV2PL Protocol
5.5.3 The MVSGT Protocol
5.5.4 A Multiversion Protocol for Read-Only Transactions
5.6 Lessons Learned
Exercises
Bibliographic Notes
Chapter 6 Concurrency Control on Objects: Notions of Correctness
6.1 Goal and Overview
6.2 Histories and Schedules
6.3 Conflict Serializability for Flat Object Transactions
6.4 Tree Reducibility
6.5 Sufficient Conditions for Tree Reducibility
6.6 Exploiting State Based Commutativity
6.7 Lessons Learned
Exercises
Bibliographical Notes
Chapter 7 Concurrency Control Algorithms on Objects
7.1 Goal and Overview
7.2 Locking for Flat Object Transactions
7.3 Layered Locking
7.4 Locking on General Transaction Forests
7.5 Hybrid Algorithms
7.6 Locking for Return Value Commutativity and Escrow Locking
7.7 Lessons Learned
Exercises
Bibliographic Notes
Chapter 8 Concurrency Control on Relational Databases
8.1 Goal and Overview
8.2 Predicate-Oriented Concurrency Control
8.3 Relational Update Transactions
8.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 Knowledge
8.4.1 Motivating Example
8.4.2 Transaction Chopping
8.4.3 Applicability of Chopping
8.5 Lessons Learned
Exercises
Bibliographic Notes
Chapter 9 Concurrency Control on Search Structures
9.1 Goal and Overview
9.2 Implementation of Search Structures by B+ Trees
9.3 Key Range Locking at the Access Layer
9.4 Techniques for the Page Layer
9.4.1 Lock Coupling
9.4.2 Link Technique
9.4.3 Giveup Technique
9.5 Further Optimizations
9.5.1 Deadlock-Free Page Latching
9.5.2 Enhanced Key Range Concurrency
9.5.3 Reduced Locking Overhead
9.5.4 Exploiting Transient Versioning
9.6 Lessons Learned
Exercises
Bibliographic Notes
Chapter 10 Implementation and Pragmatic Issues
10.1 Goal and Overview
10.2 Data Structures of a Lock Manager
10.3 Multiple Granularity Locking and Dynamic Escalation
10.4 Transient Versioning
10.5 Nested Transactions for Intra-transaction Parallelism
10.6 Tuning Options
10.6.1 Manual Locking
10.6.2 SQL Isolation Levels
10.6.3 Short Transactions
10.6.4 Limiting the Level of Multiprogramming
10.7 Overload Control
10.7.1 Feedback-Driven Method
10.7.2 Wait-Depth Limitation
10.8 Lessons Learned
Exercises
Bibliographic Notes
PART THREE - RECOVERY
Chapter 11 Transaction Recovery
11.1 Goal and Overview
11.2 Expanded Schedules with Explicit Undo Operations
11.2.1 Intuition and Overview of Concepts
11.2.2 The Formal Model
11.3 Correctness Criteria for the Page Model
11.3.1 Expanded Conflict Serializability
11.3.2 Reducibility and Prefix Reducibility
11.4 Sufficient Syntactic Conditions
11.4.1 Recoverability
11.4.2 Avoiding Cascading Aborts
11.4.3 Strictness
11.4.4 Rigorousness
11.4.5 Log Recoverability
11.5 Page Model Protocols for Schedules with Transaction Aborts
11.5.1 Extending Two-Phase Locking for Strictness and Rigorousness
11.5.2 Extending Serialization Graph Testing for Log Recoverability
11.5.3 Extending Other Protocols for Log Recoverability
11.6 Correctness Criteria for the Object Model
11.6.1 Aborts in Flat Object Schedules
11.6.2 Complete and Partial Aborts in General Object Model Schedules
11.7 Object Model Protocols for Schedules with Transaction Aborts
11.8 Lessons Learned
Exercises
Bibliographic Notes
Chapter 12 Crash Recovery: Notion of Correctness
12.1 Goal and Overview
12.2 System Architecture and Interfaces
12.3 System Model
12.4 CorrectnessCriterion
12.5 Road Map of Algorithms
12.6 Lessons Learned
Exercises
Bibliographic Notes
Chapter 13 Page Model Crash Recovery Algorithms
13.1 Goal and Overview
13.2 Basic Data Structures
13.3 Redo-Winners Paradigm
13.3.1 Actions during Normal Operation
13.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 Completion
13.4 Redo-History Paradigm
13.4.1 Actions during Normal Operation
13.4.2 Simple Three-Pass and Two-Pass Algorithms
13.4.3 Enhanced Algorithms: Log Truncation, Checkpoints, and Redo Optimization
13.4.4 Complete Algorithms: Handling Transaction Rollbacks and Undo Completion
13.5 Lessons Learned
13.5.1 Putting Everything Together
Exercises
Bibliographic Notes
Chapter 14 Object Model Crash Recovery
14.1 Goal and Overview
14.2 Conceptual Overview of Redo-History Algorithms
14.3 A Simple Redo-History Algorithm for Two-Layered Systems
14.3.1 Actions during Normal Operation
14.3.2 Steps during Restart
14.4 An Enhanced Redo-History Algorithm for Two-Layered Systems
14.5 A Complete Redo-History Algorithm for General Object Model Executions
14.6 Lessons Learned
Exercises
Bibliographic Notes
Chapter 15 Special Issues of Recovery
15.1 Goal and Overview
15.2 Logging and Recovery for Indexes and Large Objects
15.2.1 Logical Log Entries for the Redo of Index Page Splits
15.2.2 Logical Log Entries and Flush Ordering for Large-Object Operations
15.3 Intra-transaction Savepoints and Nested Transactions
15.4 Exploiting Parallelism during Restart
15.5 Special Considerations for Main-Memory Data Servers
15.6 Extensionsfor Data-Sharing Clusters
15.7 Lessons Learned
Exercises
Bibliographic Notes
Chapter 16 Media Recovery
16.1 Goal and Overview
16.2 Log-Based Method
16.2.1 Database Backup and Archive Logging during Normal Operation
16.2.2 Database Restore Algorithms
16.2.3 Analysis of the Mean Time to Data Loss
16.3 Storage Redundancy
16.3.1 Techniques Based on Mirroring
16.3.2 Techniques Based on Error-Correcting Codes
16.4 Disaster Recovery
16.5 Lessons Learned
Exercises
Bibliographic Notes
Chapter 17 Application Recovery
17.1 Goal and Overview
17.2 Stateless Applications Based on Queues
17.3 Stateful Applications Based on Queues
17.4 Workflows Based on Queues
17.4.1 Failure-Resilient Workflow State and Context
17.4.2 Decentralized Workflows Based on Queued Transactions
17.5 General Stateful Application
17.5.1 Design Considerations
17.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 Architectures
17.6 Lessons Learned
Exercises
Bibliographic Notes
PART FOUR - COORDINATION OF DISTRIBUTED TRANSACTIONS
Chapter 18 Distributed Concurrency Control
18.1 Goal and Overview
18.2 Concurrency Control in Homogeneous Federations
18.2.1 Preliminaries
18.2.2 Distributed 2PL
18.2.3 Distributed TO
18.2.4 Distributed SGT
18.2.5 Ootimistic Protocols
18.3 Distributed Deadlock Detection
18.4 Serializability in Heterogeneous Federations
18.4.1 Global Histories
18.4.2 Global Serializability
18.4.3 Quasi Serializability
18.5 Achieving Global Serializability through Local Guarantees
18.5.1 Rigorousness
18.5.2 Commitment Ordering
18.6 Ticket-Based Concurrency Control
18.6.1 Explicit Tickets for Forcing Conflicts
18.6.2 Implicit Tickets
18.6.3 Mixing Explicit and Implicit Tickets
18.7 Object Model Concurrency Control in Heterogeneous Federations
18.8 Coherency and Concurrency Control for Data-Sharing Systems
18.9 Lessons Learned
Exercises
Bibliographic Notes
Chapter 19 Distributed Transaction Recovery
19.1 Goal and Overview
19.2 The Basic Two-Phase Commit Algorithm
19.2.1 2PC Protocol
19.2.2 Restart and Termination Protocol
19.2.3 IndependentvRecovery
19.3 The Transaction Tree Two-Phase Commit Algorithm
19.4 Optimized Algorithms for Distributed Commit
19.4.1 Presumed-Abort and Presumed-Commit Protocols
19.4.2 Read-Only Subtree Optimization
19.4.3 Coordinator Transfer
19.4.4 Reduced Blocking
19.5 Lessons Learned
Exercises
Bibliographic Notes
PART FIVE - APPLICATIONS AND FUTURE PERSPECTIVES
Chapter 20 What Is Next?
20.1 Goal and Overview
20.2 What Has Been Achieved?
20.2.1 Ready-to-Use Solutions for Developers
20.2.2 State-of-the-Art Techniques for Advanced System Builders
20.2.3 Methodology and New Challenges for Researchers
20.3 Data Replication for Ubiquitous Access
20.4 E-Services and Workflows
20.5 Performance and Availability Guarantees
Bibliographic Notes
References
Index
About the Authors
