in Databases edited by
8,622 views
27 votes
27 votes

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?

  1. $T1 \to T3 \to T2$
  2. $T2 \to T1 \to T3$
  3. $T2 \to T3 \to T1$
  4. $T3 \to T1 \to T2$
in Databases edited by
8.6k views

1 comment

reshown by
in T3 are they over writing x value with y value ?
0
0

4 Answers

44 votes
44 votes
Best answer

Answer is option A.

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

edited by

4 Comments

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

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

 

0
0

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)\\$

0
0
8 votes
8 votes

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

edited

1 comment

how we apply topological ordering ..i draw the graph but after how to know its  serialize or not
0
0
6 votes
6 votes
You can use method of conflict serializability graph or precedence graph Ref: Elmasri Navathe. Then serialisation is T1 T3 T2
0 votes
0 votes
(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.
Answer:

Related questions