Locking-based algorithms for concurrency control can be employed to synchronize the execution of transactions. Explain what is meant by a serializable schedule and show that the following locking-based schedule is not serializable:

Question

S = [wl 1 (y), wl 2 (y), R 1 (y), W 1 (y), R 2 (y), W 2 (y), rl 1 (y), rl 2 (y), wl 2 (z), R 2 (z), W 2 (z), rl 2 (z),
C 2 ,
wl 1 (z), R 1 (z), W 1 (z), rl 1 (z), C 1 ]

where R i (x)/W i (x) indicates a read/write by transaction i on data item x
rl i (x)/wl i (x) indicates a release/write lock by transaction i on item x
C i indicates a commit operation by transaction i.

Answer 1

A schedule S is said to be serializable if all the reads and writes of each transaction can be reordered in such a way that when they are grouped together as in a serial schedule the net effect of executing this reorganized schedule is the same as that of the original schedule S. This reorganized schedule is called the equivalent serial schedule. A serializable schedule will therefore be equivalent to and have the same effect on the database as some serial schedule.

Use a precedence graph to show that a cycle exists in the schedule.