in Databases edited by
1,797 views
3 votes
3 votes
Consider the following schedules involving two transactions.

$S_1 : R_1(x), W_2(y),R_2(x),W_1(y), \ commit_1, \ commit_2$

$S_2 : R_1(x), R_2(y),W_1(z), \ commit_1,R_3(y), R_3(z), W_2(y), W_3(x), commit_2, commit_3$

Which of the following statements is true?

A) Both S1 and S2 are allowed under 2PL
B) only S1 is allowed under 2PL
C) only S2 is allowed under 2PL
D)  neither S1 nor S2 is allowed under 2PL
in Databases edited by
1.8k views

73 Comments

Is it A?
1
1
A is correct.
1
1
@minipanda here we will consider only serializability for the transactions to satisfy 2PL as we donot have any growing or shrinking phase or there is any other approach.?
2
2

arvin  I do like : putting locks on data items and releasing them such that all the operations of both transactions can take place as it is (in the order given). If we can do so then it is allowed under 2pl.

For eg take the 1st schedule :

T1 T2
S(x)  
R(x)  
  X(y)
  W(y)
  S(x)
  R(x)
  U(x) U(y)
X(y)  
W(y)  
U(y) U(x)  
c1  
  c2

Here all locks can be given and taken back such that all operations are done in the same order given.

Take this example : S: R1(A) W2(A) R1(A)

We check whether this is allowed under 2pl or not.

T1 T2
S(A)  
R(A)  
  W(A) -> This operation cannot be performed because we can't acquire lock on it as T1 has S lock on A. If T1 releases S then it's next operation cannot be performed which again requires S because once released cannot be acquired in the 2pl protocol.
R(A)  
U(A)  
  At this point W(A) can be performed but the order is already not maintained. So schedule is not allowed under 2PL.

 

6
6
@minipanda : thanks a lot :p
2
2
@minipanda : so it means we can acquire a lock only once for any variable in a transactiom. and unless it doesnot writes we cant remove that lock.
1
1

A transaction say T1 can acquire a lock on any data item if it is already not locked by some other transaction (only S-S lock allowed). And if T1 wants to release it to hand it over to another transaction T2, then from that point of time T1 can't acquire lock on any data item. This is because it has already entered into the shrinking phase and here it can't acquire any lock again.If it already has put some locks on other data items then it may hold them or release them. But nothing can be acquired.

2
2
oou thanks again :p
0
0
@MiNiPanda, Can you please confirm that second schedule is allowed in 2PL because of lock conversion? Or any other reason
0
0
edited by

According to me S2 is also allowed under 2PL.

T1 T2 T3
S(X)    
R(X)    
  S(Y)  
  R(Y)  
X(Z)    
W(Z)    
U(Z),U(X)    
COMMIT    
    S(Y)
    R(Y)
    X(Z) , X(X)
    R(Z)
    U(Y)
  X(Y)  
  W(Y)  
    W(X)
    U(X),U(Z)
  U(Y)  
  COMMIT COMMIT

 

Shubhgupta  If you find something wrong then let me know..

 

2
2

@MiNiPanda,but last last transaction of t3 is W(X)? I did like -

T1 T2 T3
S(X)    
R(X)    
  S(Y)  
  R(Y)  
X(Z)    
W(Z)    
U(Z),U(X)    
COMMIT    
    S(Y)
    R(Y)
    S(Z)
    R(Z)
  X(Y)  
  W(Y)  
    X(X)
    W(X)
    U(X)U(Z)
  U(Y)  
 
1
1

Shubhgupta Yes i did a mistake.. will edit it.

But in your table T3 is acquiring S-lock on Y and after that without releasing it T2 is acquiring X-lock on Y. That is not possible.

0
0
I have read it somewhere in 2PL with the help of lock conversion a shared lock can be promoted to exclusive lock in growing phase on same data item. And one more thing in 2PL can we acquire all lock for one transaction in predefined manner without knowing future need?
0
0

Shubhgupta Yes lock upgradation is possible only when that lock is not being held by some other transaction. It was fine till the time when T2 and T3 had S-S lock on Y.

I am not exactly sure whether a transaction without knowing it's future need can lock all the variables..but in conservative 2pl, a transaction locks all data items that it needs in executing itself (I don't know how the transaction gets to know what it will need in future :/ ) 

