Transactions, Concurrency Control and Recovery

Introduction

A database is valuable only when it preserves correct and durable information despite simultaneous users, software failures, hardware faults, and interrupted operations. A banking transfer, for example, must not debit one account without crediting the other. An online order should not reserve stock twice merely because two customers acted at nearly the same time. These requirements are addressed through transactions, concurrency control, and recovery.

A transaction is a logically meaningful unit of database work. It may contain several read and write operations, yet the database system must make it appear as though the unit either completed successfully or had no effect. Concurrency control coordinates overlapping transactions so that their results remain correct. Recovery restores consistency after failures and ensures that committed results are not lost.

These mechanisms are especially important in AI and machine-learning systems. Training-data pipelines may update feature stores concurrently; recommendation systems may record user events while models read those events; and model-serving platforms may require durable, consistent metadata about model versions and experiments.

Learning Objectives

By the end of this chapter, you should be able to:

• explain transactions and the ACID properties;
• represent schedules and determine conflict serializability;
• describe locking, timestamp-ordering, optimistic, and multiversion protocols;
• distinguish isolation levels and their anomalies;
• explain deadlocks and methods for handling them;
• describe logging, checkpoints, write-ahead logging, backup, and crash recovery;
• select appropriate transaction and recovery techniques for practical systems.

Transactions and the ACID Model

A transaction moves the database from one consistent state to another. Typical operations are `READ(X)` and `WRITE(X)`, although an implementation also performs validation, logging, locking, and commit processing. A transaction normally passes through active, partially committed, committed, failed, and aborted states.

The four ACID properties are:

Atomicity. All operations of a transaction take effect, or none take effect. If a transfer debits account A but fails before crediting account B, recovery must undo the debit.

Consistency. A committed transaction preserves declared integrity rules. These rules may include primary-key uniqueness, foreign-key validity, domain restrictions, and application constraints such as “an account balance cannot be negative.” Consistency is jointly enforced by application logic and the DBMS; it is not created by concurrency control alone.

Isolation. Concurrent transactions should not improperly interfere. Isolation is commonly described in terms of equivalent serial execution, although practical systems offer several isolation levels with different performance and anomaly guarantees.

Durability. Once a commit is acknowledged, its effects survive subsequent crashes, subject to the system’s durability design and storage assumptions.

ACID is a correctness model, not a guarantee that every transaction is fast or globally distributed. Stronger isolation can reduce concurrency, and durability may require stable storage and synchronous replication.

Schedules and Serializability

A schedule is the chronological order in which operations from several transactions execute. A serial schedule completes one transaction before beginning another. A nonserial schedule interleaves operations and may improve throughput.

Two operations conflict when they belong to different transactions, access the same data item, and at least one is a write. Thus, `READ_i(X)` conflicts with `WRITE_j(X)`, and `WRITE_i(X)` conflicts with `WRITE_j(X)`. Two reads do not conflict.

A schedule is conflict-serializable if it is conflict-equivalent to a serial schedule. The standard test uses a precedence graph:

1. Create one node for each transaction.

2. Add an edge from T_i to T_j when an operation of T_i precedes and conflicts with an operation of T_j on the same item.

3. The schedule is conflict-serializable exactly when this graph is acyclic.

4. A topological ordering of the graph gives an equivalent serial order.

Worked Example: Precedence Graph

Consider the schedule:

`R1(A), W1(A), R2(A), W2(B), R1(B), W1(B)`

On item A, `W1(A)` precedes `R2(A)`, producing T1 → T2. On item B, `W2(B)` precedes `R1(B)`, producing T2 → T1. The graph contains a cycle, T1 → T2 → T1, so the schedule is not conflict-serializable. A database system using a serializability-preserving protocol must prevent or roll back at least one conflicting operation.

View serializability is a broader concept than conflict serializability and can classify some schedules as serializable even when their precedence graphs contain cycles. Conflict serializability is more commonly used because it is easier to test and enforce.

Lock-Based Concurrency Control

