Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › DBMS

Concurrency Control, Schedules and Locking

A database runs many transactions at the same time for speed. Concurrency control makes sure the result is the same as if they had run one after another — the I (Isolation) in ACID.

What can go wrong

Problem What happens Example
Lost update two writes, one overwrites the other T1 and T2 both read balance 100, add 50 and 20 → final 120 instead of 170
Dirty read read data another transaction hasn't committed T2 reads T1's change, T1 rolls back
Non-repeatable read the same row read twice gives different values T2 updates the row between T1's two reads
Phantom read the same query returns new rows T2 inserts a row matching T1's WHERE

Schedules

A schedule is the order in which operations (R = read, W = write) of several transactions run.

Conflicting operations

Two operations conflict if they are from different transactions, on the same data item, and at least one is a write:

Pair Conflict?
R(A) – R(A) ❌
R(A) – W(A) ✅
W(A) – R(A) ✅
W(A) – W(A) ✅

Conflict serializability — the precedence graph test

  1. Make a node for each transaction.
  2. For each conflicting pair where Ti's operation comes before Tj's, draw an edge Ti → Tj.
  3. No cycle → conflict serializable. A topological order of the graph gives the equivalent serial order.

Example

S: R1(A) W1(A) R2(A) W2(A) R1(B) W1(B) R2(B) W2(B)

Conflicts: W1(A)→R2(A), W1(B)→R2(B) … all edges are T1 → T2. No cycle → serializable, equivalent to T1, T2.

S: R1(A) R2(A) W1(A) W2(A)

R1(A)→W2(A) gives T1→T2; R2(A)→W1(A) gives T2→T1 → cycle → not conflict serializable (this is the lost-update pattern).

View serializability is a weaker condition (same initial reads, same reads-from, same final writes). Every conflict-serializable schedule is view-serializable, not the reverse; a view-serializable but not conflict-serializable schedule always contains a blind write (write without reading first). Testing view serializability is NP-complete.

Recoverability

Type Rule Why
Recoverable if T2 reads from T1, T1 commits before T2 commits otherwise T2 commits data that may be rolled back
Cascadeless read only committed data one abort doesn't force a chain of aborts (cascading rollback)
Strict no read or write of an item until the last writer commits/aborts simplest recovery
Strict ⊂ Cascadeless ⊂ Recoverable.

Lock-based protocols

Held \ Requested S X
S ✅ grant ❌ wait
X ❌ wait ❌ wait

Two-Phase Locking (2PL)

  1. Growing phase: may acquire locks, may not release any.
  2. Shrinking phase: may release locks, may not acquire any.

The moment of the last lock acquired is the lock point. 2PL guarantees conflict serializability (serial order = order of lock points), but not freedom from deadlock, and plain 2PL can still give cascading rollbacks.

Variant Extra rule Gives
Basic 2PL — serializability
Strict 2PL hold all X locks until commit + cascadeless, strict schedules (used by most DBs)
Rigorous 2PL hold all locks until commit + serial order = commit order
Conservative 2PL take all locks before starting + no deadlock (hard in practice)

Deadlocks in databases

T1 locks A and waits for B; T2 locks B and waits for A. DBs detect cycles in a wait-for graph and abort one transaction (the victim), or prevent deadlocks with timestamps:

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 (restarts with the same timestamp)
Wound–Wait Ti wounds Tj (Tj aborts) Ti waits
Both ensure older transactions are favoured, so no starvation. More: Deadlocks.

Timestamp ordering

Each transaction gets a timestamp when it starts; operations must follow timestamp order. Each item keeps read_TS and write_TS.

Optimistic concurrency & MVCC

SQL isolation levels

Level Dirty read Non-repeatable read Phantom
Read Uncommitted possible possible possible
Read Committed (PostgreSQL, Oracle default) ❌ possible possible
Repeatable Read (MySQL InnoDB default) ❌ ❌ possible*
Serializable ❌ ❌ ❌
*InnoDB's next-key locks prevent most phantoms in practice.
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
BEGIN;
SELECT balance FROM accounts WHERE id = 1 FOR UPDATE;  -- lock the row
UPDATE accounts SET balance = balance - 500 WHERE id = 1;
COMMIT;

Higher isolation = fewer anomalies but less concurrency.

Interview one-liners

More DBMS notes