CPSC 304 – Tutorial #9 Transactions and Serializability (cont.)
March.23, 2007 Solutions

Question 1: Consider the following ordering S of transactions: T2: R(X); T3: W(X); T3: commit; T1: W(Y); T1: commit; T2: R(Y); T2: W(Z); T2: commit; T4: R(X); T4: R(Y); T4: commit. a) Draw a precedence graph for S. b) Is S conflict-serializable according to the precedence graph? Solutions: a) Precedence graph for S: T1 -> T2 -> T3 -> T4

b) S is conflict-serializable because there are no cycles in the graph. And it is also serializable (we’ve discussed this in last tutorial). The serial ordering can be seen from the precedence graph directly. Question 2: a) Draw a precedence graph for the following schedule. b) Determine if it is conflict-serializable based on the precedence graph. Transaction Time 1 2 3 4 5 6 7 8 9 10 11 12 Write(tax) Write(balance) Read(balance) Write(balance) Read(tax) Write(balance) Read(balance) Read(tax) Write(tax) Read(balance) Write(tax) Read(purchase) T1 T2 T3 T4

Solutions: a) Precedence graph: T1 goes before T3 T1 goes before T4 T2 goes before T1 T3 goes before T4 T4 goes before T1 T4 goes before T2

T1

T3

T2

T4

b) There is a cycle in the graph. Therefore, it is not conflict-serializable. Question 3: Consider the following sequence of actions, listed in the order the actions are presented to the DBMS. Assume that the concurrency control mechanism is Strict 2PL with timestamps used for “Wait-Die” (i.e., if Ti occurs before Tj, then Ti waits; otherwise Ti aborts). Describe how the concurrency control mechanism handles the sequence of actions. T1: R(X), T2: W(X), T2: W(Y), T3: W(Y), T1: W(Y), T1: Commit, T2: Commit, T3: Commit Assume that the timestamp of transaction Ti is i. Add appropriate lock and unlock requests to the sequence of actions. The DBMS processes actions in the order shown. If a transaction is blocked (waiting for a lock), assume that all of its actions are queued until it is resumed; the DBMS continues with the next action (according to the listed sequence) of an unblocked transaction. We assume that the DBMS doesn’t try to restart T2 until T1 commits. On an exam, you would be told what the abort policy was. For example, a different policy might be: don’t restart an aborted transaction until all the other transactions have finished. Solution: Wait-Die means: if Ti occurred before Tj, then Ti waits; otherwise Ti aborts. T1 gets shared lock on X T2 wants exclusive lock on X, but since T2 did not occur before T1, T2 aborts T3 gets exclusive lock on Y T1 wants exclusive lock on Y, T1 waits for T3 T3 commits & releases lock T1 gets exclusive lock on Y T1 commits & releases locks T2 restarts and gets exclusive locks on X and Y, commits & releases locks.

Question 4: Consider the following ordering S of transactions: T1: R(X), W(Y); T2: R(X), W(Y); T3: R(X), W(Y). How many schedules, if any, are conflict- equivalent to S? Solution: Recall that 2 actions conflict if they operate on the same object and at least one of them is a write. Two schedules are conflict-equivalent if they involve the same actions, and if they order every pair of conflicting actions in the same way. Here, Y is the problem; X is not a problem at all. Note that T1’s WRITE must go before T2’s WRITE, and T2’s WRITE must go before T3’s WRITE. The read for each transaction can go anywhere before that same transaction’s write. (Also, you cannot switch the ordering of reads and writes within the same transaction.) Having said all this, here is the solution: 1. There is only 1 possible location for T3’s WRITE. It must go last. This means that T3’s READ has a choice of 5 possible positions: ___ ___ ___ ___ ___ T3: W(Y) 2. After we place T3’s READ, this only leaves 4 empty spots. We have only no choice as to where to put T2’s WRITE. It MUST go in the last empty space of whichever spaces are currently left. That leaves 3 choices for placing T2’s READ. 3. Now, there are only 2 spots left. We have no choices. T1’s WRITE MUST go in the last empty spot, and T1’s READ goes in the other empty spot. This means that there are a total of 5 x 3 = 15 possible conflict-equivalent schedules.