3
3
thanks for the help [email protected]:)
this question arise because in your example you are acquiring exclusive lock on data item on X while reading z value. So how transaction will decide that in future i am having a need to do W(X) so i need acquire lock on that point only. Sounds like weird question.. Sorry.
0
0

No it's a good question actually.. But since in case of conservative 2pl a transaction acquires lock on all data items it will need in future i thought there is some way to determine the data items that it will work on.

syncronizing What is the answer given?

0
0
No Solution was given to this question.
0
0
moved by
D is the correct answer ??
0
0
No answer is given.Please explain.
0
0
First of all tell me that option D is Right or wrong ??
then I will  explain you
I am also don,t know the correct answer that's Y im asking you
0
0
i closed the question.... just read the discussion
0
0
@Arjun Sir, what will be the answer to this question? I am getting neither S1 nor S2 is allowed under 2PL. How to solve such questions?
0
0
this is the 999th time this question is posted :p
0
0
@Somoshree Datta 5, Can you post the solution what they provided? just want to confirm.
0
0
@Mk Utkarsh Ya I know. .But I am not being able to settle down at which one is the correct answer and what are the conditions that are to be checked..could you please give the link that has the right answer with right explanation to this question ??
0
0
@Shubhgupta there was no solution provided for this question.
0
0

Somoshree Datta 5 ok i'm reopening this till someone adds and selects the answer on either your question or that question.

0
0
@Somoshree

can u plz provide the solution they given

I think it is a wrong question of made easy
0
0

@MiNiPanda It is always not possible for a transaction to declare its read set and write set before hand as is the requirement for conservative 2PL to be able to work correctly. So we can't assume that a transaction will always lock the data items that it will need in future.

https://en.wikipedia.org/wiki/Conservative_two-phase_locking

1
1

@Srestha maam No solution was given for this question.But u can surely view this discussion once: https://gateoverflow.in/235026/test-series?show=235026

Can you please tell me how to solve such questions? I am not being able to get arrive at the correct answer..

1
1

Thanks Somoshree Datta 5 for this clarification..

What should be the answer according to you ?

0
0

@MiniPanda

it is surely not strict or conservative 2PL

but 1st one can be rigorous 2PL

why u written this line

If T1 releases S then it's next operation cannot be performed which again requires S because once released cannot be acquired in the 2pl protocol.

Can u elaborate?

2ndly in 2nd transaction

u releases exclusive lock U(Y) in middle

which locking protocol it can be?

 

0
0
ok chking there
0
0
@MiNiPanda I think that that S1 should be allowed under 2PL by S2 cant be allowed since T3 already holds a shared lock on data item Y, due to which transaction T2 cannot acquire an exclusive lock on Y at the same time. Moreover, T3 cant release the shared lock on Y since that would indicate the beginning of shrinking phase whereby T3 cant acquire the next lock on data item X in order to write it. Shouldn't this be the answer?
0
0
edited by

srestha

If you see this schedule S: R1(A) W2(A) R1(A)

T2 needs to acquire lock over A while T1 has already put S lock on A. Now if we want T2 to be successful in it's write operation then T1 has to release S lock on A. If it does so then T2 after completing write operation may release it's lock but now T1 can't acquire lock on A again because it has already entered the shrinking phase of 2pl protocol. So T1 can complete it's read op.

For your next question, I didn't get it..which one are you referring to?

0
0

Only S2 is allowed under 2PL. ??

what's is given ???

0
0
But how did you get S2

I got "only S1 is allowed", S2 is not allowed under 2PL
0
0
how you get S1 ??
0
0

See https://gateoverflow.in/235026/test-series?show=235026;

In this first table of minipanda. it is correct.

but minipandas 2nd table is not correct i think

0
0

See Only S2 is allowed under 2PL ...S1 is not possible

see I'm not very good in words to explain

if tomorow Somoshree Datta 5  says that yes (b) is right then I try hard to explain  you clearly Ok ???

 

0
0
they dont have any answer for this question.

just tell me where in that table, any mistake is there ?
0
0
edited by
W2(Y) Locked the data Y is in exclusive lock , so someone cannot lock it under exclusive mode

here you see W1(y)  try to lock the data Y in exclusive lock but Never be granted because

W2(Y) held the lock until transactions commits

