11.2 Concurrency Exceptions, Scheduling, and Serializability

When two windows simultaneously update inventory, each one sees its own change as successful, but when the results are merged, the final state violates the business rules of the Archive City system.

---

Metadata Card

• Prerequisites: 11.1 Transaction Boundaries, ACID, and Failure Semantics
• Keywords: concurrency exceptions, scheduling, 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 Several Types of Exceptions

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

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

Scheduling is the interleaving order of operations

Serial scheduling executes all operations of transaction T1 before starting any operations of T2. Serializable scheduling 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 Priority 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 priority graph, so the schedule is not conflict serializable. 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.

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

There exist view serializable schedules that are not 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.

Production databases typically prohibit dirty writes and dirty reads, and hold write locks until transaction completion to prevent cascading rollbacks. In contrast, MVCC allows ordinary reads to see only committed versions of data.

Treat Retries as Part of a Transaction Interface

Serializable does not guarantee that every attempt will succeed, it only guarantees that successfully committed transactions exhibit serializable semantics. PostgreSQL returns SQLSTATE 40001 for serialization failures; deadlock failures typically return 40P01. 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 just two non-conflicting operations could eliminate the cycle.

Section Checkpoint

• Can describe anomalies based on whether they're committed, whether they occur on the same line or within a predicate range, and whether they involve read-after-write or atomic updates.
• Can construct a priority 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.