8.1 Concurrency Anomalies & SQL Isolation Levels
When multiple transactions execute concurrently without adequate isolation, interference between interleaved read and write operations produces four classical data anomalies.
Figure 8.1: Concurrency anomalies arise when transactions interleave reads and writes on overlapping records.
ANSI SQL-92 Transaction Isolation Levels
| Isolation Level | Dirty Read | Non-repeatable Read | Phantom Read |
|---|---|---|---|
| Read Uncommitted | Allowed | Allowed | Allowed |
| Read Committed | Prevented | Allowed | Allowed |
| Repeatable Read | Prevented | Prevented | Allowed |
| Serializable | Prevented | Prevented | Prevented |
8.2 Lock-Based Protocols & Two-Phase Locking (2PL)
To guarantee that concurrent transaction execution schedules are Conflict Serializable, database engines enforce lock protocols. A lock grants exclusive or shared permission over a data item.
Shared (S) vs Exclusive (X) Locks
- Shared Lock ($S$): Acquired before reading. Multiple transactions can hold shared locks concurrently on the same item ($S leftrightarrow S$ compatible).
- Exclusive Lock ($X$): Acquired before writing. Only one transaction can hold an exclusive lock; all other concurrent requests are blocked ($X$ is incompatible with both $S$ and $X$).
Figure 8.2: In basic 2PL, a transaction acquires locks during its growing phase until reaching the Lock Point, after which it enters the shrinking phase where it only releases locks.
Strict 2PL and Rigorous 2PL
- Strict 2PL: Holds all Exclusive ($X$) locks until the transaction terminates (COMMIT or ABORT). Guarantees conflict serializability and prevents cascading aborts.
- Rigorous 2PL: Holds ALL locks (both $S$ and $X$) until COMMIT or ABORT. Guarantees that transactions can be serialized in the order they commit. Most widely implemented in production DBMS engines.
8.3 Deadlock Handling & Timestamp Ordering Protocol
Lock-based protocols introduce the risk of Deadlock, where two or more transactions are in a simultaneous circular wait, each holding a lock the other requires.
Deadlock Prevention: Wait-Die vs Wound-Wait
These schemes assign each transaction an immutable monotonically increasing timestamp $TS(T_i)$ based on when it begins. Older transactions have smaller timestamps ($TS(T_{old}) < TS(T_{young})$):
| Scheme | If Old requests lock held by Young | If Young requests lock held by Old |
|---|---|---|
| Wait-Die (Non-preemptive) | Old is allowed to WAIT | Young DIES (aborts & restarts) |
| Wound-Wait (Preemptive) | Old WOUNDS Young (preempts/aborts Young) | Young is allowed to WAIT |
Timestamp Ordering Protocol & Thomas Write Rule
Under Timestamp Ordering, no locks are held. Each data item $Q$ maintains two timestamps:
W-timestamp(Q): The largest timestamp of any transaction that successfully executedWRITE(Q).R-timestamp(Q): The largest timestamp of any transaction that successfully executedREAD(Q).
Thomas' Write Rule: If transaction $T_i$ attempts WRITE(Q) and $TS(T_i) < W ext{-}timestamp(Q)$, the update is simply obsolete and can be ignored without aborting $T_i$! This allows non-serializable schedules that nonetheless produce correct results.
