# GATE2014-2-29

13.3k views

Consider the following schedule S of transactions $T1, T2, T3, T4:$
$${\begin{array}{|l|l|l|l|}\hline \textbf{T1}& \textbf{T2}& \textbf{T3}& \textbf{T4} \\\hline & \text{Reads(X)} \\ && \text{Writes(X)} \\ && \text{Commit} \\ \text{Writes(X)} \\ \text{Commit}& \\ & \text{Writes(Y) } \\ & \text{Reads(Z)} \\ & \text{Commit} \\ &&& \text{Reads(X)} \\ &&& \text{Reads(Y)} \\ & &&\text{Commit} \\\hline \end{array}}$$
Which one of the following statements is CORRECT?

1. S is conflict-serializable but not recoverable
2. S is not conflict-serializable but is recoverable
3. S is both conflict-serializable and recoverable
4. S is neither conflict-serializable not is it recoverable

edited
0
i have a small doubt in this que...as it is conflict serializable ie it can be converted into a serial schedule

its precedence graph contain only 2 edges t2->t1 and t2->t3

so acc to it,the schedule can be serial in t2 t1 t3 t4 so now t4 is reading x value written by t3(even if it is committed) instead of x value written by t1....isint it wrong.... is something missing here....

plz clear my doubt
0
plz.....sm1 explain it to me.....i think i m missing smthing.......
0
there is only one edge is CSS that is from T2 -> T3 . so for rest transactions can be anywhere retaining this particular order.
0
everyone say about the answer of the question contain only two edges ie 2 to 1 and 2 to 3. But according to my solution it has more than 2 edges ie 2 to 1(R2(X) to W1(X)) and 2 to 3(R2(X) to W3(X)) and 3 to 1(W3(X) to W1(X)) and 3 to 4(W3(X) to R4(X)) and ....2 to 4(W2(Y) to R4(Y)). Please tell me my soln is correct or not
1
@KadharHussan As transactions are getting committed, don't look in other columns after the rows they get committed.
0
transaction T3 write data without read then how this will be view serializable?
0
@arjun sir . Please tell whether we have to ignore the commits while making the precedence graph for conflict serializability.
1

Saurabh666 No you can not ignore. Infact commit operation says that there will not be any conflict due to finished transaction.

1

.isint it wrong.... is something missing here....

plz clear my doubt

@qwertyui , Mistake is that you are drawing wrong precedence graph.

1

general  doubt: if a schedule is conflict serializable then always is it recoverable? No. See details in NPTEL video below.

From 21 min

0

thanks

and can you change the schedule as it is recoverable and draw the result.

0
Answer is c) S is both conflict Serializable as well as View Serializable.

Answer: S is both conflict serializable and recoverable.

Recoverable? Look if there are any dirty reads? Since there are no dirty read, it simply implies schedule is recoverable( if there were dirty read, then we would have taken into consideration the order in which transactions commit)