A lock is a permission associated with a data item. A shared lock (S) permits reading, while an exclusive lock (X) permits reading and writing. Compatibility is:

| Requested/held | S | X |

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

| S | compatible | incompatible |

| X | incompatible | incompatible |

A transaction must generally obtain an S lock before reading and an X lock before writing. Lock conversion may upgrade S to X or downgrade X to S, subject to protocol rules.

Two-Phase Locking

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

• a growing phase, during which it acquires locks but releases none;
• a shrinking phase, during which it releases locks but acquires none.

2PL guarantees conflict serializability, but ordinary 2PL may allow cascading rollback because a transaction can release a write lock before committing.

Strict 2PL holds all exclusive locks until commit or abort. It prevents other transactions from reading or overwriting uncommitted data and therefore prevents cascading rollback. Rigorous 2PL holds both shared and exclusive locks until completion. Strict protocols simplify recovery but may reduce concurrency.

Lock granularity ranges from database and table locks to page, row, key-range, or predicate locks. Fine-grained locks improve concurrency but increase memory and management overhead. Intention locks—IS, IX, and SIX—allow a hierarchy such as database–table–page–row to be used safely. Lock escalation replaces many fine-grained locks with a coarser lock when the number of locks becomes large.

Timestamp-Ordering Protocols

A timestamp-ordering protocol assigns each transaction a unique timestamp, usually reflecting its logical start order. For each item X, the DBMS records the largest timestamp of a transaction that successfully read X, `RTS(X)`, and the largest timestamp of a transaction that successfully wrote X, `WTS(X)`.

For a transaction T with timestamp TS(T):

• A read of X is rejected or causes rollback if TS(T) < WTS(X), because a newer transaction has already written X.
• Otherwise the read is allowed and `RTS(X)` becomes the maximum of its old value and TS(T).
• A write of X is rejected or causes rollback if TS(T) < RTS(X), because a newer transaction has already read X.
• A write is also normally rejected if TS(T) < WTS(X), unless a permitted optimization such as Thomas’s write rule applies.

Timestamp protocols avoid deadlock because transactions do not wait for locks. Their disadvantages include rollbacks and possible starvation when transactions repeatedly restart.

Optimistic Concurrency Control

Optimistic control assumes conflicts are uncommon. A transaction executes without acquiring ordinary data locks and passes through three phases:

1. Read phase: read database items and update private workspace.

2. Validation phase: test whether committing would conflict with transactions that overlapped it.

3. Write phase: copy updates to the database if validation succeeds; otherwise abort and restart.

This approach suits workloads with many reads, short transactions, and low contention. It performs poorly when conflicts are frequent because substantial work may be discarded during validation.

Multiversion Concurrency Control

MVCC stores multiple committed versions of a data item. A reader selects a version appropriate to its snapshot, while writers can often proceed without blocking readers. Consequently, read-heavy workloads obtain high concurrency.

A snapshot is not necessarily current: a transaction may consistently see data as of its logical start time. MVCC must eventually remove versions that no active transaction can see; this process is called garbage collection or vacuuming, depending on the DBMS. Long-running transactions can prevent old versions from being reclaimed and can increase storage use. MVCC also requires careful handling of write-write conflicts and, at stronger isolation levels, predicate or serialization conflicts.

Isolation Levels and Anomalies

Isolation levels represent a performance-correctness trade-off. Terminology is standardized in broad form, but exact behavior differs among DBMS products.

• Read uncommitted: may allow dirty reads, in which a transaction reads another transaction’s uncommitted change.
• Read committed: prevents dirty reads, but a repeated query may see a different committed value because another transaction commits between executions.
• Repeatable read: generally prevents changes to rows already read, though phantom rows or implementation-specific anomalies may remain.
• Serializable: provides behavior equivalent to some serial execution. It may be implemented by strict locking, predicate locks, serialization graphs, or serializable MVCC.

Common anomalies include:

