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

In this type of question what should be the answer ? when no option match

---

i think as in this non serial schedule , we are not able to make it equivalent to a serial schedule . so either we do T1 completely then T2 . OR T2 completely then T1.

basically either of the 2 serial schedules should be performed.

i feel option c is correct and for d) the intent of the statement is not clear.

---

This question is not mentioned clearly in 2019 GO hardcopy.

---

Yes diagram is not mentioned properly.

---

In this question there is a cycle exist in precedence graph so it clearly not css.
But what about VSS?
For schedule to be view serializable schedule it should
be view equal to some serial schedule.
and the condition for view equal are
1.Initial read must be same
2.Final write must be same
3.Updated read must be same

now let come to initial read first
T1 reading A first
T2 reading B first
as two serial schedule possible T1->T2 or T2->T1
so if T1 execute first then T2 will read different value of B
as in T1 there is one operation Write(B)
and if T2 execute first then T1 will read different value of A
as in T2 there is one operation write(A)

so initial read are not same.
so Given schedule is not view equal to any of serial schedule
so 
Option D
S is not serializable either as T1,T2 or T2,T1

---

@https://gateoverflow.in/user/Abhishek+Rauthan

Even before checking for VSS, if a schedule is not Conflict Serializable, first check if there are any blind writes. If there are no Blind writes, then it is not even View Serializable. This checking is very fast.

---

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.

---

how are you getting A = 0, B = 12?? I am getting A=0, B=20 even in order given in question. If b = 10, then you are doing b+10 in T1, I don't get how you got 12.

---

can anyone provide the precedence graph for this ?

---

@raizal In $T1 \longrightarrow T2$ $A=0$ and $B=20$

In $T2 \longrightarrow T1$ $A=0$ and $B = 22 $

This is what I'm getting if I considered both as 10 initially

---

Just checking conflict serializability & view serializability is not enough to conclude that given schedule is not serializable. Almost all posted answers are following wrong approach. Please read the correct answer -
https://gateoverflow.in/3721/gate-it-2004-question-77?show=484823#a484823

---

We can directly conclude that the given schedule is not serializable as whatever sequence we try out either T1,T2 or T2,T1 we won't be able to do swapping in both ways as there would r-w and w-w conflicts. Thus it's not a serializable schedule.

---

@JAY_BHAGAT 

This schedule is neither view serializable aslo nor conflict serializable. Still it is serializable as $(T1,T2)$ because its effect is same as effect of serial schedule: $(T1, T2)$
Check this answer - https://gateoverflow.in/3721/gate-it-2004-question-77?show=484823#a484823

---

---

MAKE SURE YOU UNDERSTAND THE FOLLOWING CORE RULES BEFORE READING THE DETAILED SOLUTION

• CS vs VS (Blind Writes): Without blind writes, Conflict Serializability equals View Serializability ($\text{CS} = \text{VS}$), but with blind writes, Conflict Serializability is a subset of View Serializability ($\text{CS} \subset \text{VS}$).

• Pure Read/Write Model: When only read/write operations are given (no mathematical operations), View Serializability is equal to General Serializability ($\text{VS} = \text{General}$).

• Computation & Undecidability: When specific mathematical Computation, testing General Serializability is mathematically undecidable,  We have to check if the effect (final database state) of given schedule in question is equal to effect of SOME serial schedule (where transactions execute one after another without interleaving).

• CS Conditions: Conflict Serializability ($\text{CS}$) is a sufficient, but not necessary condition for serializability.

• VS Conditions (Pure Read/Write): Without specific Computations only operations (read/write only), View Serializability ($\text{VS}$) is both necessary and sufficient for general serializability.

• VS Conditions (With Computations): With specific mathematical operations (Computations) given, View Serializability ($\text{VS}$) becomes only sufficient, but not necessary for general serializability.

Now look for this Solution -> https://gateoverflow.in/3721/gate-it-2004-question-77?show=484823#a484823

---

---

This Question is inspired from this DBMS Korth book examples 

