The Gateway to Computer Science Excellence
+1 vote
361 views

Consider the following schedule 

$\text{S : r2(A), w1(B), w1(C), R3(B), r2(B), r1(A), commit_1, r2(C), commit_2, w3(A), commit_3 }$

Consider the following statements : 
S1 : Schedule(S) is conflict serializable schedule. 
S2 : Schedule(S) is allowed by 2PL. 
S3 : Schedule(S) is strict recoverable schedule. 
S4 : Schedule(S) is allowed by strict 2PL. 
How many above statements true about schedule(S) ?

in Databases by Boss (36.5k points)
retagged by | 361 views
0
S1 and S2 are true i know please confirm S3 and S4 only
+2
For S3:

T2 is doing a dirty read for B but it is also committing after the transaction from which it dirty reads. So the schedule is recoverable I think
0
I got S1 and S3 :/
0
can anybody explain me how it's follow  2PL  ??
+3

 

i missed Unlock (A) in T2 after Unlock (C)
please consider that too

0
$S_1, S_2 \rightarrow True \\ S_3, S_4 \rightarrow False$
0

 answer is given 3 without explanation :|

0

@Mk Utkarsh

It's not strict recoverable cuz

Strict schedule says that value written By a transaction cannot read or writtten by other transaction until the transaction is either commit or oborts

here, In this case    R3(B)  is reading the value of W1(B) before the commit of transaction T1

0

S1 true S2 true S3 false S4 true

S1: it is conflict serializeable and schedule is T1->T2-> T3.

S2 : for 2PL the first condition to check is

       if schedule is not serializable then it is not 2PL.

       here T1 locks X(A),X(B),S(C)then after commit releases them.

       T2 locks S(A,B,C) then after commit releases them.

       T3 locks S(B),X(A) then after commit releases them.

 S3:they are asking for strict recoverable. T2 is doing R(B) before commit of T1 which is doing W(B) so it is not strict schedule.

S4: Strict 2PL : 2PL + all X(_) locks must be held until transaction completes(commits). so S4 is also true.

 

0

 i agree

0

 please add complete schedule with locks for S4 as answer i'll accept

0
already written in example.X() is exclusive lock and S() is shared lock.

first T1 will lock and release locks after commit then T2 and then T3.
+1

@Satbir in ur answer. Consider a case when T1 gets exclusive lock at data item B, now see there is read operation on same data item B by T3 and when T3 request for shared lock at B it will denied. Hence it is not strict 2PL.

0
yes but i am executing it as T1 -> T2 -> T3. T1 releases its lock after it commits and then T2 and T3 can apply shared lock on B.
+2
R2 and T3 reading data before T1's commit.
+1

 we can avoid wasting time in discussion if you post the image of your schedule 

0
no ....after T1 commits then it releases all its locks and then T2 applies locks and do its work and after it commits T3 acquires all locks .
0
That's right Utkarsh.
0

 schedule is not serial so that's incorrect

0

@Satbir plz post ur solution.

0

i agree with @Shubhanshu as s4 will be false due to r2(B) will ask for shared lock and b is already locked(xclusive) by T1.

0
Please check in the answer
+1

@Mk Utkarsh

schedule is not serial but it is conflict serializable.

so we can convert  it to T1 -> T2 -> T3 (as we are getting same output in both case) and then apply locks on it.

+2
Operations are happening in CHRONOLOGICAL order at the database.

In your schedule, it is also satisfying $S_3$
0

yes correct. @Shubhanshu

so what am i doing wrong by making the schedule serial and then executing it . since it is conflict serializable to t1->t2->t3 ?

+1
By following the lock points in 2PL you can design SERIAL SCHEDULE equal to the given schedule, which the Concurrency Controller Component $(C^3)$ does to check whether it is equal to some serial schedule or not. But still, the Operations are present in the CHRONOLOGICAL form (remember LOG File).
0

@Magma @Mk Utkarsh @Shubhanshu

Why isn't the schedule recoverable? Though there is dirty read but since the transactions are ultimately getting committed(and that also in the order of the dirty read) so can't we say it is cascadeless and hence recoverable?

Please confirm..

EDIT: I guess i got it.. there is a difference b/w strict recoverable schedule and a recoverable schedule..

0
yes :p
+1
Key word - STRICT.
0
can someone give the proper answer
0
For S2, try to give the locks and release the locks as needed and see if you are being able to form such a schedule where locking of items and releasing of items are taking place in 2 phases or not. If u can form such a schedule and at the same time if u can satisfy the lock requests of all the transactions, then the schedule is in 2PL.

For S4, according to the definition of strict 2PL, see whether the transactions are being able to hold the exclusive locks on data items until they commit. If you can form such a schedule and at the same time if you can satisfy their requests, then the schedule becomes a strict 2PL schedule.
+3

This is the schedule that is possible in 2PL. There is no way by which u can get this schedule to be under strict 2PL since transaction T1 has to unlock its exclusive mode locks on B and C even before it commits.

0
i didn't see any such ques in prev year :(
+2

only regarding 2PL has been asked in GATE before..https://gateoverflow.in/1484/gate1999-2-6

 

0

 i m confused about S3 they saying strict recoverable....i beleive those 2 are different terms

0
The schedule isnt strict recoverable also. Strict recoverable means if a transaction is performing Write operation on some data item, any Read/Write on that same data item can occur only after the transaction which performed the Write commits. But here this isnt the case. So S3 is false.
0
saying strict recoverable is as good as saying strict schedule ..every strict is recoverable !!
0

yes exactly!

0
three types we have

1) recoverable

2) cascading abort

3) strict

and they are saying term strict recoverable which is not valid term according to their definitions i think bcz strict is superset of recoverable if strict then must recoverable

u r saying just definition of strict  above .

they should nt have written that recoverable thing there ... i am just saying that ...
0

Strict recoverable implies a strict schedule.

And the second type of schedule is "Cascadeless schedule" which is a recoverable schedule and has no cascading aborts.

0

@Somoshree Datta 5

Just for confirmation

If Shared lock already taken on item other CAN take SHARED LOCK  on that item but NOT EXCLUSIVE

if Exclusive lock is already taken on item then other CAN'T take SHARED NOT EXCLUSIVE also

0

Yes, right!

0
0
any one explain
0

@Shubhanshu can you please tell what's the final answer for this question, which statements are correct so that we can understand which part we r going wrong if any nd understand from the comments.

because it's not clear what is the exact conclusion of this discussion.

thanks in advance

+2

s1: True: conflict serializable to schedule >> $T_{1}\rightarrow$$T_{2}\rightarrow T_{3}$

S2: True: allowed in basic  2PL.

s3: False

    strict recoverable schedule>> if transaction $T_{i}$ updates the data item A, then any other transaction $T_{j}$ not allowed to R(A) or W(A) until commit or rollback of $T_{i}$.

                        $T_{i}$                   $T_{j}$
                        W(A)                  
                       .....  
              commit or rollback  
                     R(A) or W(A)

 

s4: False>>>  strict 2PL is basic 2PL in which all exclusive locks should be hold until commit or rollback

                    but here R$_{2}$(B) request for shared lock on B and B is already locked(xclusive) by   $T_{1}$.

1 Answer

0 votes
S1 : true

S2 : true

S3 : false

S4: false
by (385 points)
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
50,737 questions
57,321 answers
198,401 comments
105,156 users