GATE CSE 1999 | Question: 2.6

Question

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}$$

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

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

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

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

Comments

"2pl guarantees serializability but it does not permit all serializable schedule"

---

stmt - 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 serializable then not 2pl.

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

---

 

if schedule CSS and No blind write then that schedule not VSS

---

@Devesh_Kumar Bro what is Basic Ts here and what is the entire circle stand for ??

Also where would be Strict 2PL, Rigorous 2PL and Conservative 2PL

---

to approach this one

Serializability is same as VS if only Read/ Write operation Given

if There is no Blind Write CS=VS

To Check $2PL$ First check if No CS if its true then no point of checking $2PL$ else u've to manually check taking the locks

---

if there is no calculations involve in transactions then serializability check is equivalent with view equivalent. hope it helps

---

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

If conflict serializable schedule then it is 2PL

Answer 1

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)

Comments

@princeit07 If a schedule is in Basic 2PL, then it is Conflict serializable and if it is conflict serializable then it is also view serializable. 

Now if a schedule is not serializable (means its even out of view serializable circle), it can never occur in a scheme using 2PL protocol.

So, Answer: Option D

---

@princeit07 using basic Mathematical logic. 

$p\rightarrow q$ is equivalent to it contrapositive $\neg q \rightarrow \neg p$

If 2PL generates schedule $s$ then it is Conflict Serializable.

and its contrapositive statement would be, If $s$ is not Conflict Serializable then it can’t be generated by 2PL.

---

If css is not stisfying thats why we use 2pl technique but here 2pl conditions are not hold because in shrinking phase lock acquir happens thats why not in 2pl .

If 2pl does not hold then not css

Option d

Answer 2

As we can see the precedence graph is creating a cycle. $\implies$ It is not a conflict serializable schedule

 

Also there is no blind write in the given schedule $\implies$ It is not view serializable (As it is not a conflict serializable schedule. ) $\implies$ It is not serilizable schedule.

 

Also if a schedule is not serializable then it cannot be 2PL $\implies$ It is not 2PL schedule.

$\therefore$ Option $D.$ is correct answer.

Comments

I just want to add that 2PL ensures serializability. So, if the schedule is not serializable, it cannot occur in a scheme using 2PL CC protocol.

---

how does no blind write => non-VSS schedule?

Answer 3

As shown:   T1------>T2            and  T2-------->T1

hence there is a cycle so it is not Conflict Serializable.

For 2PL:  as according to 2PL in the Growing phase we can acquire locks on data items only and in the Shrinking phase we can do unlocking only. Therefore if we do the same as above then in transaction T1 there will be the exclusive lock on data variable A (it can not be unlocked as there is remaining transaction T1) and at the same time if we look at T2, in the T2 transaction it is trying to get a lock on variable A which is not possible.

That’s why it can not occur in the 2PL protocol.

Hence answer is D

Comments

Why should we check conflict serializability,why not view serializability

Answer 4

BEST ANSWER 

Answer 5

First and important thing to notice here serialiable means question asking for general serializibilty but due to NO computation between R/W so general Serializibility is equivalent to View Serializibility 

credit @Deepakpoonia sir @GOClasses

Comments

I dont think thats true . There can be schedules which are serialisable but are not view serialisable .Correct me if I am wrong

---

sorry i initially have mistake that i have to write NO but written IN by mistake while typing , and yes your doubt is correct there are schedules but i am talking about this particular schedule here we dont have computation in between so it collapses

Answer 6

There is a cycle between T1 and T2. So, the schedule is not view-serializable.

If the schedule is not serializable, then it is also not 2PL.

Note : If a schedule is serializable, then it does not guarantee 2PL (same as Pumping Lemma analogy)