AKU EXAM 2019 DBMS

What is two-phase locking protocol ? Explain its working in detail. How can it guarantee serializability ?

Let us first understand What is transaction ?

A transaction is an executing program that forms a logical unit of Database Processing. A transaction can include one or more database operation like insertion, deletion, modification or retrieval operation.

What is schedule ?

A schedule is a list of actions like reading, writing, aborting or committing which form a set of transactions and the order in which two actions of a transaction T appear in a schedule must be the same as the order in which they appear in T.

As name indicates read operation means it read data item  For Example, Read operation in schedule represented as R(A) means read operation performed on data item A. Similarly, Write operation can be represented by W(B) means write operation performed on item B. Abort operation in schedule is used to cancel performed operation in schedule. Similarly, commit operation is used for saving performed operation permanently in schedule. A schedule that contains either an abort or commit for each transaction whose actions are listed in it is called a complete schedule.

There are basically two types of schedule is allowed in DBMS system. One is serial schedule another one is concurrent schedule.

If the actions of different transactions are not interleaved-that is transactions are executed from start to finish one by one is called serial schedule.

The DBMS interleaves the actions of different transactions to improve performance but not all interleaving should be allowed is called concurrent schedule.. Only those concurrent schedule is allowed in DBMS which is equivalent to some serial schedule. DBMS typically uses a locking protocol to achieve this.

A locking protocol is a set of rules to be followed by each transaction to ensure that , even though actions of several transactions might be interleaved, the net effect is identical to executing all transactions in some serial order.

There are two different locks are as follows :

1) Shared lock(S): It is required for reading a data item.

2) Exclusive lock(X): it is required for writing an data item.

Two phase Locking Protocol

2PL insures the serializability. It other words we can say it does not allow to execute any non serializable schedule. The idea of 2PL protocol is that a transaction cannot request additional locks once it releases any lock.

As name indicates it has one phase called growing phase in which it acquires locks followed by second phase called shrinking phase in which it release locks.

LP: (Lock Point) It is the point between last lock and first unlock.

Equivalent serial schedule is based upon the lock points of transactions in Two Phase Locking Protocol.

Ex: Consider the following schedule S: Check if schedule S is allowed by 2PL or not

In this schedule there are three transaction T1, T2 and T3 runs concurrently. So we apply two phase Locking Protocol on to check is this concurrent schedule is equivalent to any serial schedule or not.

The schedule is allowed by 2PL as follows:

As we know Two Phase Locking Protocol states apply exclusive Lock before Write operation and apply shared lock before any Read Operation.

In above schedule, transaction T1 performed first write operation on data item A simultaneously T3 performed read operation on data item C. So, first apply exclusive lock on data item before write operation by transaction T1. Similarly, apply shared lock on data item C in transaction T3 as below. 

Next operation is read operation on data item A by transaction T2 which is not possible because item A is locked by transaction T1. So, this R(A) operation is possible after unlocking data item A by transaction T1. At the same time Two Phase Locking protocol also states that after unlocking any item by transaction can not any any lock operation and here there is again one more W(B) operation in T1 so before unlocking data item in transaction T1 apply lock on data item B in transaction T1 like below fig 

. There is Lock Point 1 in transaction T1 because this is last locking and first unlocking in transaction in T1. Similarly, in transaction T2 there is read operation on data item A so apply shared lock before read operation on data item A.  then after there is read operation on data item D in transaction T3 so again apply shared lock before it. Next operation is write operation on data item D by transaction T2 so we have to apply exclusive lock on it. But already shared lock is applied in data item D by transaction T2. So it is necessary as per two phase locking protocol to apply shared lock operation on data item A before unlocking data item D in transaction T3. Finally, second lock point LP2 is applied by transaction T3 as this point where last lock and first unlock operation is applied.  Now, we can apply exclusive lock before write operation on data item D in transaction T3. Now there is no operation is left in transaction T2  so unlock first data item A and this is the position of lock point LP3 in transaction T3. These lock point in transaction decides order of serial schedule corresponding to this concurrent schedule in Two Phase Locking Protocol.

Based on Lock point order Equivalent serial schedule of this transaction is as T1 -> T3-> T2