Serializability and Concurrency Control

A schedule is serializable if its result is equivalent to some serial schedule.

Conflict Serializability

Two operations conflict if they belong to different transactions, access the same item, and at least one is a write (R-W, W-R, W-W).

Test: build a precedence graph: draw an edge Ti → Tj for each conflicting pair where Ti's operation comes first. The schedule is conflict serializable if and only if the graph has no cycle.

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

R1(A) … W2(A)  ⇒ T1 → T2
R2(B) … W1(B)  ⇒ T2 → T1
Cycle T1 → T2 → T1  ⇒  NOT conflict serializable

Lock-Based Protocols

Two-Phase Locking (2PL)

• Growing phase: a transaction may acquire locks but not release any.
• Shrinking phase: it may release locks but not acquire any.
• 2PL guarantees conflict serializability but not freedom from deadlock.
• Strict 2PL holds exclusive locks until commit, which avoids cascading rollbacks.

Timestamp Ordering

Each transaction gets a timestamp TS(T). Conflicting operations must execute in timestamp order; otherwise the younger transaction is rolled back. Thomas' write rule ignores obsolete writes instead of rolling back.