The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+24 votes

For the schedule given below, which of the following is correct:

$$\begin{array}{ll} \text{1} & \text{Read A} & \text{} \\  \text{2} & \text{} & \text{Read B} \\   \text{3} & \text{Write A} & \text{} \\  \text{4} & \text{} & \text{Read A} \\ \text{5} & \text{} & \text{Write A} \\ \text{6} & \text{} & \text{Write B} \\ \text{7} & \text{Read B} & \text{} \\ \text{8} & \text{Write B} & \text{} \\\end{array}$$

  1. This schedule is serializable and can occur in a scheme using 2PL protocol

  2. This schedule is serializable but cannot occur in a scheme using 2PL protocol

  3. This schedule is not serializable but can occur in a scheme using 2PL protocol

  4. This schedule is not serializable and cannot occur in a scheme using 2PL protocol

asked in Databases by Veteran (59.9k points)
edited by | 3.3k views
quating from namathe " 2pl guarantees serializability but it does not permit all serializable schedule"

3 Answers

+39 votes
Best answer

2PL implies Conflict Serializable Schedule   ( if p then q)

Precedence graph of this given schedule is cyclic hence, this schedule is not Conflict Serializable and hence not allowed by 2PL.

This schedule is not even (view) serializable because

  1. if   $T_1\to T_2$   we will lose Last Updated by $T_1$ on item $B$
  2. if   $T_2\to T_1$   we will lose initial value of $A$ read by $T_1$

Hence, (D) is correct choice! 

We can also see why 2PL is not allowing this schedule.

In 2PL scheme, once a transaction releases a lock it cannot acquire any more locks. Further only one transaction can acquire an Exclusive lock $(X)$ on an object while multiple transactions can acquire a Shared Lock $(S).$

$$\begin{array}{l|l|ll} \text{1} &\overset{S(A)}{\text{Read A}} & \text{}\\
\text{2} & \text{} & \overset{S(B)}{\text{Read B}} \\
\text{3} & \overset{S(A)}{\text{Write A}} & \text{}\\
 &\overset{\boxed{\text{RELEASE(A) cannot be performed}\\\text{here as } T_1 \text{ still needs to}\\\text{request lock on $B$}}}\\\\
\text{4} &&\overset{S(A) }{ \text{Read A}}\boxed{\color{red}{\text{FAILED}}} \\  

$\text{Hence, not allowed in  2PL}$

answered by Boss (17.3k points)
edited by
Who says lock's are to be put in above order to be in 2PL? they just need to follow growing and shrinking phase.

How can we say that a schedule in not in 2PL on the basis of locks?

In the above schedule, there is deadlock but deadlock is possible in 2PL or it is like - Read(A) of transaction 2 cannot execute in given order that's why given schedule is not allowed by 2PL?

For those who didn't get why if not serialzable then not 2pl.?

we must know that if schedule is 2pl(P) then it is  serialzable(Q) too

So,P->Q which is equivalent to its contrapositive parts i.e ~Q->~P

which states that if not serialzable then not 2pl.

In Schedule given we can easily prove that it is not serialzable and hence not occur in 2pl.



By finding that the given schedule is not conflict serializable. Can we directly say that it can not be in 2PL?? (since 2PL ensures serializability)
In Gateforum's solutions, they have shamelessly proved why A should be the answer.
we cannot put exclusive lock if it has already shared on it
+21 votes

If we draw the precedence graph we get a loop,and hence the schedule is not conflict serializable.

There is no blind write too so ,there is no chance that view serializability can occur.

Now 2pl ensures CS.

Since possiblity of CS is ruled out at the onset,so schedule cannot occur in 2PL.

Ans d)

answered by Active (3.6k points)
What it means that it cannot occour in a scheme using 2PL protocol?? Plzzz explain.
If a schedule occur in 2PL protocol does it mean that...both the transaction should be completed.?

Because here only first transaction can be completed..second will be blocked at READ A.....
If a schedule occurs in 2PL successfully, it is conflict serializable I think.
For a schedule to be in 2PL, there should be growth and shrinking phase. Cann't I use this fact to say it is not possible using 2PL.?
growth and shrinking phase of ""             ""?
where are locks here?
That's what i want to say that there is no locks. So can i say directly it is not using 2-phase locking.

if there is a lock then only we can talk about that concept else have to go with other methods to check...


we have to put locks ourselves and then check if 2PL is possible or not.

Suppose if I get some new question regarding if schedule is 2PL or not? then do i have to put locks myself or analyse schedule on the basis of already present lock?
@thor see my updated solution
–1 vote
Option D
answered by (427 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,434 questions
53,630 answers
70,899 users