Search Knowledge

© 2026 LIBREUNI PROJECT

Database Systems/Transactions and recoverable execution
Page 12 of 20

Transactions and Isolation

Specify what a transaction promises, trace anomalies, and choose an isolation contract that protects a stated invariant.

Lesson briefTransactions and recoverable execution · 8 h · 4 outcomes

Required knowledge

  • SQL reads, writes, constraints, and predicate semantics
  • Directed graphs and topological order
  • Durable pages, logs, and the distinction between logical and physical state

Learning outcomes

  • Separate atomicity, durability, and application consistency from the visibility guarantee called isolation.
  • Construct a precedence graph for a history and use acyclicity to establish conflict serializability.
  • Trace lost update and write skew, then select a constraint, atomic statement, serialization rule, or retry boundary that repairs the named invariant.
  • State a transaction's safe retry boundary, including why external side effects need idempotency.

Assessment target

Given an unseen concurrent history and application invariant, classify the anomaly, derive the serializability evidence, and propose a correct repair with its retry and external-effect boundary.

Scope boundary

  • Formal proofs of view serializability, every vendor's isolation implementation, and distributed commit protocols are deferred.
  • Lock-manager algorithms and MVCC garbage collection mechanics receive focused treatment in concurrency control rather than here.

Two buyers press “reserve” for the last seat. The application cannot treat two individually successful reads as proof that both reservations fit. It needs one unit of work whose committed outcome preserves available_seats >= 0, and it must say what a crash, competing transaction, or retry may observe.

ACID separates obligations that are often conflated

ClaimConcrete questionWhat it does not promise
AtomicityCan a crash expose only the debit, not the credit?that the completed transfer was authorized
ConsistencyDo commits preserve declared and encoded business invariants?that an unexpressed rule is magically checked
IsolationWhich concurrent writes/read effects can this transaction see?an absence of aborts or retries
DurabilityAfter acknowledgement, which failures retain the commit?survival of every regional or adversarial event

For a reservation, a row-local invariant can often be enforced by one conditional statement:

UPDATE seat_inventory
SET available = available - :requested
WHERE event_id = :event_id
  AND available >= :requested;

An affected-row count of zero means the predicate was false at the protected update boundary; it is not a successful reservation. This is stronger than SELECT available, computing in the application, then issuing an unconditional update.

Prediction — retry scope

A transaction inserts an order, reserves inventory, commits, then calls a payment provider. The network times out after the call. Should the client blindly repeat the whole sequence?

HintExpand

Separate a database rollback-safe action from an externally visible action that may already have occurred.

Worked solutionExpand

No. Retrying the database transaction before knowing the previous commit can duplicate inventory or orders; retrying the provider call can double-charge. Commit an outbox or an idempotency key with the database work, then make the provider operation retryable against that stable key. Isolation protects database histories; it does not make an external API atomic with them.

Histories can be tested with a precedence graph

Theorem 4.1.1Conflict-serializability test

Build a graph with one node per transaction. Add Ti→TjT_i \rightarrow T_j when an operation of TiT_i precedes and conflicts with an operation of TjT_j on the same item; a conflict has the same item and at least one write. The history is conflict-serializable exactly when this graph is acyclic.

Code
rectangle "T1\nread A\nwrite A" as T1
rectangle "T2\nread A\nwrite B" as T2
rectangle "T3\nread B" as T3
T1 --> T2 : A write → read
T2 --> T3 : B write → read
note right of T3
No edge returns to T1,
so T1, T2, T3 is
one serial order.
end note
T1read Awrite AT2read Awrite BT3read BNo edge returns to T1,so T1, T2, T3 isone serial order.A write → readB write → read

Reads of the same item do not conflict. A write followed by a read, a read followed by a write, or two ordered writes does. An acyclic graph yields a topological order that preserves every conflict order. A cycle is stronger evidence than a suspicious final balance: it proves no serial ordering can retain all observed conflicts.

Worked trace — a lost update

