Transactions, Concurrency Control and Recovery

Introduction

A database system is valuable only when it preserves correct data despite concurrent users, software failures, hardware faults, and operational disruptions. Transactions provide the unit of work through which database operations are organized. Concurrency-control mechanisms determine how simultaneously executing transactions interact, while recovery mechanisms restore a consistent database after failure. Together, these areas form the reliability core of database management.

A transaction may be a bank transfer, an order placement, an inventory update, or a multi-step analytical transformation. The central challenge is that transactions must appear correct even when their operations overlap. A system must also ensure that committed work survives failure and that incomplete work does not corrupt persistent data.

This chapter examines ACID properties, schedules and serializability, locking, timestamp ordering, multiversion concurrency control (MVCC), isolation anomalies, logging, checkpointing, backup, recovery, and business continuity. It also evaluates design trade-offs involving performance, availability, consistency, and operational risk.

Learning Objectives

After completing this chapter, the learner should be able to:

1. Explain and evaluate the ACID properties of transactions.

2. Analyze schedules using conflict and view serializability.

3. Compare two-phase locking, timestamp ordering, and MVCC.

4. Identify isolation anomalies and select suitable isolation levels.

5. Design write-ahead logging, checkpointing, backup, and recovery procedures.

6. Distinguish transaction recovery from disaster recovery and business continuity.

7. Evaluate reliability, performance, governance, and operational trade-offs in advanced database systems.

1. Transaction Fundamentals and ACID Properties

A transaction is a logically coherent sequence of database operations that is treated as one unit. Typical operations are `read(X)`, `write(X)`, `begin`, `commit`, and `abort` or `rollback`. A transaction can include application logic, but the database management system (DBMS) controls its atomicity, isolation, and durability.

Consider a transfer of amount a from account A to account B:

```text

read(A)

A := A - a

write(A)

read(B)

B := B + a

write(B)

commit

```

If the transaction commits, both changes must be reflected. If it fails before completion, neither account should reflect a partial transfer.

Atomicity

Atomicity means all-or-nothing execution. A transaction that fails must have no externally visible partial effect. Atomicity is implemented through undo information, transaction status, and recovery processing. Atomicity does not imply that every operation is individually instantaneous; rather, it defines the transaction's externally visible outcome.

Consistency

Consistency means that a committed transaction preserves all stated database integrity constraints. These may include primary-key uniqueness, foreign-key validity, domain restrictions, balance rules, and application-level invariants. Consistency is not created solely by the DBMS: it depends on schema constraints, transaction logic, concurrency control, and correct application design.

Isolation

Isolation concerns the visibility of intermediate and concurrent effects. In the ideal serial model, transactions execute one after another, although a DBMS may interleave their operations for efficiency. A practical isolation level may permit some anomalies in exchange for improved concurrency.

Durability

Durability means that once a commit is acknowledged, the committed effects survive subsequent crashes, subject to the system's stated failure model and recovery-point objectives. Durability normally relies on persistent log records, stable storage, replication, and recovery procedures. A commit acknowledged before data has safely reached durable storage may violate durability if power is lost.

The ACID properties are related but distinct. For example, a system may preserve atomicity while offering weak isolation, or provide strong isolation while failing to make committed data durable after a storage failure.

2. Schedules and Serializability

A schedule is an ordering of operations from multiple transactions that preserves the internal order of each transaction. A serial schedule runs each transaction to completion before the next begins. Serial execution is straightforward but may waste CPU, disk, and network resources. A concurrent schedule interleaves operations.

The objective is usually serializability: a concurrent schedule should have the same effect as some serial schedule.

Conflict Serializability

Two operations conflict when:

• they belong to different transactions;
• they access the same data item; and
• at least one operation is a write.

Thus, read-read operations do not conflict, whereas read-write, write-read, and write-write operations do.

Conflict serializability can be tested using a precedence graph. Each transaction is a node. Add an edge from transaction Tᵢ to Tⱼ if an operation of Tᵢ precedes and conflicts with an operation of Tⱼ on the same item. The schedule is conflict-serializable if and only if the graph is acyclic. A topological ordering of the graph gives an equivalent serial order.

