Solving Transaction Problems in DBMS Interviews

Having established what makes schedules correct (serializability), we now tackle how database systems guarantee correctness: lock-based concurrency control.

In interviews, lock analysis problems require you to trace lock acquisition and release, determine if schedules obey locking protocols, predict deadlocks before they occur, and reason about the tradeoffs between different locking strategies.

Locking is the bridge between theory and practice. While serializability tells us whether a schedule is correct, locking protocols tell us how to ensure every schedule a DBMS produces will be correct.

What Are Locks?

A lock is a mechanism that grants a transaction the right to access a data item in a specific mode. Before a transaction can read or write a data item, it must acquire an appropriate lock on that item.

Lock Types

The two fundamental lock types are:

Shared Lock (S-lock): Allows the transaction to READ the data item. Multiple transactions can hold shared locks on the same item simultaneously.

Exclusive Lock (X-lock): Allows the transaction to READ and WRITE the data item. Only one transaction can hold an exclusive lock on an item, and no other transaction can hold any lock on that item.

Lock Operations

• lock-S(X) or S(X): Request shared lock on item X
• lock-X(X) or X(X): Request exclusive lock on item X
• unlock(X) or U(X): Release lock on item X

Lock Semantics in Transaction Processing

When a transaction requests a lock:

1. Check compatibility: Is the request compatible with existing locks?
2. If compatible: Grant the lock immediately
3. If incompatible: Transaction must wait (blocked) until the conflicting lock is released

Critical rules:

• A transaction must acquire an S-lock before reading
• A transaction must acquire an X-lock before writing
• A transaction holds a lock until it explicitly releases it
• A transaction cannot request more locks after releasing any lock (in strict 2PL variants)

Two-Phase Locking (2PL) is the fundamental protocol that guarantees conflict serializability. The protocol divides each transaction's execution into two distinct phases:

The Two Phases

Phase 1: Growing Phase (Lock Acquisition)

• Transaction may acquire new locks
• Transaction may NOT release any locks
• Transaction is "growing" its set of locked items

Phase 2: Shrinking Phase (Lock Release)

• Transaction may release locks
• Transaction may NOT acquire any new locks
• Transaction is "shrinking" its set of locked items

The lock point is the moment when the transaction transitions from growing to shrinking—typically when it acquires its last lock.

Why 2PL Guarantees Serializability

Theorem: Any schedule of transactions that follow 2PL is conflict serializable.

Proof intuition: The lock point of each transaction represents the moment when it has "captured" all the data items it will ever use. Ordering transactions by their lock points gives a serial schedule that is conflict equivalent to the original.

If T₁'s lock point precedes T₂'s lock point, then:

• Either T₁ releases a lock before T₂ acquires it (no conflict)
• Or T₂ waits for T₁ (T₁ goes first in serial order)

This ordering property ensures no cycles in the precedence graph.

Basic 2PL ensures serializability but allows schedules that are not recoverable or cascadeless. To address these issues, stricter variants are used in practice:

Strict Two-Phase Locking (Strict 2PL / S2PL)

Rule: A transaction holds all its exclusive (X) locks until it commits or aborts.

Benefits:

• Ensures strict schedules (no other transaction reads or writes data written by T until T commits/aborts)
• Prevents dirty reads and lost updates
• Enables simple recovery: just undo uncommitted transactions

Rigorous Two-Phase Locking (Rigorous 2PL / R2PL)

Rule: A transaction holds ALL locks (both S and X) until it commits or aborts.

Benefits:

• Everything Strict 2PL provides, plus...
• Transaction appears to run atomically at its commit point
• Simplifies reasoning about transaction isolation
• Most restrictive, lowest concurrency, highest isolation

Sometimes a transaction needs to change the mode of an existing lock. This is called lock conversion.

Lock Upgrade (S → X)

A transaction holding an S-lock on X may need to later write X. Instead of releasing the S-lock and acquiring an X-lock (which would create a gap where another transaction could intervene), the transaction requests an upgrade from S to X.

Upgrade semantics:

• If no other transaction holds an S-lock on X: Upgrade granted immediately
• If other transactions hold S-locks on X: Request must wait until all other S-locks are released

