GATE IT 2004 | Question: 77

Question

Consider the following schedule $S$ of transactions $T1$ and $T2:$

$${\begin{array}{l|l}
\textbf{T1}&    \textbf{T2} \\\hline
\text{Read(A)} \\
\text{A = A – 10}\\
&   \text{Read(A) }\\  
&  \text{Temp = 0.2*A} \\
& \text{Write(A)} \\
& \text{Read(B)} \\    
\text{Write(A)}\\
 \text{Read(B)}\\
\text{B = B + 10}\\
\text{Write(B)} \\
& \text{B = B + Temp}  \\  
& \text{Write(B)}\\ 
\end{array}}$$

Which of the following is TRUE about the schedule $S$ ?

• A. $S$ is serializable only as $T1, T2$
• B. $S$ is serializable only as $T2, T1$
• C. $S$ is serializable both as $T1, T2$ and $T2, T1$
• D. $S$ is not serializable either as $T1,T2$ or as $T2,T1$

Comments

A Schedule can be Serializable even when it is not View Serializable. So just checking CS and VS is not enough specially when there are computation involving something other than -, +.

---

if intial values of A and B are assumed to be 10 ,

then after running in order T1 → T2 , we have A = 0 , B = 20

running in order T2 → T1 , we have A = 0 , B = 22

running in the order mentioned in question  ,we have A = 0 , B = 12

So the given schedule is not serializable to either .

---

in this question, i think that the given schedule is serializable to T2 -->T1. I have taken inital consistent state as A=a and B=b. Then i have got final database A=a-10 , and final database B = b+10+0.2a in both the executions T2--T1 as well as given schedule.

Answer 1

There is a cycle in the precedence graph - so the given schedule is not Conflict Serializable. 

If a schedule is view serializable but not conflict serializable it MUST have one or more blind writes. Here, there are no blind writes. So, the given schedule is not even view serializable. 

Option D is the Answer. 

 

Comments

Yes, you are right because a cycle exists in the precedence graph.

---

@Arjun sir, I undrstood here that a cycle exists and there is no blind write here thats why it is not serializable ... right sir ?? , but I have not seen any question like this, where T1 reads and T2 writes the same data at the same time. For example here read(B) by T1 and write(B) by T2. So, my question is-  If such scenario is there, then what to consider T1 -> T2 or T2 -> T1 dependecy or both ??  

---

@vijaycs sir Were you able to get the answer ? I have the same doubt.

---

@vijaycs i think answer willl be  D bcz they says we can exeute T1 individually or T2 individully  and single transcation always ensure serialzablity .

---

....

---

@arjun  sir what will be the answer?

---

yes, both transaction cannot happen same time
then there would be unrepeatable read problem.
I think question need some correction

---

ok, here no blind write, so not view serializable too.

if there is blind write, then schedule may or maynot view serializable and if no blind write, then it is not view serializable

---

if there would have been a blind write then how to conclude whether it is  a view serializable or not??

---

I understand that there is a cycle in the precedence graph. But can anyone explain what is the purpose of Write(A) in T2? A is not modified in T2 and it is writing the same data again in DB. It is just there to create a conflict. What if we totally ignore it? Then the schedule will become serializable to T2->T1. This may not be allowed but I need someone's confirmation.

---

@mini panda i also have the same doubt that what is role of write (a) here in t2 if u got it then please explain it .

---

But if we ignore write(A) in t2  then also it is not serializable

---

Prince Sindhiya

Yes right.. I don't know how I got it as serializable at that time :P

---

If we use lock here , then B) will be ans

eg:

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

---

what should be the ans of this qsn??

Answer 2

For a schedule to be serializable check as follows : 

a) check for CSS(sufficient but not necessary) : since cycle in precedence graph. so not CSS.

b) check for VSS (sufficient and necessar): since no blind write it is not VSS.

thus not serializable(equivalent to any serial schedule).

Only serial schedule is possible either as T1->T2 or T2->T1.

Answer 3

Ans is Option D which is saying that each transaction should run individually that is T1 separate and T2 separate

Answer 4

no option correct as there is cycle in precedence graph therfore it is not VSS means not serializable!!

Comments

cycle therefore not CS. and even there is no blind writes therefore not VS