Transactional Information Systems

Transactional Information Systems

Theory, Algorithms, and the Practice of Concurrency Control and Recovery

1st Edition - May 21, 2001

Write a review

  • Authors: Gerhard Weikum, Gottfried Vossen
  • eBook ISBN: 9780080519562
  • Hardcover ISBN: 9781558605084

Purchase options

Purchase options
DRM-free (PDF)
Available
Sales tax will be calculated at check-out

Institutional Subscription

Free Global Shipping
No minimum order

Description

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.

Key Features

  • 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.

Readership

Database designers and programmers.

Table of Contents

  • 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

Product details

  • No. of pages: 872
  • Language: English
  • Copyright: © Morgan Kaufmann 2001
  • Published: May 21, 2001
  • Imprint: Morgan Kaufmann
  • eBook ISBN: 9780080519562
  • Hardcover ISBN: 9781558605084

About the Authors

Gerhard Weikum

Gerhard Weikum is Professor of Computer Science at University of the Saarland in Saarbruecken, Germany, where he leads a research group on database and information systems. His research has focused on parallel and distributed information systems, transaction processing and workflow management, database optimization and performance evaluation, multimedia data management, and intelligent search on Web data.

Gottfried Vossen

Gottfried Vossen is Professor of Computer Science and a Director of the Institür für Wirtschaftsinformatik, Universität Münster (Department of Information Systems, University of Muenster, Germany). His research in the area of object-based database systems has dealt primarily with models for data and objects, database languages, transaction processing, integration with scientific applications, XML and its applications, and workflow management.

Affiliations and Expertise

Institür für Wirtschaftsinformatik, Universität Münster, Department of Information Systems, University of Muenster, Germany

Ratings and Reviews

Write a review

There are currently no reviews for "Transactional Information Systems"