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

Consider three data items D1, D2, and D3, and the following execution schedule of transactions T1, T2, and T3. In the diagram, R(D) and W(D) denote the actions reading and writing the data item D respectively.


Which of the following statements is correct?

  1. The schedule is serializable as T2; T3; T1

  2. The schedule is serializable as T2; T1; T3

  3. The schedule is serializable as T3; T2; T1

  4. The schedule is not serializable

asked in Databases by Veteran (59.5k points)
edited by | 1.5k views
Can't we check the schedule by trying to convert it in a serial schedule???
I hava a doubt...if trans T1 is writing a irem which is final means bo else trans is writing after this but reading it. Schenario:

T1.   . T2




So here can we take T1 as final write ?

4 Answers

+20 votes
Best answer
There is a cycle in precedence graph so schedule is not conflict serialisable.
Check View Serializability:
Checking View Serializability is NPC problem so proving by contradiction..

1. Initial Read
T2 read D2 value from initial database and T1 modify D2 so T2 should execute before T1.
i.e., T2 $\to$ T1

2. Final write.
final write of D1 in given schedule done by T2 and T1 modify D1 i.e. W(D1)..
that means T2 should execute after T1.
i.e., T1 $\to$ T2

So, schedule not even View Serializable.
Not Serializable.
answered by Veteran (55.1k points)
selected by
for checking view serialization, there is a more simple explanation than checking NPC and contradictory proofing,

ie. just check if there is any blind write in the execution schedule of transactions, if yes then only we need to form view equivalence graph.

in this case there is no blind write under either of the three transactions, so we can say that its not view serializable.hence, not serializable.

option d is right one
we can also draw the polygraph and check for view serializability

Having blind writes does not imply that it is view serializable.A schedule which is not conflict serializable will be having two choices :

    1)Not containing Blind writes : then surely it will not be view serializable and thus not Serializable.

   2)Containing Blind writes : it may/may not be view serializable. Then we will go for the Polygraph.

+6 votes

Conflict Serializability is  the sufficient condition for a schedule to be Serializable while View Serializability is the Neccassary and Sufficient condition for a Serializable schedule.

So first we will check conflict serializability using precendence graph. Here it containing the cycle and thus it fails for conflict serializability.Now we will go for the Blind Writes check.

if a schedule is not conflict serializable and not containing the blind writes then it FAILS for view serializability also.

As given schedule not containing any Blind write, it is not View serializable.Thus, the given schedule is not Serializable. 

answered by Active (1.6k points)
+5 votes
The above schedule is not conflict serializable as there is a cycle in the precedence graph .Also no blind writ in any of the three transactions (i.e write without read ) which is a must condition for view serializable  . So it is not serializable.

For Serializable : A schedule is serializble if it is either conflict serializable or view serializable  So simple and easy
answered by Junior (821 points)
–3 votes
answered by Junior (609 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

38,174 questions
45,676 answers
49,562 users