The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+30 votes

Consider the following transactions with data items $P$ and $Q$ initialized to zero:
   \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

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
asked in Databases by Veteran (399k points)
edited by | 4.4k views

@Bikram sir 

wht does it mean non-serial interleaving ?



wht does it mean non-serial interleaving ?

Non serial Interleaving means  :

  1. read(P) for T1 is executed before write(P) for T2 and
  2. read(q) for T2 is executed before write(q) for T1.

non-serial schedule is a schedule where the operations of a group of concurrent transactions are interleaved


what does option (d) mean a schedule for which a precedence graph cannot be drawn
is this possible? , every schedule has transaction represented as nodes and conflicting operations as edges, can someone explain ? @Bikram / @ Arjun ?

how to draw graph for this ?
@Arjun Sir,

What will be serial schedule output of both transactions?

If T1 -> T2: Conflict between the last operation of T1 with the first operation of T2.

If T2 -> T1: Conflict between the last operation of T2 with the first operation of T1.

What can we infer from the above statements?

Non-serial Interleaving means  :

  1. read(P) for T1 is executed before write(P) for T2 and
  2. read(q) for T2 is executed before write(q) for T1.

How is this derived from the given problem?

What is significant of this statement here

P and Q are initialized to zero ?

@Bikram sir

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

It means we have to check for every possible non serial interleaving possible over T1 and T2 right ?

6 Answers

+52 votes
Best answer
Answer is (B). Explanation: $T1:r(P),r(Q),w(Q) T2:r(Q),r(P),w(P)$ now, consider any non serial schedule for example, $S:r1(P),r2(Q),r1(Q),r2(P),w1(Q),w2(P)$ now, draw a precedence graph for this schedule. here there is a conflict from $T1->T2$ and there is a conflict from $T2->T1$ therefore, the graph will contain a cycle. so we can say that the schedule is not conflict serializable.
answered by Loyal (8.1k points)
edited by
consider non serial schedule S:r2(Q),r2(P),r1(P),w2(Q),r1(Q),w1(P). this schedule is conflict serizable .
is the transactions view serializable also....???
Anmol it can be view serializable in some cases but here we're talking about any ( all). In that way option is only (b) .
I think that it's not even view serializable . Here T1 is reading original value of P and T2 is reading original value of Q.

If we consider T1 followed by T2 then T1 will write the value of Q and T2 will not be able to read the original value of Q. Same is the case with T2 followed by T1, T2 will write the value of P and T1 will not be able to read the original value of P

Correct me if I am wrong.

your operations are wrong

for example : there is no write on P in transaction 1, but you wrote w1(p) in you schedule

please check it once
how to consider any non serial schedule?? Is it randomly choosen??
sorry.. not sure now as I am not in touch with database since more than two years. I would suggest to wait for someone's reply or check the reference book..

            T1                                                                             T2 


here we can clearly see that T1==>T2,  T2==>T1 both conflict pairs are present ,so it's precedence graph will contain cycle ,so not conflict serializable schedule, and there is not any blind-write so there must not be view serializability also.( not CSS + no blind-write ==> no view serializable ,,,, OR ,,,no CSS + view serializable==> atleast one blind-write)


@ ,  Is it true for all other non-serial schedule????


@MRINMOY_HALDER... yes try for any possibility of non serial will not be conflict serializable.

Can we say schedule is not serial schedule so it is not conflict serializable. Saying this is right ?
+8 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.
answered by Junior (935 points)
+4 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
if (P=0), Q=Q+1

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.


answered by Boss (25.4k points)

here in question it is asking about the ANY so try to take an counter example and try falsify the each statement

A:Can we make non serializable schdule out of give then schedule 

 see S:r1(P),r2(Q),r1(Q),r2(P),w1(Q),w2(P)S:r1(P),r2(Q),r1(Q),r2(P),w1(Q),w2(P) 

C Again false using same example of option a

D:We can draw precedence graph of any schedule  so false 

so OPTION B is correct


+2 votes

I found this way much simpler : 


answered by Active (5k points)
0 votes
option B
answered by Junior (787 points)
is this schedule view serializable. i guess its not.
how?pls explain
If a schedule has to be view serializable, then it must have blind writes in the transaction, as we see there are no blind writes, it is not view serializable.
0 votes

Here, the "non-serial" in "non-serial interleaving" is superfluous (redundant). Interleaving, by its very nature, is non-serial.

You've been asked to interleave, which means, you cannot execute all operations of one transaction in a row followed by all operations of the other transaction. Otherwise it would just be a serial schedule, which we don't want.

Our schedule can start with the first operation of either T1 or T2 (it has to start somewhere). If you start with T1 in your schedule (read1 P) then you cannot end T1 (write1 Q) without first starting T2 (read2 Q). Similarly, if you start with T2 (read2 Q) then you cannot end T2 (write2 P) without first starting T1 (read1 P). In both cases, you are taking a serial(izable) schedule (T1 $\rightarrow$ T2 in the first case, and T2 $\rightarrow$ T1 in the second) and changing the order of two conflicting operations.

We know that the moment we change the order of a pair of conflicting operations in a serial (or serializable) schedule , the schedule no longer remains conflict serializable. Hence, B is the correct answer.

answered by Junior (899 points)
edited by

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
49,403 questions
53,576 answers
70,852 users