Worked Example: Precedence Graph

Suppose the schedule is:

```text

r1(X), w1(X), r2(X), w2(Y), r3(Y), w3(X)

```

Conflicts produce the following edges:

• T1 → T2 because `w1(X)` precedes `r2(X)`.
• T1 → T3 because `w1(X)` precedes `w3(X)`.
• T2 → T3 because `w2(Y)` precedes `r3(Y)`.

The graph contains no cycle. Therefore, the schedule is conflict-serializable. One equivalent serial order is T1, T2, T3.

If the edges were T1 → T2, T2 → T3, and T3 → T1, a cycle would exist and the schedule would not be conflict-serializable.

View Serializability

View serializability is more general than conflict serializability. Two schedules are view equivalent when they preserve:

1. which transaction reads the initial value of each item;

2. which transaction reads a value written by another transaction; and

3. which transaction performs the final write on each item.

Every conflict-serializable schedule is view-serializable, but the reverse is not always true. View-serializable schedules may involve blind writes—writes not preceded by a read—and are more difficult to test efficiently. Consequently, practical concurrency-control protocols commonly guarantee conflict serializability or a stronger property.

Recoverability and Cascadeless Execution

Serializability alone does not guarantee safe recovery. A schedule is recoverable if a transaction that reads data written by another transaction commits only after the writer commits. A cascadeless schedule prevents transactions from reading uncommitted data. A strict schedule prevents other transactions from reading or writing an item until the transaction that last wrote it commits or aborts. Strictness simplifies undo recovery and is a major practical design goal.

3. Concurrency-Control Techniques

Concurrency control coordinates competing transactions while preserving a selected correctness criterion. The main families are locking, timestamp ordering, and multiversion methods.

3.1 Lock-Based Control

A lock is a permission associated with a data item, page, row, table, or other object. The standard lock types are:

• Shared (S) lock: permits reading and is compatible with other shared locks.
• Exclusive (X) lock: permits reading and writing but is incompatible with both shared and exclusive locks.

The compatibility matrix is:

| Requested / Existing | S | X |

|---|---:|---:|

| S | Compatible | Not compatible |

| X | Not compatible | Not compatible |

A transaction must obtain an appropriate lock before accessing protected data. Lock granularity affects performance. Row locks improve concurrency but require more lock-management overhead; table locks are cheaper but restrict concurrency. Hierarchical or intention locks allow a DBMS to combine table- and row-level locking safely.

#### Two-Phase Locking

Under two-phase locking (2PL), a transaction has:

• a growing phase, in which it obtains locks but releases none; and
• a shrinking phase, in which it releases locks but obtains none.

2PL guarantees conflict serializability. Strict 2PL holds all exclusive locks until commit or abort, preventing dirty reads and simplifying recovery. Rigorous 2PL holds both shared and exclusive locks until completion. Strict protocols can cause blocking, deadlocks, and reduced concurrency, but they provide strong and predictable behavior.

#### Deadlocks

A deadlock occurs when transactions wait in a cycle. For example, T1 holds X and waits for Y, while T2 holds Y and waits for X. A wait-for graph represents transactions as nodes and waiting relationships as directed edges. A cycle indicates deadlock.

Deadlock handling includes:

• Prevention: impose ordering or use timestamp rules such as wait-die and wound-wait.
• Avoidance: grant a request only if the resulting state remains safe.
• Detection and recovery: periodically find cycles and abort one or more victim transactions.
• Timeout: abort transactions that wait too long; simple but may mistake slow work for deadlock.

Victim selection may consider rollback cost, amount of work completed, locks held, transaction priority, and the number of previous aborts.

3.2 Timestamp-Ordering Protocols

