Page History

...

The S1 is obviously serial: it corresponds to execution sequence: T3, T2, T1. It's not that obvious for S2 if it's serializable or not. To prove it me should find a equivalent serializable schedule. We can attempt to swap non-conflicting operation (preseving the order of conflicting) until the equivalent schedule is foundproduced.

w3[x] r1[x] r3[y] r2[y] w3[z] r2[z] r1[z] w2[y] w1[x] → w3[x] r1[x] r3[y] r2[y] w3[z] r2[z] r1[z] w1[x] w2[y] → w3[x] r3[y] r2[y] w3[z] r2[z] r1[x] r1[z] w1[x] w2[y]  → w3[x] r3[y] w3[z] r2[y] r2[z] r1[x] r1[z] w1[x] w2[y]  → w3[x] r3[y] w3[z] r2[y] r2[z] w2[y]  r1[x] r1[z] w1[x] 

So, S2 is serializable and equivalent to T3, T2, T1. Such schedules are called conflic serializable - they can be converted to serial schedule by swapping non-conflicting operations, which have no effect on execution outcome. Every conflict serializable schedule is serializable, but not vice versa.

Consider the transactions:

T1 = r1[x] w1[x] c1, T2 = w2[x] c2

and a schedule: r1[x] w2[x] c2 w1[x] c1

This schedule is serializable, but not conflict serializable.

We must also take into account schedules containing aborted transactions. 

...