Schedules and Serializability

When is interleaving safe?

A schedule is an ordering of the operations (reads, writes, commits) of several concurrent transactions. A serial schedule runs one transaction completely after another, which is always correct but slow. A schedule is serializable if its effect equals that of some serial schedule. Conflict serializability is the practical test: two operations conflict if they belong to different transactions, access the same data item and at least one is a write (read-write, write-read, write-write). Swapping adjacent non-conflicting operations does not change the outcome. Build a precedence graph: one node per transaction and an edge Ti → Tj whenever an operation of Ti conflicts with and comes before an operation of Tj. The schedule is conflict serializable if and only if the graph has no cycle, and a topological order of the graph gives an equivalent serial order. Schedules should also be recoverable (a transaction commits only after transactions it read from have committed) and ideally cascadeless (transactions read only committed data).

A precedence graph worked by hand

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

operations in order:    T1: R(A)   T2: W(A)   T2: R(B)   T1: W(B)

conflicts:
  R1(A) before W2(A)   same item A, one write  -> edge T1 -> T2
  R2(B) before W1(B)   same item B, one write  -> edge T2 -> T1

precedence graph:  T1 -> T2 -> T1   (cycle)
=> S is NOT conflict serializable

change S to: R1(A) W1(B) W2(A) R2(B)
  edges: T1 -> T2 only -> acyclic -> equivalent to serial order T1, T2

Sharing a whiteboard

Two people can read the same whiteboard in any order. Trouble starts when one writes while the other reads or writes the same spot; the order of those clashes decides whether the result matches doing the work one person at a time.

त्वरित जाँच: When is a schedule conflict serializable?

• When transactions never read data
• When it has exactly two transactions
• When all operations are writes
• When its precedence graph contains no cycle