A timestamp-ordering system assigns each transaction a unique timestamp, representing its logical order. Each data item maintains a read timestamp and a write timestamp. A basic protocol rejects an operation when it would violate the timestamp order. For example, if a transaction with an older timestamp attempts to write an item already read by a newer transaction, the older transaction may be aborted and restarted.

Timestamp ordering avoids deadlock because transactions do not wait for locks in the basic protocol. Its disadvantages include transaction restarts, possible starvation, and overhead for maintaining timestamps. Variants such as Thomas's write rule may ignore obsolete writes in carefully defined cases, improving concurrency while preserving correctness under the relevant model.

3.3 Multiversion Concurrency Control

MVCC maintains multiple committed versions of a data item. A reader selects a version visible under its snapshot, while a writer creates a new version rather than overwriting the old version immediately. This allows readers and writers to proceed with less blocking.

MVCC is particularly effective for read-intensive systems. However, it requires version storage, visibility metadata, garbage collection, and protection against anomalies that snapshot visibility alone may not prevent. Long-running readers can delay version cleanup. Different DBMS products implement snapshot and serializable modes differently; therefore, an administrator must consult the product's formal guarantees rather than relying on terminology alone.

4. Isolation Levels and Anomalies

Isolation levels express permitted visibility anomalies. The SQL standard names Read Uncommitted, Read Committed, Repeatable Read, and Serializable. Implementations vary, and some systems provide Snapshot Isolation as a separate model.

Dirty Read

A dirty read occurs when T2 reads a value written by T1 before T1 commits. If T1 aborts, T2 has consumed a value that never became part of the committed database.

Nonrepeatable Read

T1 reads a row, T2 modifies and commits it, and T1 reads the row again, obtaining a different value.

Phantom Read

T1 executes a predicate query, T2 inserts or deletes a row satisfying that predicate and commits, and T1 repeats the query, obtaining a different set of rows. Preventing phantoms generally requires predicate or range protection, not merely row locks on rows that already exist.

Lost Update

Two transactions read the same old value and both write derived values. The later write overwrites the earlier result. Locking, atomic update statements, optimistic validation, or suitable serializable mechanisms can prevent this anomaly.

Write Skew

Under snapshot-style isolation, two transactions may read overlapping facts and update different rows. Each transaction individually satisfies the constraint it observed, but their combined committed result violates a cross-row invariant. Serializable validation or explicit locking of the logical predicate is needed when such invariants matter.

A simplified comparison is:

| Level or model | Typical protection | Typical cost or limitation |

|---|---|---|

| Read Uncommitted | Minimal | Dirty and other anomalies possible |

| Read Committed | Prevents dirty reads | Repeated reads may differ |

| Repeatable Read | Stable reads of accessed rows | Phantoms or implementation-specific behavior may remain |

| Snapshot Isolation | Consistent transaction snapshot | Write skew may occur |

| Serializable | Equivalent to serial execution | More blocking, aborts, or validation overhead |

Isolation should be selected according to business invariants, not merely maximum throughput.

5. Logging and Recovery

Recovery addresses failures such as transaction errors, system crashes, media failures, and site disasters. A recovery manager uses logs and backups to restore a state satisfying atomicity and durability.

Write-Ahead Logging

Write-ahead logging (WAL) requires that a log record describing a change reach stable storage before the corresponding changed data page is written to stable storage. Before a commit is acknowledged, the log records required to redo the transaction must be durable. WAL permits recovery to reconstruct committed changes and remove incomplete changes.

A conceptual update log record may contain:

```text

<transaction-id, data-item, old-value, new-value>

```

Physical systems may instead log page offsets, physiological changes, logical operations, or combinations. Each log record generally has a log sequence number (LSN), and pages record the LSN of their latest logged change. This supports efficient recovery decisions.

Deferred and Immediate Update

With deferred update, database pages are not written with a transaction's changes until the transaction commits; recovery mainly requires redo of committed work. With immediate update, uncommitted pages may reach storage, so recovery requires undo of incomplete work and redo of committed work. Modern systems commonly use immediate-update WAL because it supports flexible buffering and efficient operation.

Checkpointing

