CS3402 Database Systems Tutorials
CS3402 Tutorial 8:
1. Which of the following schedules is (conflict) serializable? For each serializable schedule, determine the equivalent serial schedules.
(a) r1(X); r3(X); w1(X); r2(X); w3(X); (b) r1(X); r3(X); w3(X); w1(X); r2(X); (c) r3(X); r2(X); w3(X); r1(X); w1(X);
2. Consider the following concurrent schedule. Draw the serialization graph for the schedule. Is it conflict serializable?
Ta
Tb
Tc
Read(x)
Write(y)
Read(y)
Write(y)
Write(x)
Commit
Write(z)
Commit
Commit
3. Consider schedules S1, S2 and S3 below. Determine whether each schedule is strict, cascadeless, recoverable, or nonrecoverable. Determine the strictest recoverability condition that each schedule satisfies.
(a) r1(X); w1(X); r2(X); r1(Y); w2(X); c2; c1;
(b) r1(X); w1(X); r2(X); r1(Y); w2(X); w1(Y); c1; c2; (c) r1(X); w1(X); w2(X); w1(Y); c1; r2(X); c2;
Can you change c) into a strict schedule?
CS3402 Database Systems CS3402 Tutorial 8:
1. Answer:
(a) Not conflict serializable, because the serialization graph contains cycle.
(b) Not conflict serializable, because the serialization graph contains cycle.
(c) Conflict serializable, because the serialization graph contains no cycle.
it is equivalent to this serial schedule:
r2(X); r3(X); w3(X); r1(X); w1(X); (or you can simply write T2, T3, T1)
2. Answer:
It is not serializable as the schedule is cyclic.
Tutorials
3. Answer:
(a) Non-recoverable, because T2 reads X written by T1£¬but T1 commits after T2.
If T1 abort after T2 commits, the value of X is not recoverable.
(b) Recoverable, because T2 reads X written by T1 and T2 commits after T1, which satisfy the condition of recoverable¡° A schedule S is recoverable if no
CS3402 Database Systems Tutorials
transaction T in S commits until all transactions T¡ä that have written some item X that T reads have committed.¡±
It is not cascadeless£¬ because T2 reads X written by T1 before T1 commits. If T1 fails, T1 has to be rolled back and T2 also need to be rolled back.
(c) Cascadeless. Because T2 reads X written by T1 after T1 commits. It satisfies the condition of Cascadeless schedule ¡°Every transaction reads only the items that are written by committed transactions.¡±
It is not the strict schedule because T2 write X after T1 write X but before T1 commits. It does not satisfy the condition of strict schedule :¡°A schedule in which a transaction can neither read or write an item X until the last transaction that wrote X has committed.¡±
Schedule (c) can be changed into the strict schedule: r1(X); w1(X); w1(Y); c1; w2(X); r2(X); c2;