Start with available = 20. T1 reads 20 and plans to subtract 7. T2 reads 20 and plans to subtract 7. T1 writes 13; T2 then writes 13. The intended serial result is 6, but the final result is 13: one subtraction disappeared. The writes create a cycle when each transaction’s read/write dependencies are represented, so a serializable protocol must block, abort, or otherwise reject one path.

Interactive exploration

Expose a lost update in the schedule

Advance the interleaving. Both transactions read the same version, so the second write overwrites rather than composes with the first.

0 of 6 events applied
Schedule step: 0 of 6
  1. 1T₁ reads x=0
  2. 2T₂ reads x=0
  3. 3T₁ computes x+1
  4. 4T₂ computes x+1
  5. 5T₁ writes x=1
  6. 6T₂ writes x=1
T₁ local—
T₂ local—
database x0

The final value alone cannot explain the anomaly. The read-from relation and write order show why both commits are individually valid but the pair is not equivalent to serial execution.

Expose a lost update in the schedule
  1. 1T₁ reads x=0
  2. 2T₂ reads x=0
  3. 3T₁ computes x+1
  4. 4T₂ computes x+1
  5. 5T₁ writes x=1
  6. 6T₂ writes x=1
T₁ local1
T₂ local1
database x1

A schedule is the evidence: two successful transactions can still violate the intended increment invariant.

Use the schedule explorer to commit to the observed value before revealing its explanation. It models a read-modify-write lost update; it is not evidence that every database’s named isolation levels behave identically.

Snapshot visibility has a known boundary

Counterexample. “At least one doctor remains on call” can fail even when each transaction reads a consistent snapshot. T1 reads doctors A and B and turns A off; T2 reads the same snapshot and turns B off. The writes are disjoint, both commit, and no doctor remains.

Code
participant "T1" as T1
participant "T2" as T2
database "on_call" as D
T1 -> D : read A=true, B=true
T2 -> D : read A=true, B=true
T1 -> D : write A=false
T2 -> D : write B=false
note right of D
Each row update succeeds;
the predicate invariant fails.
end note
T1T2on_callT1T1T2T2on_callon_callread A=true, B=trueread A=true, B=truewrite A=falsewrite B=falseEach row update succeeds;the predicate invariant fails.

Snapshot isolation often prevents dirty reads and many read anomalies while allowing readers and writers to proceed concurrently. It does not automatically serialize predicates over several rows. A serializable level may detect a dangerous dependency and abort one transaction; another repair is to lock/update a summary row that represents the invariant, or to encode a viable declarative constraint where possible.

RequirementReliable repair shapeWhy a weaker shortcut fails
no duplicate emailunique constraintSELECT then INSERT races
nonnegative stock in one rowconditional UPDATE ... WHERE stock >= na prior read becomes stale
at least one on-call doctorserializable validation or protected summary/predicaterow-local updates are disjoint
price + order snapshot agreesame transaction and foreign-key/version rulesapplication-side sequencing can expose a prefix

Application — pick the conflict boundary

A tenant has a monthly credit limit across many invoices. Two requests each read remaining credit and add a different invoice. Name a repair and state the price it pays.

Worked solutionExpand

Maintain a tenant-month summary row and update it conditionally in the same transaction, or use serializable isolation with a retry on serialization failure. The summary row makes the aggregate invariant a shared write boundary but can become hot; serializable validation preserves flexibility but can abort more often under contention. A normal row lock on each new invoice does not protect the aggregate predicate.

Isolation labels require an implementation contract

PostgreSQL, for example, documents Read Committed, Repeatable Read, and Serializable behavior, treats Read Uncommitted as Read Committed, and may report a serialization failure that the application must retry. That is an implementation example, not a license to generalize its exact snapshot boundary to another engine.

Transfer — design a test rather than trust the label

You are told a service uses “repeatable read.” Give the smallest experiment that reveals whether it protects the on-call invariant.

HintExpand

Run the two disjoint writes concurrently and retain outcome evidence, not just the final rows.

Worked solutionExpand

Create two on-call rows, begin two transactions at the claimed level, have both read the predicate, have each disable a different doctor, then commit. Record blocking, errors, commits, and the final predicate. If both commit with no doctor on call, the level does not protect this invariant; add a serializable/summary/predicate-based repair and rerun the same schedule.