A checkpoint records sufficient recovery information so that recovery need not scan the entire log from the beginning of the database. A checkpoint may record active transactions, dirty pages, and a log position. Fuzzy checkpoints allow normal processing to continue while checkpoint information is collected.

Checkpointing does not replace backups. A checkpoint limits crash-recovery work for a running system, whereas a backup provides a recoverable copy after media loss or corruption.

ARIES-Style Recovery

The ARIES family of algorithms is a major recovery design. Its analysis phase identifies the state at failure, including active transactions and dirty pages. Its redo phase repeats history from an appropriate point, including changes of transactions that were incomplete at the crash. Its undo phase rolls back loser transactions, writing compensation log records (CLRs) so that undo itself is recoverable.

The phrase “repeating history” is important: redo reconstructs the database state represented by the log, after which incomplete work is undone. Recovery correctness depends on WAL, page LSNs, transaction status, and carefully ordered log flushing.

6. Backup, Disaster Recovery and Business Continuity

Transaction recovery and disaster recovery operate at different scales. Transaction recovery addresses failures within a DBMS execution environment. Disaster recovery addresses loss or unavailability of infrastructure, such as storage arrays, data centers, networks, or cloud regions.

Common backup types include:

• Full backup: copies the complete selected database.
• Incremental backup: copies changes since a reference backup, often the most recent backup.
• Differential backup: copies changes since the last full backup.
• Log backup: preserves transaction-log history for point-in-time recovery.
• Snapshot or replica: provides a rapid copy, but may not be an independent, durable backup unless separately protected.

A reliable design defines:

• Recovery Point Objective (RPO): the maximum acceptable amount of data loss measured in time.
• Recovery Time Objective (RTO): the target time to restore service.
• Maximum tolerable downtime: the business limit beyond which consequences become unacceptable.

For example, an RPO of five minutes means that, under the recovery design, the organization accepts losing at most approximately five minutes of committed changes. It is not a guarantee unless log transfer, storage, monitoring, and restoration processes have been tested.

Business continuity includes alternate processing locations, redundant infrastructure, communication plans, manual workarounds, security controls, staff responsibilities, and supplier dependencies. High availability and disaster recovery are related but not identical: replication may reduce downtime but can also replicate corruption or accidental deletion. Backups must therefore be isolated, access-controlled, monitored, and periodically restored in tests.

7. Illustrative Case: Online Retail Order Processing

Background

Consider a fictional online retailer that sells limited-stock products. An order transaction creates an order, reserves inventory, records payment authorization, and emits a fulfillment event.

Problem

During a promotional event, two customers purchase the last unit simultaneously. A weak isolation scheme permits both transactions to read inventory quantity 1 and decrement it, creating a negative quantity or overselling. A server crash after payment authorization but before order completion creates uncertainty about the order's status.

Analysis

The inventory rule is a cross-operation invariant: the committed quantity must not become negative. A simple snapshot read may not prevent write skew or conflicting updates. Payment and order creation also require an idempotent design because retries may repeat external requests.

Approach

The retailer adopts the following design:

1. Use an atomic conditional update such as “decrement inventory only where quantity is at least one,” and verify that exactly one row was affected.

2. Use a transaction with strict locking or serializable validation for the inventory reservation.

3. Write an order and reservation event to a durable transaction log or an outbox table in the same transaction.

4. Use an idempotency key so a retried request does not create a second order or payment attempt.

5. Replicate logs to a separate failure domain and retain encrypted backups.

6. Test point-in-time restoration and failover against stated RTO and RPO targets.

Outcome

Only one transaction reserves the final unit. If the service crashes after commit, recovery reconstructs the committed order and the outbox processor eventually delivers the fulfillment event. If the transaction aborts, WAL-based undo removes the incomplete reservation. A reconciliation process compares payment, order, inventory, and fulfillment records to detect external-system discrepancies.

Learning Points

Correctness requires more than selecting an isolation level. Business invariants must be stated explicitly, external side effects must be made idempotent or reconciled, and recovery must be tested under realistic failure conditions.

