edited by
23,408 views
70 votes
70 votes

Consider the following transactions with data items $P$ and $Q$ initialized to zero:
$${\begin{array}{|c|l|r|c|}\hline
   \textbf{$T_1$}&    \text{read (P);}\\ & \text{read (Q);} \\ & \text{if P = 0 then Q := Q + 1; }\\ &      \text{write (Q)}  \\ \hline   
\textbf{$T_2$}& \text{read (Q);}\\& \text{read (P);} \\ & \text{if Q = 0 then P := P + 1;}   \\ & \text{write (P)} \\     \hline
\end{array}}$$

Any non-serial interleaving of T1 and T2 for concurrent execution leads to

  1. a serializable schedule
  2. a schedule that is not conflict serializable
  3. a conflict serializable schedule
  4. a schedule for which a precedence graph cannot be drawn
edited by

7 Answers

Best answer
82 votes
82 votes
Answer is (B).

Explanation: $T_1:r(P),r(Q),w(Q) T_2:r(Q),r(P),w(P).$

Now, consider any non serial schedule for example, $S:r_1(P),r_2(Q),r_1(Q),r2(P),w_1(Q),w_2(P).$

Now, draw a precedence graph for this schedule. Here there is a conflict from $T_1\to T_2$ and there is a conflict from $T_2\to T_1.$ Therefore, the graph will contain a cycle. So we can say that the schedule is not conflict serializable.
edited by
25 votes
25 votes

I found this way much simpler : 

 

9 votes
9 votes
Answer is b:

As for any non serial interleaving it is necessary that read(p) for t1 is executed before write(p) for t2 and read(q) for t2 is executed before write(q) for t1.This will give you a cycle of length 2 in the precedence graph.
6 votes
6 votes

P and Q are initialised to 0.

Consider the values of P and Q when T1 is executed followed by T2.

P=0 and Q=1

$T_2\rightarrow T_1$

P=1, Q=0

Consider another schedule

T1      T2
R(P)
R(Q)
        R(Q)
        R(P)
        if(Q=0),P=P+1
        W(P)
if (P=0), Q=Q+1
W(Q)

This execution would set values of P and Q both to 1.

As you can see, here consistency requirement the ACID property is broken. Consistency in results is not ensured.

Hence, any non-serial interleaving would never lead to a serial schedule.

Transactions T1 and T2 are inconsistent.

Answer-B

Answer:

Related questions

14.1k
views
4 answers
49 votes
go_editor asked Apr 21, 2016
14,138 views
Consider the following relations $A, B$ and $C:$ ... $3$0$1$
30.0k
views
6 answers
71 votes
gatecse asked Sep 29, 2014
29,967 views
Consider the following relations $A, B$ and $C:$ ... $.$(A\cup B)\bowtie _{A.Id > 40 \vee C.Id < 15} C$$7$4$5$9$
11.7k
views
4 answers
47 votes
Arjun asked Sep 29, 2014
11,665 views
Suppose $R_{1} (\underline{A}, B)$ and $R_{2} (\underline{C}, D) $ are two relation schemas. Let $r_{1}$ and $r_{2}$ be the corresponding relation instances. $B$ is a ... {C}(r_{2})$\prod_{B}(r_{1}) - \prod _{C}(r_{2}) \neq \varnothing$
17.0k
views
5 answers
28 votes
gatecse asked Aug 5, 2014
16,996 views
Given the basic ER and relational models, which of the following is INCORRECT?An attribute of an entity can have more than one valueAn attribute of an entity ... a relational table, an attribute can have exactly one value or a NULL value