Skills101

AdvancedDBMS & SQL · Lesson 21 of 25 · Updated ·

Concurrency Control — Schedules, Conflict Serializability, Two-Phase Locking and Timestamps

The transactions lesson explained what can go wrong when transactions overlap — dirty reads, lost updates — and the isolation levels that prevent them. This lesson explains how a database decides whether an overlap is safe. It is a core unit in every DBMS syllabus and a favourite for numerical exam questions: "is this schedule conflict serializable?"

1. Schedules

A transaction is a sequence of reads R(X) and writes W(X) on data items. We write R1(A) for "transaction T1 reads A".

A schedule is the order in which the operations of several transactions actually run.

  • Serial schedule: one transaction runs completely, then the next. Always correct, but slow — no overlap at all.
  • Concurrent (non-serial) schedule: operations are interleaved. Faster, but only some interleavings are correct.

A concurrent schedule is serializable if its effect is the same as some serial schedule. That is the definition of "correct" for concurrency.

2. Conflicting operations

Two operations conflict if all three hold:

  1. They belong to different transactions.
  2. They touch the same data item.
  3. At least one of them is a write.
Pair on the same itemConflict?Why
R1(A), R2(A)notwo reads never change anything
R1(A), W2(A)yesthe order decides which value T1 sees
W1(A), R2(A)yesthe order decides which value T2 sees
W1(A), W2(A)yesthe order decides the final value
W1(A), W2(B)nodifferent items

Swapping two adjacent non-conflicting operations does not change the result. If swaps like that can turn a schedule into a serial one, it is conflict serializable.

3. The precedence graph test

Swapping by hand is slow. The standard test:

  1. Draw one node per transaction.
  2. For each conflicting pair where Ti's operation comes before Tj's, draw an edge Ti → Tj.
  3. If the graph has no cycle, the schedule is conflict serializable. A topological order of the graph gives an equivalent serial schedule.

Two schedules on the same item A (and B):

  • S1: R1(A), R2(A), W1(A), W2(A)
  • S2: R1(A), W1(A), R2(A), W2(A), R1(B), W1(B), R2(B), W2(B)

The code builds both graphs and checks them:

def precedence_edges(schedule):
    ops = [(int(op[1]), op[0], op[3]) for op in schedule.split()]   # (txn, R/W, item)
    edges = set()
    for i, (ti, ai, xi) in enumerate(ops):
        for tj, aj, xj in ops[i + 1:]:
            if ti != tj and xi == xj and 'W' in (ai, aj):
                edges.add((ti, tj))
    return sorted(edges)

def has_cycle(edges):
    graph = {}
    for a, b in edges:
        graph.setdefault(a, []).append(b)
    def reaches(start, target, seen):
        for nxt in graph.get(start, []):
            if nxt == target or (nxt not in seen and reaches(nxt, target, seen | {nxt})):
                return True
        return False
    return any(reaches(n, n, {n}) for n in graph)

for name, s in [('S1', 'R1(A) R2(A) W1(A) W2(A)'),
                ('S2', 'R1(A) W1(A) R2(A) W2(A) R1(B) W1(B) R2(B) W2(B)')]:
    e = precedence_edges(s)
    print(name, 'edges:', ['T%d->T%d' % p for p in e], '| serializable:', not has_cycle(e))
S1 edges: ['T1->T2', 'T2->T1'] | serializable: False
S2 edges: ['T1->T2'] | serializable: True

Precedence graphs: S1 has edges T1 to T2 and T2 to T1, a cycle, so it is not conflict serializable; S2 has only T1 to T2, so it is equivalent to the serial order T1 then T2

S1 is the lost update. Both read A, then both write it — whichever writes last wipes out the other. The cycle shows that no serial order explains it. S2 behaves exactly like "all of T1, then all of T2", even though B's operations were interleaved after A's.

There is a weaker, broader notion called view serializability. Every conflict serializable schedule is view serializable, but not the other way round. Testing view serializability is NP-complete, so real databases use conflict-based methods.

4. Recoverable and cascadeless schedules

Serializability is not enough when transactions can abort.

  • Recoverable: if T2 reads a value written by T1, then T1 must commit before T2 commits. Otherwise T2 might commit using data that T1 later rolls back — and a committed transaction cannot be undone.
  • Cascadeless: a transaction reads only committed values. This avoids cascading rollback, where one abort forces many others to abort.
  • Strict: no transaction reads or writes an item until the last transaction that wrote it has committed or aborted. Strict schedules make recovery simple.

