Proof that Two Phase Locking (2PL) can guarantee conflict serializability

Proof that 2PL is sufficient condition for conflict-serializability

Theorem:

Let T₁, T₂, ... T_n be n transactions that obey the 2PL rule:
Let S_n = a schedule of the (read, write, lock and unlock) operations found in T₁, T₂, ... T_n (that obey the locking semantics !!!)
Then:

Proof: by induction

The base case: n = 1

T₁ is 1 transaction that obey the 2PL rule
S₁ = a schedule of the (read, write, lock and unlock) operations found in T₁
Then:

The induction case:

Induction asumption:

Every schedule S_n−1 of the (read, write, lock and unlock) operations found in n−1 transactions T₁, T₂, ... T_n−1 (that obey the locking semantics !!!) is conflict-serializable

Let S_n = a schedule of the (read, write, lock and unlock) operations found in n transactions T₁, T₂, ... T_n (that obey the locking semantics !!!)

Let u_i(•) be the first unlock operation found in schedule S_n:

Claim:

We can move all the operations r_i(•) and w_i(•) of the transaction T_i forward in schedule S_n without passing any conflicting operation by another transaction
Graphically:

In other words:

Every operation that preceeds an operation X of transaction T_i do not conflict the operation X

Proof of the claim:

Consider an aribitrary operation by transaction T_i: e.g., w_i(Y)
Consider an arbitrary conflicting operation of a transaction T_j: e.g., w_j(Y) that preceeds w_i(Y):
We will prove that this ordering of operations is not possible
I.e.:
In order for this ordering to be legal (= obeying the 2-phase locking rules), we must have the following lock/unlock sequence on the DB element Y:

Since transaction T_i is 2 Phased locking, the first unlock operation u_i(•) must follow every lock operations

In particular, the first unlock operation u_i(X) of transaction T_i must follow ℓ_i(Y):

That means, in schedule S_n:

The transaction j performed an unlock operation before the first unlock operation u_i(•) in the schedule S_n:
Conclussion:

This is a contradiction of the fact that u_i(•) is first unlock operation in the schedule S_n !!

So this claim is true:

Every operation that preceeds an operation X of transaction T_i do not conflict the operation X

Therefore:

We can move all the operations r_i(•) and w_i(•) by transaction T_i forward in schedule S_n without passing any conflicting operation by other transactions:

After moving all operations of transaction T_i forward, we obtain the following schedule S'_n that is conflict-equivalent to the original schedule S_n:

Schedule S'_n consists of:

All operations by transaction T_i (= the first transaction that performs an unlock operation) is at the front
Followed by a (sub-)schedule S''_n−1 for (n−1) (2-phased-locking) transactions

By the induction asumption that says:

Every schedule S_n−1 of n−1 transactions T₁, T₂, ... T_n−1 that obey the 2-phased locking semantics is conflict-serializable

We conclude that the schedule S''_n−1 (of (n−1) transactions) is conflict-serializable:

In other words:

The schedule S'_n is conflict-equivalent to a schedule consisting of:
I.e.: schedule S'_n is conflict-serializable

Since S_n is conflict-equivalent to S'_n:

The schedule S_n is conflict-serializable:

Q.E.D.