Lock Downgrade (X → S)

A transaction holding an X-lock on X has finished writing but still needs to read. It can downgrade from X to S, allowing other transactions to also hold S-locks.

Downgrade semantics:

• Always succeeds immediately (we already have exclusive access)
• Increases concurrency by allowing other readers

Lock Upgrade Deadlock

A particularly nasty situation occurs when two transactions each hold S-locks on the same item and both request upgrades:

T₁: S(A) ... upgrade(A) → waiting for T₂ to release S(A)
T₂: S(A) ... upgrade(A) → waiting for T₁ to release S(A)

This is a deadlock! Neither can proceed because each is waiting for the other's S-lock to be released before their upgrade can succeed.

Update Locks (U-locks): The Solution

Some systems use update locks (U-locks) to prevent upgrade deadlocks:

• U-lock is compatible with S-locks (multiple readers allowed)
• U-lock is NOT compatible with other U-locks or X-locks
• U-lock can be upgraded to X-lock when no S-locks remain

This ensures at most one transaction can be "waiting to upgrade," preventing the circular wait.

Let's work through a comprehensive lock analysis problem that tests all concepts.

Problem

Given the following schedule with locking operations, analyze:

1. Does each transaction follow 2PL?
2. Which variant of 2PL (if any)?
3. Are there any blocking situations?
4. What is the final serialization order?

Analysis

T₁ 2PL Check:

• Growing: X(A), S(B)
• Shrinking: U(A), U(B)
• No lock acquired after any unlock ✓
• Follows Basic 2PL
• X-lock released before commit → NOT Strict 2PL

T₂ 2PL Check:

• Growing: X(B)
• Shrinking: U(B)
• No lock acquired after unlock ✓
• Follows Basic 2PL
• X-lock released before commit → NOT Strict 2PL

T₃ 2PL Check:

• Growing: S(A)
• Shrinking: U(A)
• No lock acquired after unlock ✓
• Follows Basic 2PL
• Only S-lock held, question of Strict 2PL doesn't apply to S-locks

Blocking Analysis:

• T₃ blocked by T₁ (waiting for S(A) while T₁ holds X(A))
• T₂ blocked by T₁ (waiting for X(B) while T₁ holds S(B))

Serialization Order: Lock points: T₁ first (acquired both locks before T₂ or T₃ acquired theirs) T₂ and T₃ acquired locks only after T₁ released

Equivalent serial order: T₁ → (T₂ or T₃ in either order, they don't conflict)

In real database systems, the question of what to lock is as important as how to lock.

Granularity Levels

Locks can be acquired at different levels of the data hierarchy:

1. Database level: Lock entire database
2. Table level: Lock entire table
3. Page level: Lock a disk page (typically 4-16KB)
4. Row level: Lock individual rows
5. Field level: Lock individual columns (rare)

Trade-off: Concurrency vs. Overhead

Fine granularity (row-level):

• Pro: High concurrency—many transactions can work on different rows
• Con: High overhead—many locks to acquire, maintain, and release

Coarse granularity (table-level):

• Pro: Low overhead—few locks needed
• Con: Low concurrency—transactions block each other unnecessarily

Intention Locks

Intention locks solve the problem of efficiently checking lock compatibility across granularity levels.

Problem: If T₁ wants to lock table T exclusively, it must check that no row in T is locked. Scanning all rows is expensive!

Solution: Before locking a row, acquire an intention lock on the parent (table). The intention lock signals "some row is locked" without locking the whole table.

Intention Lock Types:

• IS (Intention Shared): Transaction intends to acquire S-locks on some descendants
• IX (Intention Exclusive): Transaction intends to acquire X-locks on some descendants
• SIX (Shared + Intention Exclusive): S-lock on node + IX on descendants (read all, write some)

Lock analysis questions in interviews follow predictable patterns. Here's how to recognize and solve each type efficiently.

Lock analysis connects abstract serializability theory to practical database implementation. Let's consolidate the essential skills:

What's Next:

With lock analysis mastered, we'll tackle Deadlock Detection—understanding why deadlocks occur, how to detect them through wait-for graphs, and the various strategies for prevention, avoidance, and resolution.