Strict ⊂ cascadeless ⊂ recoverable: every strict schedule is cascadeless, and every cascadeless schedule is recoverable.

5. Two-phase locking (2PL)

Databases do not draw graphs while running. They use locks so that only serializable schedules can happen.

  • Shared lock S(X) for reading — many transactions can hold it together.
  • Exclusive lock X(X) for writing — only one transaction, and no shared locks at the same time.

Two-phase locking rule: each transaction has

  1. a growing phase — it may acquire locks but not release any;
  2. a shrinking phase — after its first release, it may not acquire any new lock.

The moment of the last lock acquired is the lock point. 2PL guarantees conflict serializability: transactions are equivalent to the serial order of their lock points.

Two-phase locking: the number of locks held rises during the growing phase up to the lock point, then falls during the shrinking phase; in strict 2PL exclusive locks are held until commit

VariantRuleGives
Basic 2PLgrow, then shrinkconflict serializable; cascading rollbacks still possible
Strict 2PLhold all exclusive locks until commit/abortalso strict, so cascadeless — used by most databases
Rigorous 2PLhold all locks until commit/abortsimplest; serial order = commit order

2PL does not prevent deadlocks: T1 holds A and waits for B while T2 holds B and waits for A.

6. Handling deadlocks

  • Detection: build a wait-for graph (Ti → Tj if Ti waits for a lock Tj holds). A cycle means a deadlock; abort one transaction (the "victim"), usually the youngest or the one with least work done.
  • Prevention with timestamps — each transaction gets a timestamp when it starts (smaller = older):
SchemeOlder Ti requests a lock held by younger TjYounger Ti requests a lock held by older Tj
Wait-dieTi waitsTi dies (aborts, restarts later with the same timestamp)
Wound-waitTi wounds Tj (Tj aborts)Ti waits

In both schemes the older transaction is never aborted because of a younger one, so every transaction eventually becomes the oldest and finishes — no starvation.

  • Timeout: abort a transaction that has waited longer than a limit. Simple, and common in practice.

7. Timestamp ordering (no locks)

Each transaction gets a timestamp TS. Each item X remembers read_TS(X) and write_TS(X) — the largest timestamps that read and wrote it. The rule: operations must happen as if transactions ran in timestamp order.

  • Ti wants R(X): if TS(Ti) < write_TS(X), a younger transaction already wrote X → abort Ti. Otherwise read, and update read_TS(X).
  • Ti wants W(X): if TS(Ti) < read_TS(X) or TS(Ti) < write_TS(X) → abort Ti. Otherwise write, and set write_TS(X) = TS(Ti).

Thomas write rule: if TS(Ti) < write_TS(X) but no younger transaction has read X, the write is simply ignored (it would be overwritten anyway) instead of aborting Ti.

Timestamp ordering never deadlocks (no one waits), but it may abort and restart transactions often.

MVCC (multi-version concurrency control), used by PostgreSQL, MySQL InnoDB and Oracle, keeps several versions of each row. Readers see a consistent snapshot and never block writers. That is why a long report does not freeze the order system.

Common mistakes

  • Counting two reads as a conflict. At least one operation must be a write.
  • Drawing the edge the wrong way. The edge goes from the transaction whose operation comes first.
  • Thinking 2PL prevents deadlocks. It guarantees serializability; deadlocks still need detection or prevention.
  • Mixing up wait-die and wound-wait. In both, the older transaction wins; they differ in whether the younger waits or dies.
  • Saying a serializable schedule is always recoverable. Recoverability is a separate condition.

Quick recap

  • Serializable = same effect as some serial schedule.
  • Conflict: different transactions, same item, at least one write.
  • Precedence graph with no cycle → conflict serializable; topological order = equivalent serial order.
  • Recoverable ⊃ cascadeless ⊃ strict.
  • 2PL (grow then shrink) guarantees serializability; strict 2PL holds exclusive locks to commit.
  • Deadlocks: wait-for graph, wait-die, wound-wait, timeouts. Timestamp ordering and MVCC avoid locks for reads.

Practice what you learned

📝 Quiz: Concurrency Control5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →