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

Source: https://skills101.in/learn/dbms-sql/dbms-concurrency-control — Skills101 free tutorial (DBMS & SQL). Updated 2026-11-21.

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 item | Conflict? | Why |
|---|---|---|
| R1(A), R2(A) | no | two reads never change anything |
| R1(A), W2(A) | yes | the order decides which value T1 sees |
| W1(A), R2(A) | yes | the order decides which value T2 sees |
| W1(A), W2(A) | yes | the order decides the final value |
| W1(A), W2(B) | no | different 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:

```python
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))
```

```text
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](https://skills101.in/learn-img/dbms-sql/precedence-graph.svg)

**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](https://skills101.in/learn-img/dbms-sql/two-phase-locking.svg)

| Variant | Rule | Gives |
|---|---|---|
| Basic 2PL | grow, then shrink | conflict serializable; cascading rollbacks still possible |
| **Strict 2PL** | hold all **exclusive** locks until commit/abort | also strict, so cascadeless — used by most databases |
| Rigorous 2PL | hold **all** locks until commit/abort | simplest; 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):

| Scheme | Older Ti requests a lock held by younger Tj | Younger Ti requests a lock held by older Tj |
|---|---|---|
| **Wait-die** | Ti **waits** | Ti **dies** (aborts, restarts later with the same timestamp) |
| **Wound-wait** | Ti **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 quiz and free certificate: https://skills101.in/learn/dbms-sql/dbms-concurrency-control