8. Design Evaluation and Professional Practice

A sound design begins by identifying invariants, transaction boundaries, workload characteristics, and failure assumptions. Designers should then select the weakest isolation model that safely preserves required invariants, rather than choosing either maximum isolation everywhere or maximum throughput everywhere.

Important engineering practices include:

• keep transactions short and avoid user interaction inside a transaction;
• access shared objects in a consistent order to reduce deadlocks;
• index predicate and foreign-key columns appropriately;
• monitor lock waits, deadlocks, rollback rates, log growth, checkpoint duration, and replication lag;
• distinguish committed data from merely acknowledged application requests;
• test crash recovery, backup restoration, failover, and rollback procedures;
• document RPO, RTO, ownership, escalation, and communication responsibilities;
• protect logs and backups through encryption, access control, retention policies, and tamper-evident auditing.

Governance is also important. Recovery copies may contain personal, financial, or health information. Retention must respect legal and regulatory obligations, while deletion requests and archival requirements must be reconciled with immutable audit records. Artificial intelligence can assist with anomaly detection, deadlock-pattern analysis, workload forecasting, and recovery testing, but automated recommendations must be explainable, monitored, and subject to human approval. An AI system should never silently change isolation or recovery policy without controlled validation.

Contemporary Developments

Distributed databases increasingly combine replication, consensus, partition management, and transaction protocols. A distributed commit protocol may preserve atomicity across services, but it adds coordination latency and failure modes. Saga patterns divide a long business process into local transactions with compensating actions; they provide eventual business consistency but do not have the same semantics as one ACID transaction.

Cloud-managed databases automate backups, replicas, and failover, yet responsibility is shared: the provider manages infrastructure while the customer must configure retention, permissions, recovery objectives, and application behavior. Immutable backups, isolated recovery environments, continuous verification, and ransomware-aware recovery planning are increasingly important. The fundamental principles remain unchanged: define correctness, preserve a trustworthy history, and prove recoverability through testing.

Chapter Summary

Transactions organize database work into atomic units. ACID properties describe atomicity, consistency, isolation, and durability, but each depends on different mechanisms and assumptions. Concurrent schedules improve resource utilization, while serializability provides a correctness benchmark. Conflict serializability can be tested with a precedence graph; view serializability is more general but harder to test.

Locking protocols, especially strict two-phase locking, provide strong guarantees but may cause blocking and deadlocks. Timestamp ordering avoids lock-based deadlocks but may require restarts. MVCC improves read concurrency through multiple versions, although snapshot-based systems can permit anomalies such as write skew. Isolation levels must be selected according to business invariants.

Write-ahead logging, checkpoints, redo, undo, and compensation records support crash recovery. Backups, replication, RPO, RTO, and restoration testing address broader disaster-recovery and business-continuity needs. Professional database reliability requires technical controls, governance, security, observability, and tested operational procedures.

Key Terms

Transaction: A logical unit of database work.

Atomicity: The all-or-nothing property of transaction execution.

Consistency: Preservation of database constraints after a committed transaction.

Isolation: Control over the visibility and interaction of concurrent transactions.

Durability: Persistence of committed effects after failure.

Schedule: An ordering or interleaving of operations from transactions.

Conflict serializability: Equivalence to a serial schedule based on conflicting operations.

Precedence graph: A graph used to test conflict serializability.

Recoverable schedule: A schedule in which dependent transactions commit in a safe order.

Shared lock: A lock permitting reading and compatible shared access.

Exclusive lock: A lock required for writing and incompatible with other locks.

Two-phase locking: A locking protocol with growing and shrinking phases.

Deadlock: Cyclic waiting among transactions.

MVCC: Multiversion concurrency control using multiple visible data versions.

Dirty read: Reading data written by an uncommitted transaction.

Phantom read: A changed result set caused by concurrent insertion or deletion.

Write-ahead logging: Requiring log durability before corresponding data-page durability.

