Page History

...

Before continuing further towards the discussion of CC protocol, which provides serializable schedules, let's dive into the serialization theory. Assume we have 3 transactions:

T1 = r1[x] r1[z] w1[x] c1,  T2 = r2[y] r2[z] w2[y] c2,  T3 = w3[x] r3[y] w3[z] c3

Two possible and two schedules:

S1 = w3[x] r3[y] w3[z] r2[y] r2[z] w2[y] r1[x] r1[z] w1[x] c1 c2 c3

S2 = w3[x] r1[x] r3[y] r2[y] w3[z] r2[z] r1[z] w2[y] w1[x] c1 c2 c3

What we can tell about serializability of S2 ? Recall the serializable schedule definition: to be serializable, it must be equivalent to some serial execution order of transactions T1, T2, T3.

...

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 found.

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.

We must also take into account schedules containing aborted transactions. 

...

T1 = w1[x] a1, T2 = r2[x] w2[x] c2

and a schedule

S = w1[x] r2[x] w2[x] c2 a1

Such schedule is unrecoverable, because T2 is committed and can't be undone on T1 abort.

T1 = w1[x] c1, T2 = w2[x] a2

S = w2[x] w1[x] a2 c1

Here w1[x] will be undone by a2, causing lost update on c1.

...