basically it's a example of Srict 2PL
0
0
I think the question is also somewhat wrong ...they use the Commit so that I guess that they are try to implement Strict 2Phase locking Protocol
0
0
"here you see W1(y)  lock the data Y in exclusive lock".

ya thats true, but we are unlocking exclusive lock on Y in T2 before we are applying exclusive lock on Y in T1.
0
0

read my comment again..I just edit something

ya thats true, but we are unlocking exclusive lock on Y in T2 before we are applying exclusive lock on Y in T1.

So why they are using commits in the transaction ,

In this question they are trying to say that All Exclusive mode locks taken by a transaction must be hold until transaction commits

 

0
0
It holds Strict 2PL  and we know every strict 2PL is also a 2PL

therefore wrt me b is the options
0
0

In this question they are trying to say that All Exclusive mode locks taken by a transaction must be hold until transaction commits

this codition is to be met in Strict 2PL, not In Basic 2PL.

in question they are asking only Basic 2PL.

0
0
In basic 2PL commits not used
0
0
is it ?

but in Basic 2PL condition they didnt mention anything about commit as they did it in Strict 2PL.

they just mentioned about Growing and Shrinking phase.

so we have to check conditions of growing and shrinking phases only irrelevant of Commit operations.

anyway lets see what others have to say.
0
0

daksirp  that's what I'm saying

0
0
release means unlock, right?

If after writing T2 again release then why cannot T1 again acquire this lock?
0
0
@Magma

why r u thinking it is strict 2PL, it can be regorious 2PL too
0
0
edited by

srestha  mam check  that  S2  is also  hold  rigorous  2PL property

 

0
0

According to the two-phase locking protocol, a transaction handles its locks in two distinct, consecutive phases during the transaction's execution:

  1. Expanding phase (aka Growing phase): locks are acquired and no locks are released (the number of locks can only increase).
  2. Shrinking phase (aka Contracting phase): locks are released and no locks are acquired.

Somoshree Datta 5 

S2 cant be allowed since T3 already holds a shared lock on data item Y, due to which transaction T2 cannot acquire an exclusive lock on Y at the same time. Moreover, T3 cant release the shared lock on Y since that would indicate the beginning of shrinking phase 

$T_3$ can release shared lock before $T_2$ acquiring Exclusive lock on Y. Even after this some operations are done on some other data items this is valid. The only thing which is restricted is that you cannot lock some other data item after unlocking.

If you are finding this understanding from any standard resource that in shrinking phase no operation can be done in between  2 locks are released then please share with us too

0
0
@Mk Utkarsh my statement meant that if T3 releases the shared lock on Y for T2 to acquire an exclusive lock on it, then T3 cant acquire an exclusive lock on X which it needs later to perform the final write on X since T3 has already entered its shrinking phase. Isn't this true??
0
0
@Magma, commit operation is irrelevant here I guess since it is never said in the question that exclusive mode locks or shared mode locks are held till the transaction commits. Moreover while solving such questions we try putting locks on data items and releasing them such that all the operations of both transactions can take place as it is (in the order given). So if we unlock exclusive mode lock on Y in transaction T2, then T1 can easily acquire the exclusive mode lock on Y and complete its operations. I don't think that we can make any assumptions regarding the fact that since commit is given so locks must be held till commit operation..

Moreover if we assume also that locks are held till commit operation, then the given schedule isnt possible under strict PL since transaction T1 will not be granted the lock on item Y and hence this schedule doesnt qualify to be under strict PL.
0
0
after $T_3$ releases the shared lock on Y, $T_3$ is in shrinking mode and is not acquiring any lock and already locked (X) in growing phase.
0
0
@Mk Utkarsh How is it guaranteed that T3 will know that it would require X later and hence it would lock X in the growing phase? It may not be possible for a transaction to declare its read set and write set before hand. So how can you guarantee that T3 will declare its requirement in the growing phase only?
0
0

In databases and transaction processing, two-phase locking (2PL) is a concurrency control method that guarantees serializability. It is also the name of the resulting set of database transaction schedules (histories). The protocol utilizes locks, applied by a transaction to data, which may block (interpreted as signals to stop) other transactions from accessing the same data during the transaction's life.

By the 2PL protocol, locks are applied and removed in two phases:

  1. Expanding phase: locks are acquired and no locks are released.
  2. Shrinking phase: locks are released and no locks are acquired.

