Transactional Information Systems

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

Transactional Information Systems is the long-awaited, comprehensive work from leading scientists in the transaction processing field. Weikum and Vossen begin with a broad look at the role of transactional technology in today's economic and scientific endeavors, then delve into critical issues faced by all practitioners, presenting today's most effective techniques for controlling concurrent access by multiple clients, recovering from system failures, and coordinating distributed transactions.

The authors emphasize formal models that are easily applied across fields, that promise to remain valid as current technologies evolve, and that lend themselves to generalization and extension in the development of new classes of network-centric, functionally rich applications. This book's purpose and achievement is the presentation of the foundations of transactional systems as well as the practical aspects of the field what will help you meet today's challenges.

• Provides the most advanced coverage of the topic available anywhere--along with the database background required for you to make full use of this material.
• Explores transaction processing both generically as a broadly applicable set of information technology practices and specifically as a group of techniques for meeting the goals of your enterprise.
• Contains information essential to developers of Web-based e-Commerce functionality--and a wide range of more "traditional" applications.
• Details the algorithms underlying core transaction processing functionality.

Database designers and programmers.