• Lost update: one write overwrites another update.
• Dirty read: a transaction reads data later rolled back.
• Nonrepeatable read: the same row yields different committed values within one transaction.
• Phantom read: repeating a predicate query returns a different set of rows because matching rows were inserted or deleted.
• Write skew: two transactions read overlapping information and update different rows, jointly violating a constraint. Snapshot isolation may prevent many anomalies but does not automatically guarantee full serializability.

Isolation should be selected per business risk. A public product catalogue may tolerate read committed, whereas inventory allocation or financial settlement may require serializable behavior.

Deadlocks and Starvation

A deadlock occurs when transactions wait permanently for one another. For example, T1 holds X(A) and requests X(B), while T2 holds X(B) and requests X(A). A wait-for graph contains a node per transaction and an edge T_i → T_j when T_i waits for a lock held by T_j. A cycle indicates deadlock.

Deadlocks can be handled by:

• prevention: impose an ordering on data items or use timestamp schemes such as wait-die and wound-wait;
• avoidance: grant a request only when the resulting state is safe, though this requires additional knowledge;
• detection and recovery: allow waiting, periodically find cycles, select a victim, roll it back, and release its locks;
• timeouts: abort a transaction waiting beyond a threshold, a simple but imperfect approximation.

Victim selection may consider rollback cost, amount of work completed, number of locks, priority, and previous aborts. Repeatedly selecting the same transaction can cause starvation, so systems should track restart history or increase priority.

Logging and Write-Ahead Recovery

Recovery uses a log stored on stable storage. Typical records include `<START T>`, `<T, X, old, new>`, `<COMMIT T>`, `<ABORT T>`, and checkpoint records. The old and new values support undo and redo.

Write-ahead logging (WAL) imposes two essential rules:

1. The log record describing a data change must reach stable storage before the changed database page is written to disk.

2. The commit record must reach stable storage before the DBMS confirms commit to the client.

WAL ensures that recovery has sufficient information. Systems may use immediate update, in which uncommitted pages can reach disk and recovery must undo losers, or deferred update, in which database pages are not written until commit and recovery primarily redoes committed changes.

A steal policy permits an uncommitted page to be written to disk; a no-steal policy forbids it. A force policy writes all changed pages at commit; a no-force policy does not. Modern systems commonly use steal/no-force for performance, making both undo and redo necessary.

Checkpoints and Crash Recovery

A checkpoint limits how far backward recovery must examine the log. A fuzzy checkpoint records active transactions and relevant dirty pages while normal processing continues. Recovery commonly has three conceptual phases:

1. Analysis: identify the most recent checkpoint, active transactions, and dirty pages.

2. Redo: repeat logged actions as necessary to reconstruct effects that may not have reached disk.

3. Undo: reverse changes of transactions that were active at the crash and never committed.

The exact algorithm varies. In ARIES-style recovery, redo repeats history and undo writes compensation log records so that recovery itself is restartable. A crash during recovery therefore does not invalidate the recovery process.

A checkpoint is not a substitute for backup. It helps recover from a crash affecting memory or database processes; it does not protect against corruption, accidental deletion, ransomware, or destruction of the storage system.

Backup, Restore, and Recovery Objectives

A full backup copies the complete database. An incremental backup copies changes since a selected prior backup, while a differential backup copies changes since the last full backup. Log or archive backups capture transaction history and can support point-in-time recovery.

Two operational objectives are important:

• Recovery point objective (RPO): the maximum acceptable amount of data loss measured in time.
• Recovery time objective (RTO): the maximum acceptable time to restore service.

Lower RPO may require frequent log shipping or synchronous replication; lower RTO may require replicas, automation, and tested failover. Replication improves availability but is not identical to backup: an accidental deletion can be replicated to every replica.

Backups should be encrypted, access-controlled, retained according to policy, geographically separated when appropriate, and regularly tested by restoration exercises. An untested backup is only an assumption of recoverability.

Applied Case: Illustrative Online Inventory Reservation

Background. An online retailer sells a limited-stock product. Each purchase transaction reads the available quantity, creates an order, and decreases inventory.