Checkpoint: Recovery information that limits the log-scanning effort.

RPO: Maximum acceptable amount of data loss measured in time.

RTO: Target time for restoring service after disruption.

Review Questions

Short Answer Questions

1. Define atomicity and explain how it differs from durability.

2. What condition in a precedence graph indicates that a schedule is not conflict-serializable?

3. Distinguish a shared lock from an exclusive lock.

4. What is a phantom read?

5. Why is write-ahead logging required?

Long Answer Questions

1. Explain ACID properties and discuss the mechanisms that support each property.

2. Compare strict two-phase locking, timestamp ordering, and MVCC in terms of correctness, blocking, restart behavior, and workload suitability.

3. Explain dirty reads, nonrepeatable reads, phantom reads, lost updates, and write skew.

4. Describe checkpointing and ARIES-style analysis, redo, and undo recovery.

5. Develop a backup and business-continuity strategy for a transaction-intensive organization, including RPO, RTO, security, and testing.

Analytical / Application Questions

1. Construct a precedence graph for a supplied concurrent schedule and determine whether it is conflict-serializable. If it is, provide an equivalent serial order.

2. An inventory system uses snapshot isolation and permits two transactions to reserve different rows after reading a shared capacity limit. Analyze whether write skew can occur and propose a correction.

3. Design a recovery architecture for an online retailer whose requirements are an RPO of five minutes and an RTO of thirty minutes. Justify logging, replication, backup, restoration testing, and failover choices.

Multiple Choice Questions with Answers

Question 1

Which condition proves that a schedule is conflict-serializable?

A. Its precedence graph contains at least one cycle

B. Its precedence graph is acyclic

C. All transactions use exclusive locks

D. Every transaction performs the same number of writes

Correct Answer: B. Its precedence graph is acyclic

Question 2

Which lock type is normally required before modifying a data item?

A. Shared lock

B. Intent-shared lock only

C. Exclusive lock

D. Read timestamp

Correct Answer: C. Exclusive lock

Question 3

Which anomaly occurs when a transaction reads data written by a transaction that later aborts?

A. Dirty read

B. Phantom read

C. Write skew

D. Lost commit

Correct Answer: A. Dirty read

Question 4

What is the principal requirement of write-ahead logging?

A. Data pages must be written before log records

B. Log records describing changes must reach stable storage before corresponding data pages

C. Only committed transactions may generate log records

D. Checkpoints must occur after every read

Correct Answer: B. Log records describing changes must reach stable storage before corresponding data pages

Question 5

Which recovery phase identifies active transactions and dirty pages after a crash?

A. Analysis

B. Redo

C. Undo

D. Replication

Correct Answer: A. Analysis

Question 6

What is a major advantage of MVCC?

A. It eliminates the need for backups

B. It allows many readers to proceed without blocking writers

C. It guarantees that write skew can never occur

D. It prevents all transaction aborts

Correct Answer: B. It allows many readers to proceed without blocking writers

Question 7

A cycle in a wait-for graph indicates what condition?

A. A checkpoint

B. A serial schedule

C. A deadlock

D. A durable commit

Correct Answer: C. A deadlock

Question 8

What does an RPO of five minutes specify?

A. The maximum time allowed to restart a server

B. The maximum acceptable amount of data loss measured approximately in time

C. The maximum transaction duration

D. The interval between all database checkpoints

Correct Answer: B. The maximum acceptable amount of data loss measured approximately in time

Question 9

Which schedule property prevents transactions from reading uncommitted data?

A. Cascadelessness

B. Nonserializability

C. Blind writing

D. Timestamp omission

Correct Answer: A. Cascadelessness

Question 10

Why are backups necessary even when a system uses checkpoints?

A. Checkpoints provide copies after total media loss

B. Backups replace transaction isolation

C. Checkpoints limit crash recovery, whereas backups support restoration after media loss or corruption

D. Backups guarantee zero downtime

Correct Answer: C. Checkpoints limit crash recovery, whereas backups support restoration after media loss or corruption