The Gateway to Computer Science Excellence
+33 votes
4.6k 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
in Databases by Veteran (105k points)
edited by | 4.6k views
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.

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

3 Answers

+39 votes
Best answer
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.
by (171 points)
edited by
+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..

 

http://coddicted.com/recoverable-and-cascadeless-schedules/
+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.
+7

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 ?

answer is no 

example 

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

 schedule css but not recoverable 

+2

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. 

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

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 !

+18 votes

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. 

by Boss (27.5k points)
0

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?

 

+1
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 @Deepakk Poonia (Dee) Sir.

+1
Read each word of your answer carefully. Admittedly, I already knew most of it, but your explanation certainly made things clearer. Thank you!
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
+4 votes
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.
by Loyal (9.9k points)
+1

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

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

Answer:

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
50,737 questions
57,313 answers
198,349 comments
105,051 users