Notes about Serializability 

1) A concurrent schedule is considered serializable if, for every possible initial consistent database state, its final effects on the database state are exactly the same as the effects of some serial schedule.

2) To truly determine this general serializability, the analysis must rely on evaluating all specific operations and actual computations performed by the transactions.

3)Analysing  these exact computations determines true general serializability, this type of semantic analysis is hard to implement and computationally expensive in practice.

Some More examples : 

Type 1 : Not CS , Not VS , Not Serializability 

Type 2 : Not CS , Not VS  But Serializability 

 

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

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??

---

View Seriazibility = Serizability (general) : when only read write operation is there , if computation given than it is Serizability (general)

Conflict = View : when there is no blind write present is transtion so we directly solve using Conflict serizable method

Answer 2

$\color{red}\text{Correct option is D but it is not what you think.}$

$\color{red}\text{Just a slight modification in the given schedule}$
$\color{red}\text{will change the answer of this question.}$ 

$\color{red}\text{Debunking a Major Misconception:}$

Majority of aspirants has misconception that serializability is same as view serializability. They think view serializability is necessary and sufficient for serializability. But it is not so. You may potentially loose marks in future GATE Exam if your concepts are not correct. To justify this, I'll give counter example (just a slight variation of this question) at the end.

Since computations are also given along with read and write operations, just checking view serializability is not enough to conclude that given schedule is not serializable. Because every view serializable schedule is serializable but not every serializable schedule is view serializable.

From NPTEL:

It may so happen that given schedule is neither CS nor VS but serializable just because of detailed behaviour of transactions are given. Its just coincidence the wrong answers posted here are getting correct option. Even faulty clock shows correct time twice a day.

General Serializability definition from Ullman:

(Based on above definiton, we'll analyze the GATE question.)

From Ullman:

In above example, given schedule is neither CS nor VS but it is serializable. Its equivalent to serial schedule $(T1,T2)$ and $(T2,T1)$ both. If this example had been given in the question, then the answer would have been option $C$.

---

Now, coming to the given question.
We have to check if the effect (final database state) of given schedule in question is equal to effect of SOME serial schedule (where transactions execute one after another without interleaving)..

Assume that initially $A=x$ and $B=y$. Effect of given schedule -

If we execute above schedule, then final value of $A$ and $B$ will be $x-10$ and $y+0.2x$ respectively.

If there are $n$ transactions in schedule then $n!$ serial schedules are possible. Since there are two transactions involved in given schedule, only $2!(=2)$ serial schedules are possible. Now, Let's check effect of both serial schedule.

Effect of serial schedule $S_1 : (T1, T2)$ -

Effect of serial schedule $S_2 : (T2,T1)$ -

We can see that effect of given schedule is neither equal to effect of $S_1$ nor equal to effect of $S_2$.

So, given schedule is neither serializable as $T1, T2$ nor as $T2, T1$. Option D is correct.

---

Now consider the following schedule $S_{t}$ which is variation of given question, where I replaced $Temp = 0.2*A$ with $Temp = A$ :

Effect of $S_t$ -

Effect of serial schedule $S_{t1} : (T1,T2)$ -

Effect of serial schedule $S_{t2} : (T2, T1)$ -

We can easily see that for every initial database state, effect of $S_t$ is equal to effect of serial schedule $S_{t1} : (T1, T2)$.

So, schedule $S_t$ is serializable only as $T1,T2$. Here, option A is correct, not option D.
But $S_t$ is neither view serializable nor conflict serializable even though $S_t$ is serializable.

---

Note: 

• When computations are given in the Schedule, we have to check for general serializability.
• When computations are not given and only Read and Write operations are given then in that case, Serializability $\equiv$ View Serializability.
• When computations and blind writes are not there, Serializability $\equiv$ View Serializability $\equiv$ Conflict Serializability.

Comments

Learnt something new. Thanks!!

---

Great answer broo!!

---

 

Thanks guru

Answer 3

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 4

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

Answer 5

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

Answer 6

1. Caption