11.2 Concurrency Anomalies, Schedules, and Serializability

---

Metadata Card

• Prerequisites: 11.1 Transaction Boundaries, ACID, and Failure Semantics
• Keywords: concurrency anomalies, schedules, conflict graph, serializability, retry
• Code Languages: SQL, scheduling markers

---

"Two queries return different results" is just the surface symptom. When analyzing concurrency issues, you must simultaneously track who read what, who wrote what, whether modifications were committed, and which rows or ranges the business logic depends on.

Distinguish Among Concurrency Anomalies

Let R1(A) represent transaction T1 reading value A, and W2(A) represent transaction T2 writing to A.

Anomaly	Key Condition	Risk
Dirty Read	Reading a write from another transaction that has not yet been committed	Making decisions based on data that will eventually be rolled back
Dirty Write	Overwriting a write from another transaction that has not yet been committed	The order of rollbacks undermines the consistency of committed results
Non-Repeatable Read	Seeing a new version of the same row after re-reading it	A shifting baseline within a transaction leads to inconsistent judgments
Phantom Read	After re-executing the same predicate query, the set of rows matching the condition changes	Invariants over ranges are violated
Lost Update	Multiple transactions base their updates on stale reads and overwrite each other	A business update vanishes silently
Write Skew	Multiple transactions read the same set of constraints but write to different rows	Individual rows may not conflict, yet the constraint set is violated

"Lost update" cannot be judged solely by the name of the isolation level. The following two scenarios behave differently:

-- The database performs atomic increments directly on the current row; concurrent writes typically serialize and wait.
UPDATE counter SET value = value + 1 WHERE counter_id = 1;

T1: SELECT value → 10
T2: SELECT value → 10
T1: UPDATE ... SET value = 11
T2: UPDATE ... SET value = 11

The second case (where the application performs read-modify-write) poses a higher risk of losing updates. Atomic SQL, SELECT ... FOR UPDATE, versioned conditions, or Serializable isolation can be used to protect against this, rather than assuming that any given isolation level automatically resolves all update loss scenarios.

A Schedule Is an Interleaving of Operations

The counter SQL above is a mechanism fragment requiring an existing counter(counter_id, value) table and target row. In PostgreSQL 16+ at Read Committed, two atomic increments should turn an initial value of 10 into 12. Higher isolation levels may instead raise a conflict that requires retrying.

A serial schedule executes all operations of transaction T1 before starting any operations of T2. A serializable schedule allows interleaving, but the final outcome after successful commit must be equivalent to some serial execution order.

To determine whether a schedule is conflict-serializable, two operations conflict only if all of the following conditions are met:

1. They belong to different transactions;
2. They access the same logical data item;
3. At least one of them is a write operation.

Thus, read–read operations do not conflict, while read–write, write–read, and write–write operations do conflict.

Using a Precedence Graph to Determine Conflict Serializability

Consider this explicitly ordered schedule:

R1(A)  W1(A)  R2(A)  W2(B)  R1(B)  C1  C2

Examine each pair of operations for conflicts:

• W1(A) occurs before R2(A), resulting in an edge T1 → T2;
• W2(B) occurs before R1(B), resulting in an edge T2 → T1.

A cycle T1 → T2 → T1 appears in the precedence graph, so the schedule is not conflict serializable. It also contains dirty reads and is a single-version theory example; ordinary PostgreSQL SELECT statements will not reproduce these reads of uncommitted versions. If the graph is acyclic, a topological sort of the graph yields a valid equivalent serial order.

Do not merely list operations within individual transactions while ignoring the global interleaving order; without the global sequence, it's impossible to determine edge directions and thus to detect cycles.

Conflict Serializability Is Not the Whole Theory

View equivalence also requires:

• Transactions that read initial values must be identical;
• The transactions upon which each read depends must be the same;
• The final writer of each data item must be the same.

Schedules containing blind writes can be view serializable without being conflict serializable. In practice, systems more commonly design their protocols around conflict dependencies, because detecting cycles in conflict graphs is straightforward, whereas determining view serializability in general is significantly more complex.

It's also important to distinguish between "conflict serializable histories" and SQL's SERIALIZABLE isolation level. Databases can implement strict two-phase locking, or adopt approaches like PostgreSQL's SSI (Serializable Snapshot Isolation) to detect dangerous read-write dependencies. The implementation does not necessarily construct the full teaching graph described in this section at runtime.

Recoverability and Cascading Rollbacks

Serializable isolation ensures that the outcome of concurrent execution is equivalent to some serial order. Recoverability ensures that the commit order of transactions is safe: if transaction T2 reads data written by T1, T2 must not commit before T1; if T1 rolls back last, then T2 must also roll back.

At isolation levels that prohibit dirty reads, readers do not depend on another transaction's uncommitted writes, avoiding that form of cascading rollback. Ordinary MVCC reads generally select committed visible versions and also see earlier changes in their own transaction. Products that permit Read Uncommitted need separate treatment.

Treat Retries as Part of a Transaction Interface

Serializable does not guarantee that every attempt will succeed; it guarantees that successfully committed transactions exhibit serializable semantics. PostgreSQL retry rules specify SQLSTATE 40001 for serialization failures and 40P01 for deadlocks. Applications should retry the entire transaction, rather than replay the last SQL statement alone.

repeat up to retry_limit:
    begin
    try:
        execute all reads, decisions, and writes
        commit
        return success
    catch retryable_transaction_error:
        rollback
        wait with bounded exponential backoff and jitter
fail or send to recovery path

Retries must satisfy three conditions:

• External side effects outside the transaction must be idempotent or deferred to an outbox;
• Each retry must start fresh by re-reading from the beginning; previous failure state within the transaction must not be reused;
• There must be defined retry limits, total timeout, and monitoring to prevent hot-spot conflicts from triggering infinite retry storms.

Exercise

Given the schedule:

R1(A)  W2(A)  R3(B)  W1(B)  R2(B)  C1  C2  C3

Complete the following tasks:

1. List all conflicting edges between transactions;
2. Determine whether a cycle exists in the graph;
3. If no cycle exists, provide a topological order; if a cycle exists, identify the edges that form the cycle;
4. Explain whether swapping two non-conflicting operations changes the verdict.

Check: the edges are T1 → T2, T3 → T1, and T3 → T2. The graph is acyclic, with topological order T3, T1, T2. Swapping adjacent non-conflicting operations preserves the conflict edges. Although this schedule is conflict serializable, T2 reads T1's B write before T1 commits; recoverability still needs a separate check if those reads are permitted.

Section Checkpoint

• Can describe anomalies based on whether they're committed, whether they occur on the same row or within a predicate range, and whether they involve read-modify-write or atomic updates.
• Can construct a precedence graph from a complete schedule, rather than guessing edges based on transaction names.
• Understands that serializability does not mean failure-free execution, and can design retry boundaries for entire transactions.

The next chapter introduces MVCC, explaining how databases select the correct version for a given read and why the same isolation level behaves differently across products.