8 votes 8 votes Consider the following schedule: S : w1(A) w1(B) r2(A) w2(B) r3(A) w3(B) The number of schedules conflict equivalent are __________ . Databases databases + – srestha asked Feb 3, 2017 srestha 7.3k views answer comment Share Follow See all 12 Comments See all 12 12 Comments reply Show 9 previous comments smsubham commented Dec 22, 2019 reply Follow Share @Sumaiya23 its asking for conflict equivalent and not conflict serializable. 0 votes 0 votes mrinmoyh commented Jan 23, 2020 reply Follow Share see the first comment under this qsn - https://gateoverflow.in/10299/conflict-equivalent 0 votes 0 votes Shiva Sagar Rao commented Jan 19, 2021 reply Follow Share Similar questions: https://gateoverflow.in/118640/gate2017-2-44 https://gateoverflow.in/10299/conflict-equivalent https://gateoverflow.in/37446/number-of-conflict-serializible-schedules 0 votes 0 votes Please log in or register to add a comment.
Best answer 14 votes 14 votes ............................ Anusha Motamarri answered Feb 3, 2017 • edited Feb 3, 2017 by dd Anusha Motamarri comment Share Follow See all 39 Comments See all 39 39 Comments reply srestha commented Feb 3, 2017 reply Follow Share ok .. 0 votes 0 votes cse23 commented Feb 3, 2017 reply Follow Share @Anusha is it like we always always take read operation then we find the places where we can place it ...preserving its conflict??? 0 votes 0 votes Kaushik.P.E commented Feb 3, 2017 reply Follow Share From the precedence graph, it can be inferred that the equivalent serial schedule is T1-> T2 -> T3. This order must be preserved and the order of operations within each transaction must be preserved ie. R3(A) must precede W3(A). And to maintain order of the schedule last operation of transaction T1,T2,T3 must precede each other in the same order. Hence as mentioned R2(A) can be executed in two time slots and R3(A) can be executed in four time slots.totally 8 possible schedules. 0 votes 0 votes Kaushik.P.E commented Feb 3, 2017 reply Follow Share Actually given schedule is a serial schedule so precedence graph is not required. 0 votes 0 votes dd commented Feb 3, 2017 reply Follow Share A precedence graph topological orders for this given schedule S will give the wrong result because we do not need no of serial schedules which are conflict equivalent to this schedule. Rather we need non-serial+serial schedules which are conflict equivalent to this given schedule S. 0 votes 0 votes dd commented Feb 3, 2017 reply Follow Share wrong : Topological ordering of precedence graph gives all possible conflict equivalent schedules. It gives serial conflict equal only. 0 votes 0 votes Kaushik.P.E commented Feb 3, 2017 reply Follow Share I agree that it's not needed. But as I said order of operations within each transaction must be preserved. And the original conflict equivalent serial schedule must also be preserved. Reference you've added does maintains the same T1->T2->T3 0 votes 0 votes srestha commented Feb 3, 2017 i edited by srestha Feb 3, 2017 reply Follow Share Simply we can say arrangements of schedules which are non conflicting operation gives conflict equivalent schedule. 0 votes 0 votes srestha commented Feb 3, 2017 reply Follow Share What will be answer for it , if it is asking for conflict serializable schedule? 0 votes 0 votes Kaushik.P.E commented Feb 3, 2017 reply Follow Share When I say order must be preserved I don't mean T2 starts after T1. operations can be interleaved but T1 must end before T2 is what I mean. "And to maintain order of the schedule last operation of transaction T1,T2,T3 must precede each other in the same order." 0 votes 0 votes Kaushik.P.E commented Feb 3, 2017 reply Follow Share Am I wrong? 0 votes 0 votes Kaushik.P.E commented Feb 3, 2017 reply Follow Share If the operations are not serial as given in the question. Then we must use precedence graph to find conflict equivalent serial schedule. And find all combinations such that this order is preserved. correct me If I am wrong. 0 votes 0 votes dd commented Feb 3, 2017 reply Follow Share @Kaushik.P.E The number of schedules conflict equivalent are______ this is the question. We agree ! They ask conflict equal schedules but not conflict equal schedules preserving any kind or orders. And to your comment on topological: a general case is shown below. Not related to this QS Some other non-serial schedules might NOT be conflict equal to $(1)$ and $(2)$ always. But they may become conflict equal to S We need those some others if exist which we did here (in this QS) by brute force. 0 votes 0 votes Kaushik.P.E commented Feb 3, 2017 reply Follow Share Here there are two conflict equivalent serial schedules. Either one of the the two orders must be preserved. Are you saying that we can take combinations in which T2 ends before T1? 0 votes 0 votes Kaushik.P.E commented Feb 3, 2017 reply Follow Share When the order of conflicting instructions is maintained, naturally conflict equivalent serial order will also be maintained. 0 votes 0 votes Kaushik.P.E commented Feb 3, 2017 reply Follow Share Check all the 8 combinations you've mentioned. The order T1->T2->T3 will be maintained. If any combination doesn't do so then please mention it. 0 votes 0 votes dd commented Feb 3, 2017 reply Follow Share Two schedules $S$ and $T$ are said to be conflict equal iff What serial orders is maintained in S and T, those things we need not bother in this QS Given any random schedule $S$ when we are asked to total find no of conflict equal schedules to this S, we just need to see the conflict operations and should not change their relative orders.That's it 0 votes 0 votes srestha commented Feb 3, 2017 reply Follow Share Accha number of conflict serializable schedule is 1 here? I somewhere read no. of conflict serializable schedule is n! @Debasish @ Kaushik.P.E 0 votes 0 votes dd commented Feb 3, 2017 reply Follow Share @Kaushik.P.E ..how will you proceed if given schedule $S$ is non-serial? 0 votes 0 votes Kaushik.P.E commented Feb 3, 2017 reply Follow Share "we just need to see the conflict operations and should not change their relative orders.That's it" Ya I agree we need not worry about it. When the order of conflicting instructions is maintained, naturally conflict equivalent serial order will also be maintained. Check all the 8 combinations you've mentioned for this QS. The order T1->T2->T3 will be maintained. If any combination doesn't do so then please mention it. 0 votes 0 votes srestha commented Feb 3, 2017 reply Follow Share yes non serial schedule cannot be conflict equivalent.because to be conflict equivalent, it has to be atleast conflict serializable 0 votes 0 votes Kaushik.P.E commented Feb 3, 2017 reply Follow Share Maintain order of conflicting instructions and ensure conflict equivalent serial schedule order is maintained. i.e T1 completes before T2 and so on. 0 votes 0 votes dd commented Feb 3, 2017 reply Follow Share @Kaushik.P.E Ya I agree we need not worry about it. When the order of conflicting instructions is maintained, naturally conflict equivalent serial order will also be maintained When the order of conflicting instructions is maintained- as you said, how can you assume that the digraph will not contain loop in it ?? always ?? In your case, there must always to some conflict serial equal existing. What I think given S may not be conflict serializable. Going by your logic, in this case, there are no conflict equal schedules to S ???? 0 votes 0 votes Kaushik.P.E commented Feb 3, 2017 reply Follow Share Ya When precedence graph i.e digraph has loops then there is no conflict equivalent order at all. 0 votes 0 votes srestha commented Feb 3, 2017 reply Follow Share @ Debashish No, there is atleast 1 conflict serialzable schedule 0 votes 0 votes Kaushik.P.E commented Feb 3, 2017 reply Follow Share First of all such a schedule will not be consistent. then I can take all possible concurrent schedules as conflict equivalent to that schedule. 0 votes 0 votes Rahul Jain25 commented Feb 3, 2017 reply Follow Share Why just 8??? I am getting much more than that. You can also shuffle between operations on A and B data items. By using permutations I am getting much more than 8. We can suffle operations on A and B also right??? 0 votes 0 votes dd commented Feb 3, 2017 reply Follow Share @srestha ..yes I am aware of that :) :) @ Kaushik.P.E Ya When precedence graph i.e digraph has loops then there is no conflict equivalent order at all. Here is a given S. There exists conflict equal to this S. Although S does not have any conflict serial equivalent. 0 votes 0 votes Kaushik.P.E commented Feb 3, 2017 reply Follow Share Only if that digraph is a DAG everything else comes into picture. conflict equivalence is done in order to maintain consistency. If precedence graph is cyclic then all possible schedules including all inconsistent schedules will be equivalen to it. 0 votes 0 votes Kaushik.P.E commented Feb 3, 2017 reply Follow Share Understand why conflict equivalnce must be maintained. conflict equivalence is to ensure results are consistent to some serial schedule. If that is ignored then all possible concurrent schedules including inconsistent schedules will be conflict equivalent to it. 0 votes 0 votes Rahul Jain25 commented Feb 3, 2017 reply Follow Share My approach is that 6 operations can be arranged by 6! And then write operations on B have to be done in specific order therefor divide by 3! Now for A item we can have two orders w1(a) then r2(a) or r3(a) hence divide by 2. So total = 6!×2/(3!×3!)=40 possible 0 votes 0 votes dd commented Feb 3, 2017 reply Follow Share @rahul. Orders or operations inside a particular transaction must be same. We can not change the transaction itself. example Initial balance = $100$ T : deposit(100) withdraw(100), these order should not change in a running schedule. 2 votes 2 votes Kaushik.P.E commented Feb 3, 2017 reply Follow Share In the schedule you've given there's no order. So all possible concurrent schdules will be equivalent to it. 0 votes 0 votes Rahul Jain25 commented Feb 3, 2017 reply Follow Share Oops went too much into permutations. Thanks @ Debashish 0 votes 0 votes Kaushik.P.E commented Feb 3, 2017 reply Follow Share just ensuring first R(A) in T1 occurs before W(A) of T2 will make no difference. 0 votes 0 votes dd commented Feb 3, 2017 reply Follow Share @Kaushik.P.E: My point was just to say that topological order does not help in this QS and we need to consider that at all to solve this QS and any serial order related stuff. I only used the definitions from the books in conflict equivalent irrespective of the given schedule property. Not needed but I am quoting these definitions of conflict equivalent Korth : If a schedule $S$ can be transformed into a schedule $S^{'}$ by a series of swaps of nonconflicting instructions, we say that $S$ and $S^{'}$ are conflict equivalent. Navathe: The definition of conflict equivalence of schedules is as follows: Two schedules are said to be conflict equivalent if the order of any two conflicting operations is the same in both schedules What you are saying may be relevant in some other cases. 0 votes 0 votes Kaushik.P.E commented Feb 3, 2017 reply Follow Share oh k maybe I am wrong... 0 votes 0 votes junaid ahmad commented Jul 16, 2017 reply Follow Share I think this is the correct approach https://gateoverflow.in/10299/conflict-equivalent 2 votes 2 votes gatecrack commented Sep 3, 2018 reply Follow Share thanks 0 votes 0 votes Please log in or register to add a comment.
6 votes 6 votes I think this should do it . Pratyush Priyam Kuan answered Dec 24, 2019 Pratyush Priyam Kuan comment Share Follow See all 2 Comments See all 2 2 Comments reply sags.sharma commented Jan 25, 2020 reply Follow Share @ Pratyush Priyam Kuan If you see conflict equivalent schedule for this it will be T1 -> T2 -> T3, So how can we take operation 5 before T2 . 0 votes 0 votes Pratyush Priyam Kuan commented Jan 25, 2020 reply Follow Share @sags.sharma position of 5 will not affect the conflict serializability. please check.. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes you can arrange R3 at 4 places and R2 at 2 places so total 8 way possible as there is no dependency between R2 and R4 abhishek tiwary answered Jan 23, 2018 abhishek tiwary comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes let me know if there is any mistake- Prateek Raghuvanshi answered Aug 3, 2018 Prateek Raghuvanshi comment Share Follow See all 0 reply Please log in or register to add a comment.