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 ?
Only S1 is conflict-serializable
A schedule is conflict-serializable when its precedence graph has no cycle. Two operations conflict when they belong to different transactions, access the same item and at least one of them is a write; each conflict adds an edge from the transaction whose operation comes first.
Step 1 — S1, item y: r2(y) comes before w3(y), giving T2 → T3. Item x: r3(x) comes before w1(x), giving T3 → T1.
Step 2 — S1, item z: r2(z) before w3(z) gives T2 → T3; w3(z) before r1(z) and w1(z) gives T3 → T1; r2(z) before w1(z) gives T2 → T1. The graph T2 → T3 → T1 has no cycle, so S1 is conflict-serializable, equivalent to the serial order T2, T3, T1.
Step 3 — S2, item z: r1(z) comes before w2(z), giving T1 → T2; r2(z) and w2(z) come before w1(z), giving T2 → T1.
Step 4 — The edges T1 → T2 and T2 → T1 form a cycle, so S2 is not conflict-serializable (the other edges, T2 → T3 on y and T3 → T1 on x, do not remove it).
Because S2 has a cycle, any statement calling S2 conflict-serializable is false, and because S1 has an acyclic graph, the claim that neither schedule is serializable is also false.
Only S1 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 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 ?
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 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 ?