This is the exact definition, checking the serial schedule given by MiNiPanda everything is satisfied i have any reason to disagree that schedule is not in 2PL. NO. 

Do i know the algorithm that how algorithm works and how many data items in future its checking. No

Is it required? No because definition is itself satisfied. Based on definitions algorithm will work how to grow and how to shrink. If any standard resource says that my understanding is wrong. I'll change my answer, but i still think its A.

0
0
@minipanda second one should not be under 2pl see in T3 you have aquired S(y)

Now before releasing shared  lock on y you can't obtain the ex lock on  (Y)in T2 and if  you have released the lock on Y then T3 is in shrinking phase and now it can't obtain Ex-(X)lock
0
0

Prince that's why Ex-(X) is acquired before releasing (Y)

0
0
@Mk Utkarsh - ya, if this is the case, why did they mention separate protocols for Conservative 2PL.

"All locks must be acquired on data items before starting the transaction".  - C2PL - Growing Phase

they could have done it in Basic 2PL only...

im totally confused !!
0
0

Conservative 2PL has its own limitations out of which one of the limitations are transactions not being able to declare its read set and write set before hand always. Hence conservative 2PL is not used very frequently due to this. If the question would have asked about whether the schedules are allowed under conservative 2PL, then S2 would have been possible because there would have been a way by which transactions could acquire and release locks without violating the definition of conservative 2PL. But here question is asked about basic 2PL and not conservative 2PL.

0
0
ya, this is what im saying.
0
0

Somoshree Datta 5  what's the answer given ???

0
0
@Magma answer isnt given for this question. No solution is provided.
0
0
@Somoshree 1st one cannot be strict 2PL
0
0
@Srestha ma'am yes the first schedule can't be strict 2PL..but my question is can the second one be allowed under 2PL?
0
0
both are allowed under 2PL, I dont know why i didnt notice at that time :)
0
0
2ND ONE IS NOT 2PL ACCORDING TO ME ALSO
0
0
whats ur reason ?
0
0
once we start unlocking  we are not going to lock any variable again
0
0
but where are we doing this ? did u saw minipandas comment ?
0
0

4 Answers

2 votes
2 votes

Concluding the above comments:

S1 is 2PL which can be seen easily in Fig.1.

Fig.1

 

 

The main problem is in the step that I have marked in the Fig.2 for schedule S2, which is that whether we can apply lock on X where it is applied in transaction 3. According to me, I have seen no such restriction, therefore S2 should be 2PL. If anyone knows anything about this, please do share in the comments.

Fig.2

 

0 votes
0 votes
D will be the answer because S2 will obtain all the locks in the growing phase and S1 can't do anything till S2 releases locks but we can see an overlap so both are not allowed for 2 phase locking protocol.
by
0 votes
0 votes

For S1                                         

T1 T2
       S(x)  
      Read(x)  
           X(y)  
        Write(y)
          S(x)
        Read(x)
        U(x)
       U(y)
      X(y)  
     U(y)  
    U(y)  
    commit  
       Commit

                                                    For S2

T1 T2 T3
  S(x)    
  Read(x)    
   S(y) , **  
    Read(y)  
  X(z)    
  Write(z)    
  commit    
  U(z)    
  U(x)    
     S(y)
     Read(y)
      S(z)
      Read(z)
      X(x)
      U(y)
       #  
     Write(y)  
      Write(x)
       U(x)
       U(z)
       commit

Here S1 is under 2PL.

For S2 there is two possibility where it violates the 2PL property.

First possibility is 

 # : Here in transaction T2 of S2, to write on Y we have to apply exclusive lock on Y but we can not do that as we have already applied  shared lock on Y during initial read on Y. So we can not apply exclusive lock.

Second possibility is

** : Here in transaction T2 of S2, we can apply exclusive lock on Y to read and write. But after applying this lock we can not apply lock on Y in transaction T3 to read Y.

Due to above condition S2 is not under 2PL.

So answer is option (C) Only S1 is allowed under 2PL.

0 votes
0 votes

S1: It satisfies 2PL

T1 T2
SL(X) SL(X)
R(X) XL(Y)
   
  W(Y)
  U(Y)
XL(Y) R(X)
  U(X)
W(Y)  
U(X)  
U(Y)