The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
2.3k views

Consider the following schedule S of transactions T1, T2, T3, T4:

T1 T2 T3 T4

  Reads(X)    
       
    Writes(X)  
    Commit  
Writes(X)      
Commit      
       
  Writes(Y)    
  Reads(Z)    
  Commit    
       
      Reads(X)
      Reads(Y)
      Commit

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
asked in Databases by Veteran (101k points)
edited by | 2.3k 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
0
@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.

2 Answers

+26 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.
answered by (171 points)
edited by
+1
general  doubt: if a schedule is conflict serializable then always is it recoverable ?
+5
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.
+2

Precedence graph

 

+1

Hi @Vicky rix ji,

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

0
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 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.
answered by Loyal (8.4k points)
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

39,440 questions
46,623 answers
139,377 comments
57,022 users