Problem. Two customers submit orders for the final unit at nearly the same time. If both transactions read quantity 1 before either writes, both may create orders and one update may be lost. The system may promise an item it cannot deliver.

Analysis. The inventory update and order creation form one logical transaction. The business invariant is that available inventory must not become negative and every confirmed order must correspond to a valid reservation. Read committed without suitable locking may not protect this invariant.

Approach. One solution uses a serializable transaction with an exclusive row lock on the inventory record. The transaction checks that quantity is at least one, decrements it, inserts the order, and commits. The second transaction waits; after the first commits, it reads quantity zero and returns an out-of-stock result. A conditional atomic update—conceptually, “decrease quantity where quantity > 0”—can also enforce the constraint, provided order creation and the inventory change share the same transaction. WAL guarantees that a confirmed order and inventory change survive a crash.

Outcome. Exactly one reservation succeeds. If the server crashes before commit, recovery undoes or ignores the incomplete transaction; if it crashes after commit acknowledgment, redo preserves the committed result.

Learning points. Business invariants determine isolation requirements. A successful SQL statement is not necessarily a successful business transaction. Constraints, appropriate locking or serializable validation, idempotent retry design, and tested recovery must work together.

Professional, Governance, and Contemporary Considerations

Transaction design affects latency, throughput, availability, and customer trust. Developers should keep transactions short, access data in a consistent order, avoid user interaction inside a transaction, and choose indexes that reduce lock duration. Retries must be safe: clients should use idempotency keys when repeating payment or order requests.

Audit logs should distinguish business events from technical recovery logs. Access to logs and backups may expose personal, financial, or proprietary information, so encryption, least privilege, retention limits, and regulatory obligations such as privacy and financial-record requirements must be considered. Recovery procedures should preserve auditability rather than silently rewriting history.

AI systems introduce additional concerns. Feature-store updates require consistent point-in-time data to avoid training–serving skew and label leakage. Model registries need atomic promotion of a model version together with its metadata and approval status. Experiment tracking benefits from immutable committed records. Automated systems should not trade away durability or audit controls merely to reduce latency.

Challenges and Limitations

No concurrency protocol is universally best. Strict locking can cause blocking and deadlocks; timestamp and optimistic methods may cause repeated aborts; MVCC consumes storage and can produce anomalies under snapshot isolation. Strong serializability can lower throughput, while weak isolation can produce subtle business errors. Distributed databases add network partitions, replica lag, clock issues, and coordination costs. Recovery algorithms also depend on reliable storage, correctly ordered log writes, and operational discipline.

Best Practices

1. Define business invariants before selecting an isolation level.

2. Keep transactions short and consistent in their lock acquisition order.

3. Use parameterized statements and constraints to protect data integrity.

4. Understand the exact isolation semantics of the chosen DBMS.

5. Monitor lock waits, deadlocks, transaction duration, log growth, and version retention.

6. Implement bounded, observable retries for serialization failures and deadlocks.

7. Protect, replicate, and regularly restore-test backups.

8. Separate crash recovery, backup recovery, and disaster recovery in operational plans.

9. Use idempotency keys for externally retried operations.

10. Document recovery objectives and test them under realistic failure scenarios.

Chapter Summary

Transactions group database operations into atomic units and are judged by atomicity, consistency, isolation, and durability. Schedules describe interleavings; precedence graphs test conflict serializability. Locking, timestamp ordering, optimistic validation, and MVCC offer different balances between correctness, blocking, storage, and rollback cost. Isolation levels expose different anomalies, so the appropriate level must follow the business invariant. Deadlocks require prevention, avoidance, detection, or recovery. WAL, checkpoints, undo, redo, and ARIES-style processing restore correct state after crashes. Backups and replication address broader failures but require encryption, governance, recovery objectives, and regular testing. In AI-enabled systems, transaction design is essential for reliable feature data, model metadata, experiments, and auditable operations.

Key Terms

Transaction: A logical unit of database work.

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

Consistency: Preservation of database constraints after commitment.