Conflict serializable? Draw the precedence graph( make edges if there is a conflict instruction among Ti and Tj. But for the given schedule, no cycle exists in precedence graph, thus it's conflict serializable.

Hope this helps.
1 flag:
✌ Edit necessary (goxul “Deepak's answer is more correct.”)

edited
3
general  doubt: if a schedule is conflict serializable then always is it recoverable ?
11
No, conflict serialzable is not always a recoverable schedule.. a non-recoverable schedule is one where we perform a dirty read, which we can be done without violating conflict serializablity of the schdule..!! In the given schdule there is no dirty read.. every read is performing after commit..

1
will the position of commit do any change in the precedence graph for finding conflict serializability?
0
Yes thats always true.
1
i have a small doubt in this que...as it is conflict serializable ie it can be converted into a serial schedule

its precedence graph contain only 2 edges t2->t1 and t2->t3

so acc to it,the schedule can be serial in t2 t1 t3 t4 so now t4 is reading x value written by t3(even if it is committed) instead of x value written by t1....isint it wrong.... is something missing here....

plz clear my doubt
0

@hkara657 ..No It wont affect ..as i interpreted:-

Wiki says:->>Another definition for conflict-serializability is that a schedule is conflict-serializable if and only if its precedence graph/serializability graph, when only committed transactions are considered, is acyclic (if the graph is defined to include also uncommitted transactions, then cycles involving uncommitted transactions may occur without conflict serializability violation).

0
@Arvind Every Cascadeless schedule is also recoverable schedule, but every CS is not recoverable.
9

Precedence graph

1

Hi @Vicky rix ji,

Small correction is required edge will come from $T_{3}$ to $T_{1}$ also.

1
I suppose that "Every cascadeless schedule is recoverable, but not every recoverable schedule is cascadeless."  @Brij Mohan Gupta
0
Hey @ramandeep I have a doubt, other than dirty read what will happen if after the write operation in T3 (after the commit) there is a rollback in T2..then when T2 will start again and read the value that is inconsistent which it is not intended to do ..?
0
There is dirty read from T3->T4 and T1->T4 na? How are you concluding there is no dirty read?

Anyway it's Rocoverable because commit in T4 is happening after commit in T1 and T3.
0

sir is their will be edge from T3 to T1 ??

0

@Shaik Masthan got it .. thank you

1
I think there will be an edge from T3->T4? Please correct me if i wrong.
1
yes
0
Thank you.it's clear now
0

general  doubt: if a schedule is conflict serializable then always is it recoverable ?

example

S: 1w(x) 2R(x) commit T2 then faild T1

schedule css but not recoverable

3

still you people saying, there is an edge ( conflict ) from T3 to T4.

@Shaik Masthan Because indeed there will be this edge.

Many students are making incorrect Precedence graph.

T 3 is commited before T1  starts ===> there is no conflict.

if commit operation happens, after that just consider that transaction is over !

@Shaik Masthan , This is incorrect. If you don't put conflict edge from a committed transaction to a newly started transaction then How will you even make precedence graph for serial schedules? Moreover, suppose your argument is correct then according to your argument the precedence graph will be  as follows :

Now, for this precedence graph, there will be many serial schedules which will be conflict equivalent to this given schedule... like serial schedule $T4,T2,T1,T3$ will be equivalent to the given schedule which is wrong because in this serial schedule $T4$ is reading the value of data item $X$ directly from  the database(unmodified, initial value) But in the given schedule in the question $T4$ is reading the value of $X$ which is modified by $T1$... so clearly this schedule is not conflict equivalent to the given schedule... this schedule is Not even View equivalent to the given schedule.

Refer here for details : https://gateoverflow.in/1988/gate2014-2-29?show=325636#a325636

0

@Deepakk Poonia (Dee)

It's was my mistake that, doesn't update the wrong info after i understood...

Because i don't know where i commented !

0
NO edge from T3 to T1, as T3 has already committed before the conflicting operation with T1...

Even though @Ramandeep Singh has answered this question, I'd like to add some additional points because in the comments and discussion on this question, many students are having incorrect arguments which they think are correct.

The Mistake that most students are doing (in the comments to this question) is that they are Not making correct Precedence Graph because they are not making conflict edges in the Precedence graph "from a committed transaction to a newly started transaction"....which is completely wrong because if you do so then How will you make Precedence Graph for Serial Schedule??

Following all the definitions and concepts are directly (without modification) picked mostly from Navathe and some from the following link : http://www.ict.griffith.edu.au/~rwt/uoe/1.1.ccc.html

Refer Navathe if you still have some doubt.

Transactions :

transaction is effectively a sequence of read and write operations on atomic database items. A transaction may be incomplete because the (database) system crashes, or because it is aborted by either the system or the user (or application). Complete transactions are committed. Transactions must terminate by either aborting or committing.

Complete Schedule :

A schedule $S$ of $n$ transactions $T1, T2, ..., Tn$ is said to be a complete schedule if the following conditions hold:

1. The operations in $S$ are exactly those operations in $T1, T2, ..., Tn$, including a commit or abort operation as the last operation for each transaction in the schedule.
2. For any pair of operations from the same transaction $Ti$ , their relative order of appearance in $S$ is the same as their order of appearance in $Ti$ . (i.e Operation order in/of  every transaction must preserve.)
3. For any two conflicting operations, one of the two must occur before the other in the schedule.

Condition 1 simply states that all operations in the transactions must appear in the complete schedule. Since every transaction has either committed or aborted, a complete schedule will not contain any active transactions at the end of the schedule.

In general, it is difficult to encounter complete schedules in a transaction processing system because new transactions are continually being submitted to the system. Hence, it is useful to define the concept of the committed projection $C(S)$ of a schedule $S$.

Committed Projection of a schedule :

Committed Projection $C(S)$ of a schedule $S$ includes only the operations in $S$ that belong to committed transactions—that is, transactions $Ti$ whose commit operation $Ci$ is in $S$.

Given a schedule S, the committed projection C(S) is the subset of S consisting of operations ($r1(X), w2(Y),$ etc) that are part of transactions that have committed (that is, $r1(X)$ would be part of C(S) only if transaction 1's commit, $c1,$ were also part of S). This is sometimes useful in analyzing schedules when transactions are continuously being added.

A committed projection C(S) of a schedule S include the operations in S only from the committed transactions. Let's take an example :

Transactions:

T1: r1(X); w1(X); r1(Y); w1(Y); c1;

T2: r2(Y); w2(Y); a2;

T3: r3(X); w3(X);

S1: r1(X); r2(Y); w1(X); w2(Y); r1(Y); a2; w1(Y); c1; r3(X); w3(X);

Then C(S1) = ??

Well, C(S1) will be same as $T1$ because T3 has No Commit/Abort operation as the last operation of the transaction and T2 is Not committed. So, by the definition of Committed Transaction, C(S1) = T1.

Now, as according to Navathe,

We can theoretically define a schedule $S$ to be serializable if its committed projection $C(S)$ is equivalent to some serial schedule, since only committed transactions are guaranteed by the DBMS.

And It applies to both Conflict and View Serializability.

A schedule is serialisable if the effect of its committed projection (the restriction to its committed transactions) on any consistent database is identical to that of some serial schedule of its committed transactions.

(Conflict) Serialisability theorem :

Given a schedule $S$, define the serialisation graph(Precedence Graph) SG(S) to have the committed transactions of $S$ as its nodes, and a directed edge from $T1$ to $T2$ if $T1$ and $T2$ contain conflicting operations $O1$ and $O2$ such that $O1$ precedes $O2$ in $S.$ Then $S$ is serialisable if and only if SG(S) is acyclic.

http://www.ict.griffith.edu.au/~rwt/uoe/1.1.ccc.html

Now, coming to the given question :

The given schedule is Complete Schedule as all the transactions in the schedule are committed(or aborted). Moreover, the given schedule is Committed Projection of itself as well because all the Transactions are committed. Now, as the above definition of Conflict serializability suggests, we make Precedence graph for this schedule and in the precedence graph, the Nodes will be the Transactions participating in the committed projection of the schedule(which is same as the given schedule ) ..

The precedence graph will be as following :

From the precedence graph we can see that Only One serial schedule is conflict equivalent to the given schedule which is $T2,T3,T1,T4$ ..No other schedule is conflict equivalent to the given schedule.

Only One serial schedule is conflict equivalent to the given schedule which is $T2,T3,T1,T4$ ..This makes sense because $T2$ is reading the initial value of data item $X$ (directly from the database) But if we run either of $T3$ or $T1$ before $T2$ then they will write the data item $X$ and $T2$ will have to read the modified value of $X.$ Hence, Only one Serial Schedule can be equivalent to the given schedule and thet is $T2,T3,T1,T4.$

The Mistake that most students are doing (in the comments to this question) is that they are Not making correct Precedence Graph because they are not making conflict edges from a committed transaction to a new started transaction....which is completely wrong because if you do so then How will you make Precedence Graph for Serial Schedule??

Serial Schedule (Definition as it is given in Navathe) : Formally, a schedule S is serial if, for every transaction T participating in the schedule, all the operations of T are executed consecutively in the schedule; otherwise, the schedule is called nonserial. Therefore, in a serial schedule, only one transaction at a time is active—the commit (or abort) of the active transaction initiates execution of the next transaction. No interleaving occurs in a serial schedule.

$S = R_1(X) \,\, W_1(X) \,\,C1 \,\,R_2(X)\,\, W_2(X)\,\, C2\,\, R_3(X)\,\, W_3(X)\,\, C3$

If you make precedence graph for this schedule, then you must get a acyclic precedence graph But those students who are not putting conflict edges in the precedence graph "from a committed transaction to a newly started transaction" then you won't get any edges in this graph and the graph will be empty graph..... which you know is not correct.

Consider this schedule :

 T1 T2 T3 Writes(X) Writes(Z) Writes(X) Commit Writes(Y) Reads(Y) Writes(Z) Writes(M) Commit Reads(M) Commit

Try to find whether this schedule is Conflict Serializable Or Not??

If you do it correctly, It is Not conflict serializable because there is Cycle in the precedence graph of this schedule. But If you don't put conflict edges in the precedence graph "from a committed transaction(T1) to a newly started transaction(T3)" then you won't get edge $T1 \rightarrow T3$ in the precedence graph and hence, you will incorrectly get the answer as Conflict serializable.

1

Thank you @Deepakk Poonia (Dee) Sir for your very detailed explanation.

But in some of GATE questions we find schedules which are partial.In such case if we don't have any committed transactions,then how should we draw the precedence graph?By assuming all will commit some time in future?

3
yes, when in the question, commit/abort is not given for any transaction then you can draw the dependency graph assuming they will commit at some point later.
0

Ohkkk got the point Thank you

1
0
Sir you said newly added transaction it means if it is not newly added then do not consider conflict...i understood there should be edge for T1 to T3 because T3 is newly added but here T3->T2 there is edge but why this edge is taken here T2 is not newly added.
0

Sir you said newly added transaction it means if it is not newly added then do not consider conflict.

No, I did not say that. I did not mean it. You have interpreted wrongly.

0
So overall the way we used to check CS when commit is not given, the same way we will also check when commit is given because we are taking conflict action even after commit??
0
Yes
0

here T2 reads X before T1 & T3 both writes X & both commits before T2. so shouldn’t we consider it as dirty read ?

or T2 never writes X, that’s why it’s not considered as dirty read ?

0
Refer Navathe for definition of Dirty Read.
0

Deepakk Poonia (Dee)

Thanks for such a nice explanation,but what about recoverability, what i mean is now that we’ve obtained the serial schedules, will we check if their Commit operation is following the same order as “Dirty read” won’t be a sufficient condition, in a nutshell like if there was a dirty read then the schedule would be irrecoverable right.?

To check for conflict-serializable, we need to make a precedence graph, if the graph contains a cycle, then it's not conflict serializable, else it is. Here, for the precedence graph there will be only two directed edges, one from T2 -> T3 ( Read- Write Conflict), and another from T2 -> T1( Read- Write Conflict), hence no cycle, so the schedule is conflict serializable. Now to check for Recoverable, we need to check for a dirty-read operation( Write by Transaction Ti, followed by Read by Transaction Tj but before Ti commits) between any pair of operations. If no dirty-read then recoverable schedule, if a dirty read is there then we need to check for commit operations. Here no dirty read operation ( as T3 and T1 commits before T4 reads the Write(X) of T3 and T1 , and T2 commits before T4 reads the Write(Y) of T2 ). Therefore the schedule is recoverable. Hence, Option C.
2

Precedence graph that you are drawing is incorrect. Though you are getting correct answer by applying wrong concept.

## Related questions

1
9.6k views
SQL allows duplicate tuples in relations, and correspondingly defines the multiplicity of tuples in the result of joins. Which one of the following queries always gives the same answer as the nested query shown below: select * from R where a in (select S.a from S) select R.* from R, S where R.a ... R,(select distinct a from S) as S1 where R.a=S1.a select R.* from R,S where R.a=S.a and is unique R
Consider a join (relation algebra) between relations $r(R)$ and $s(S)$ using the nested loop method. There are 3 buffers each of size equal to disk block size, out of which one buffer is reserved for intermediate results. Assuming size(r(R))<size(s(S)) , the join will have fewer number of ... $r(R)$ and $s(S)$ is more than 0.5. join selection factor between $r(R)$ and $s(S)$ is less than 0.5.
Consider the transactions $T1, T2, \:\text{and} \:T3$ and the schedules $S1 \:\text{and} \:S2$ given below. $T1: r1(X); r1(Z); w1(X); w1(Z)$ $T2: r2(Y); r2(Z); w2(Z)$ $T3: r3(Y); r3(X); w3(Y)$ ... schedules is TRUE? Only $S1$ is conflict-serializable. Only $S2$ is conflict-serializable. Both $S1$ and $S2$ are conflict-serializable. Neither $S1$ nor $S2$ is conflict-serializable.
Consider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item x, denoted by $r(x)$ and $w(x)$ respectively. Which one of them is conflict serializable? $r_1(x)$; $r_2(x)$; $w_1(x)$; $r_3(x)$; $w_2(x)$; $r_2(x)$; $r_1(x)$; $w_2(x)$ ... $r_2(x)$; $r_1(x)$; $w_2(x)$; $w_1(x)$; $r_2(x)$; $w_2(x)$; $r_3(x)$; $r_1(x)$; $w_1(x)$;