Question

Show that the multi-version read consistency algorithm ensures serializability. That is, read-only transactions use the multi-version technique whereas read-write transactions use strict two phase locking.

Answer 1

Given in the data that a multi-version database, where each data item is a sequence of its versions. The number of versions of a data item may be limited or not.

Suppose we have n transactions T1, T2, ..., Tn such that they all obey the basic

two-phase locking rule (i.e. no transaction has an unlock operation followed by a lock

operation). Suppose that a non-(conflict)-serializable schedule S for T1, T2, ..., Tn

does occur; then, according to Section 17.5.2, the precedence (serialization) graph for

S must have a cycle. Hence, there must be some sequence within the schedule of the form:

S: ...; [o1(X); ...; o2(X);] ...; [ o2(Y); ...; o3(Y);] ... ; [on(Z); ...; o1(Z);]...

where each pair of operations between square brackets [o,o] are conflicting (either [w,

w], or [w, r], or [r,w]) in order to create an arc in the serialization graph. This

implies that in transaction T1, a sequence of the following form occurs:

T1: ...; o1(X); ... ; o1(Z); ...

Furthermore, T1 has to unlock item X (so T2 can lock it before applying o2(X) to follow

the rules of locking) and has to lock item Z (before applying o1(Z), but this must occur

after Tn has unlocked it). Hence, a sequence in T1 of the following form occurs:

T1: ...; o1(X); ...; unlock(X); ... ; lock(Z); ...; o1(Z); ...

This implies that T1 does not obey the two-phase locking protocol (since lock(Z) follows

unlock(X)), contradicting our assumption that all transactions in S follow the two-phase

locking protocol.

Suppose two-phase locking does not ensure serializability:

Then there exists a set of transactions T0, T1 ... Tn−1 which obey 2PL and which produce a nonserializable schedule. A non-serializable schedule implies a cycle in the precedence graph, and we shall show that 2PL cannot produce such cycles.

Without loss of generality, assume the following cycle exists in the precedence graph: T0 → T1 → T2 → ... → Tn−1 → T0. Let αi be the time at which Ti obtains its last lock (i.e. Ti’s lock point).

Then for all transactions such that Ti → Tj , αi < αj . Then for the cycle we have α0 < α1 < α2 < ... < αn−1 < α0 Since α0 < α0 is a contradiction, no such cycle can exist. Hence 2PL cannot produce non-serializable schedules.

Because of the property that for all transactions such that Ti → Tj , αi < αj , the lock point ordering of the transactions is also a topological sort ordering of the precedence graph. Thus transactions can be serialized according to their lock points