The Gateway to Computer Science Excellence
+20 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 by Veteran (105k points)
edited by | 3k views
in T3 are they over writing x value with y value ?

3 Answers

+35 votes
Best answer

Answer is option A.

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

precedence graph

by Boss (30.8k points)
edited by
How to apply topological sort on a precedence graph?

@amarVashishth There should be $2$ edges from $T_3 \text{ to } T_2$, one for $\text{RW(Y)}$ and the other for $\text{WR(X)}$. Isn't it?

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

2 options eliminated this way.

Now, Write (X) of T3 is read by T2, so T3 should precede T2.So, Option (A) suitable.
Please help me identify What's the conflict from T1 to T2?
+8 votes

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

by Active (3.6k points)
how we apply topological ordering ..i draw the graph but after how to know its  serialize or not
+6 votes
You can use method of conflict serializability graph or precedence graph Ref: Elmasri Navathe. Then serialisation is T1 T3 T2
by Boss (11k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
104,909 users