GATE CSE 2010 | Question: 42

Question

Consider the following schedule for transactions $T1, T2$ and $T3:$

$$\begin{array}{|c|c|c|}\hline \textbf{T1} & \textbf{T2} & \textbf{T3} \\\hline  \text{Read(X)} & \text{} & \text{} \\\hline   \text{} & \text{Read(Y)} & \text{} \\\hline  \text{} & \text{} & \text{Read(Y)} \\\hline \text{} & \text{Write(Y)} & \text{} \\\hline  \text{Write(X)} & \text{} & \text{} \\\hline  \text{} & \text{} & \text{Write(X)} \\\hline  \text{} & \text{Read(X)} & \text{} \\\hline \text{} & \text{Write(X)} & \text{} \\\hline\end{array}$$
Which one of the schedules below is the correct serialization of the above?

• A. $T1 \to T3 \to T2$
• B. $T2 \to T1 \to T3$
• C. $T2 \to T3 \to T1$
• D. $T3 \to T1 \to T2$

Comments

in T3 are they over writing x value with y value ?

---

We have 3 Notions of serializablity based on ease of implementation.

since we are not given computations therefore we can’t check for general serializability.

Conflict serializability and View serializability only focuses on read and write operation.

The view serializability is strongest serializability we can check here. so check based on it.

In this question the schedule is both Conflict serializable and View Serializable.

Answer 1

Answer is option A.

create precedence graph and apply Topological sort on it to obtain 
$T1 \rightarrow T3 \rightarrow T2$

Comments

Please help me identify What's the conflict from T1 to T2?

---

@Ayush Upadhyaya 

check for view serializability here.Final write of X is made by T2, so in equivalent serial order T2 should come last.

Sir then, Initial Read on X and Y is done by T1 and T2 respectively. But if we look at the answer it says initial read on X and Y is done by T1 and T3 respectively. How can it be view serializable?

 

---

amarVashishth

why there is an edge from T1 to T2?

In dependency graph each edge represents a conflicting operation and We should only consider latest write for conflicting operations.

So $\\ W_{3}(X) -R_{2}(X) \: and \: W_{3}(X)-W_{2}(X)\\$ should only be considered not $\\ W_{1}(X) -R_{2}(X) \: and \: W_{1}(X)-W_{2}(X)\\$

Answer 2

The solution is described here.
            
hence option A is True.

Comments

how we apply topological ordering ..i draw the graph but after how to know its  serialize or not

Answer 3

You can use method of conflict serializability graph or precedence graph Ref: Elmasri Navathe. Then serialisation is T1 T3 T2

Answer 4

(A) T1→T3→T2

T1 can complete before T2 and T3 as there is no conflict between Write(X) of T1 and the operations in T2 and T3 which occur before Write(X) of T1 in the above diagram.
T3 should can complete before T2 as the Read(Y) of T3 doesn’t conflict with Read(Y) of T2. Similarly, Write(X) of T3 doesn’t conflict with Read(Y) and Write(Y) operations of T2.