Consider the following schedule S. 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.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
T2-T4-T3-T1
A schedule is conflict serializable when its precedence graph is acyclic; a topological order of that graph gives the equivalent serial execution order. Two operations conflict when they belong to different transactions, use the same item and at least one is a write.
Step 1 — item X: T2 reads and writes X at t1–t2, T4 reads and writes X at t3–t4, T3 reads and writes X at t5–t6. Conflicts: T2 → T4, T2 → T3 and T4 → T3.
Step 2 — item Y: T3 reads and writes Y at t1–t2, T1 reads and writes Y at t3–t4. Conflict: T3 → T1.
Step 3 — the precedence graph has edges T2→T4, T2→T3, T4→T3, T3→T1; it has no cycle, so S is conflict serializable.
Step 4 — T2 has no incoming edge and comes first; T4 must precede T3; T3 must precede T1. The only topological order is T2, T4, T3, T1.
Orders starting with T3 or T4 put a transaction before T2 although T2 wrote X before them, and the order T2-T3-T1-T4 places T3 before T4 although T4 wrote X before T3 read it.
T2-T4-T3-T1 option is correct.
Similar Questions
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 ?
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 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 ?
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 ?