Isolation: Protection of concurrent transactions from improper interference.

Durability: Persistence of committed effects after failure.

Schedule: An ordered interleaving of transaction operations.

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

Precedence graph: A graph used to test conflict serializability.

Shared lock: A lock permitting compatible reads.

Exclusive lock: A lock required for writing.

Two-phase locking: Locking with separate growing and shrinking phases.

Deadlock: A cycle of transactions waiting for one another.

MVCC: Concurrency control using multiple data versions.

Dirty read: Reading an uncommitted value.

Write-ahead logging: Requiring log persistence before relevant data or commit acknowledgment.

Checkpoint: A recovery marker that limits log processing.

Undo: Reversal of effects of incomplete transactions.

Redo: Reapplication of logged effects needed after a crash.

RPO: Maximum acceptable time-based data loss.

RTO: Maximum acceptable time to restore service.

Review Questions

Short Answer Questions

1. Define atomicity and give one example of an atomicity failure.

2. What is the purpose of a precedence graph?

3. Distinguish a shared lock from an exclusive lock.

4. What is a dirty read?

5. State the two principal rules of write-ahead logging.

Long Answer Questions

1. Explain ACID properties and discuss how they interact in a banking transfer.

2. Describe two-phase locking, strict 2PL, and their effects on serializability and recovery.

3. Compare timestamp ordering, optimistic concurrency control, and MVCC.

4. Explain deadlock detection and recovery, including victim selection considerations.

5. Describe analysis, redo, and undo in crash recovery and explain the role of checkpoints.

Analytical / Application Questions

1. Construct a precedence graph for a supplied interleaved schedule and determine whether it is conflict-serializable.

2. Design a transaction for reserving the last item in inventory. Specify the isolation or locking strategy and explain how it prevents lost updates and overselling.

3. Recommend backup, logging, RPO, and RTO strategies for an ML feature store whose data must be recoverable after both a server crash and accidental deletion.

Multiple Choice Questions with Answers

Question 1

Which ACID property ensures that committed changes survive a system crash?

A. Atomicity

B. Consistency

C. Isolation

D. Durability

Correct Answer: D. Durability

Question 2

A precedence graph for a schedule contains a cycle. What does this establish?

A. The schedule is conflict-serializable

B. The schedule is not conflict-serializable

C. All transactions are independent

D. The schedule contains only read operations

Correct Answer: B. The schedule is not conflict-serializable

Question 3

Under strict two-phase locking, exclusive locks are normally held until:

A. The first read

B. The growing phase ends

C. Commit or abort

D. The next checkpoint

Correct Answer: C. Commit or abort

Question 4

Which pair of operations conflicts when performed by different transactions on the same item?

A. READ and READ

B. READ and WRITE

C. Two metadata operations only

D. Two lock requests for compatible shared locks

Correct Answer: B. READ and WRITE

Question 5

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

A. Dirty read

B. Lost update

C. Phantom read

D. Write skew

Correct Answer: A. Dirty read

Question 6

What is a principal advantage of MVCC?

A. It eliminates the need for storage

B. Readers can often proceed without blocking writers

C. It guarantees serializability at every isolation level

D. It prevents all deadlocks in every implementation

Correct Answer: B. Readers can often proceed without blocking writers

Question 7

What does a cycle in a wait-for graph indicate?

A. A checkpoint

B. A committed transaction

C. A deadlock

D. A successful validation

Correct Answer: C. A deadlock

Question 8

According to write-ahead logging, what must happen before a changed database page is written to disk?

A. The corresponding log record must reach stable storage

B. Every active transaction must abort

C. A full backup must be completed

D. All shared locks must be released

Correct Answer: A. The corresponding log record must reach stable storage

Question 9

Which recovery phase reverses effects of transactions that were incomplete at the crash?

A. Analysis

B. Redo

C. Undo

D. Validation

Correct Answer: C. Undo

Question 10

An RPO primarily describes:

A. The maximum acceptable service-restoration time

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

C. The number of locks per transaction

D. The number of replicas required

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