Section Exercises

Deep Practice

Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.

Exercise 4.1.1: Conflict-Serializability Precedence Graph Construction

Verificationapplication

Consider history H=r1(A)  r2(B)  w1(B)  w2(A)  c1  c2H = r_1(A)\; r_2(B)\; w_1(B)\; w_2(A)\; c_1\; c_2 Using Theorem 4.1.1, construct the serialization graph and verify whether HH is conflict-serializable.

HintExpand

Identify conflicting operation pairs on the same data item and draw directed edges.

Worked solutionExpand

The conflicting pairs are:

  1. r2(B)r_2(B) precedes w1(B)w_1(B) on item BB inducing directed edge T2→T1T_2 \to T_1
  2. r1(A)r_1(A) precedes w2(A)w_2(A) on item AA inducing directed edge T1→T2T_1 \to T_2 The serialization graph contains the cycle T1→T2→T1T_1 \to T_2 \to T_1 By Theorem 4.1.1, because the graph contains a directed cycle, the history HH is not conflict-serializable.

Exercise 4.1.2: Write Skew Anomaly under Snapshot Isolation

Descriptionrecall

Explain why snapshot isolation permits write skew in the classic hospital on-call problem (where at least one doctor must remain active) while preventing dirty reads, non-repeatable reads, and lost updates.

HintExpand

Each transaction reads the shared active count but modifies disjoint doctor rows.

Worked solutionExpand

Under snapshot isolation, transactions read from a consistent snapshot taken at start and check for write conflicts only on the specific rows they update (first-committer-wins). In write skew, transaction T1T_1 updates doctor AA while T2T_2 updates doctor BB Because their write sets {A}\{A\} and {B}\{B\} are disjoint, no write-write conflict is detected, and both commit. However, their commit decisions depended on each other’s state, violating the multi-row invariant.

Exercise 4.1.3: Multi-Invoice Aggregate Credit Limit Protection

Constructionapplication

A business requires that the total of all unpaid invoices for a tenant cannot exceed credit limit LL Two concurrent transactions attempt to insert new invoices for tenant 12. Specify two alternative architectural mechanisms to prevent exceeding LL under concurrent execution.

HintExpand

Consider explicit lock serialization on a parent row versus serializable snapshot isolation.

Worked solutionExpand
  1. Explicit parent row lock: Each transaction begins by executing SELECT * FROM Tenant WHERE tenant_id = 12 FOR UPDATE;. This serializes all invoice additions for tenant 12, forcing each transaction to read the committed sum of prior transactions before inserting.
  2. Serializable isolation: Run both transactions at SERIALIZABLE isolation. The database tracks predicate read dependencies and aborts one transaction with a serialization error (40001), requiring the application to retry.

Exercise 4.1.4: Empirical Isolation Level Validation Harness

Generalisationtransfer

Design an automated test harness to empirically verify whether a database’s declared REPEATABLE READ isolation level is vulnerable to write skew. Define the initial database fixture, the interleaved operations of two concurrent sessions, and the assertion that detects invariant violation.

HintExpand

Seed two doctors on call, have two concurrent threads each take one doctor off call, then assert final count.

Worked solutionExpand
  1. Fixture: Insert Doctor(id, on_call) with rows (1, true) and (2, true). Invariant: COUNT(*) FILTER (WHERE on_call) >= 1.
  2. Schedule:
    • Session 1: BEGIN ISOLATION LEVEL REPEATABLE READ; reads active count (2).
    • Session 2: BEGIN ISOLATION LEVEL REPEATABLE READ; reads active count (2).
    • Session 1: UPDATE Doctor SET on_call = false WHERE id = 1; COMMIT;
    • Session 2: UPDATE Doctor SET on_call = false WHERE id = 2; COMMIT;
  3. Assertion: Query SELECT COUNT(*) FROM Doctor WHERE on_call = true;. If count is 0, both committed and write skew occurred, proving the level is snapshot isolation rather than true serializability.

References & Further Reading