Consider following schedules involving two transactions : S1 : r1(X); r1(Y); r2(X); r2(Y); w2(Y); w1(X) S2 : r1(X); r2(X); r2(Y); w2(Y); r1(Y); w1(X) Which of the following statement is true ?
S1 is not conflict serializable and S2 is conflict serializable.
A schedule is conflict serializable when its precedence graph is acyclic. Two operations conflict if they belong to different transactions, access the same data item and at least one of them is a write; each conflicting pair adds an edge from the transaction whose operation comes first.
Step 1 — S1: r1(Y) comes before w2(Y), giving edge T1 → T2. r2(X) comes before w1(X), giving edge T2 → T1. The graph has the cycle T1 → T2 → T1, so S1 is not conflict serializable.
Step 2 — S2: r2(X) comes before w1(X), giving T2 → T1; w2(Y) comes before r1(Y), again T2 → T1. r1(X) and r2(X) are both reads and do not conflict, and T1 never writes Y. The only edge is T2 → T1, the graph is acyclic, and S2 is conflict equivalent to the serial order T2, T1.
So the statements claiming S1 is conflict serializable (alone or together with S2) are wrong because of the cycle, and the statement that neither schedule is conflict serializable ignores the acyclic graph of S2.
S1 is not conflict serializable and S2 is conflict serializable. option is correct.
Similar Questions
Consider the following schedule S.
T1 T2 T3 T4 Timestamp R(X) R(Y) t1 W(X) W(Y) t2 R(Y) R(X) t3 W(Y) W(X) t4 R(X) t5 W(X) t6 R(X) denotes read operation on data item X by transaction Ti.
W(X) denotes write operation on data item X by transaction Ti.
Choose the correct execution order for the above schedule S.
Consider the transactions T1, T2, T3 and the schedules S1 and S2 given below.
T1 : r1(x); r1(z); w1(z)
T2 : r2(y); r2(z); w2(z)
T3 : r3(y); r3(x); w3(y)
S1 : r1(x); r3(y); r3(x); r2(y); r2(z); w3(y); w3(z);
r1(z); w1(x); w1(z)
S2 : r1(x); r3(y); r2(y); r3(x); r1(z); r2(z); w3(y);
w1(x); w2(z); w1(z)
Which one of the following statements about the schedules is TRUE ?
Important Questions from Serializability of Schedules - Teaching
Suppose a database schedule 5 involves transactions T 1, T 2, .............T nConsider the precedence graph of S with vertices representing the transactions and edges representing the conflicts. If S is serializable, which one of the following orderings of the vertices of the precedence graph is guaranteed to yield a serial schedule ?
Consider the following statements:
Statement I: Conservative 2 PL is a deadlock-free protocol.
Statement II: Thomas's write rule enforces conflict serializability.
Statement III: Timestamp ordering protocol ensures serializability based on the order of transaction timestamps.
Which of the following is correct?
Consider the following schedules involving two transactions.
S 1: r 1(X) ; r 1(Y) ; r 2(X) ; r 2(Y) ; w 2(Y) ; w 1(X)
S2 : r 1(X) ; r 2(X) ; r 2(Y) ; w 2(Y) ; r 1(Y) ; w 1(X)
Which one of the following statements is correct with respect to above?Consider the following schedule S.
T1 T2 T3 T4 Timestamp R(X) R(Y) t1 W(X) W(Y) t2 R(Y) R(X) t3 W(Y) W(X) t4 R(X) t5 W(X) t6 R(X) denotes read operation on data item X by transaction Ti.
W(X) denotes write operation on data item X by transaction Ti.
Choose the correct execution order for the above schedule S.
Consider the transactions T1, T2, T3 and the schedules S1 and S2 given below.
T1 : r1(x); r1(z); w1(z)
T2 : r2(y); r2(z); w2(z)
T3 : r3(y); r3(x); w3(y)
S1 : r1(x); r3(y); r3(x); r2(y); r2(z); w3(y); w3(z);
r1(z); w1(x); w1(z)
S2 : r1(x); r3(y); r2(y); r3(x); r1(z); r2(z); w3(y);
w1(x); w2(z); w1(z)
Which one of the following statements about the schedules is TRUE ?
