search
Log In
22 votes
3.9k views

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
3.9k views
0
in T3 are they over writing x value with y value ?

3 Answers

37 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


edited by
0
Thanks
1
How to apply topological sort on a precedence graph?
0

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

2
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.
0
Please help me identify What's the conflict from T1 to T2?
8 votes

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


edited
0
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
Answer:

Related questions

35 votes
6 answers
1
9.8k views
Which of the following concurrency control protocols ensure both conflict serializability and freedom from deadlock? 2-phase locking Time-stamp ordering I only II only Both I and II Neither I nor II
asked Sep 29, 2014 in Databases jothee 9.8k views
28 votes
7 answers
2
4.1k views
The following functional dependencies hold for relations $R(A, B, C)$ and $S(B, D, E).$ $ B \to A$ $A \to C$ The relation $R$ contains $200$ tuples and the relation $S$ contains $100$ tuples. What is the maximum number of tuples possible in the natural join $R \bowtie S$? $100$ $200$ $300$ $2000$
asked Sep 30, 2014 in Databases jothee 4.1k views
20 votes
2 answers
3
3.1k views
A relational schema for a train reservation database is given below. passenger(pid, pname, age) reservation(pid, class, tid) ... 'AC' AND EXISTS (SELECT * FROM Passenger WHERE age>65 AND Passenger.pid=Reservation.pid) $1, 0$ $1, 2$ $1, 3$ $1, 5$
asked Sep 29, 2014 in Databases jothee 3.1k views
39 votes
8 answers
4
8.7k views
Consider a $B^+$-tree in which the maximum number of keys in a node is $5$. What is the minimum number of keys in any non-root node? $1$ $2$ $3$ $4$
asked Sep 29, 2014 in Databases jothee 8.7k views
...