CPS 432/562 Homework #4 Solution Sketches

1. (5*4=20 points) Consider the following two transactions:
   
   
   
   • Transaction 1: TransferBalance
     READ(A,x);
     x = x-50;
     WRITE(A,x);
     READ(B,y);
     y = y+50;
     WRITE(B,y);
     
     
   • Transaction 2: ReportSum
     
     READ(A,x);
     READ(B,y);
     print x+y;
   
   For the following items, take into account all operations, even those like x=x-50 and print x+y. Count the number of:
   
   
   1. interleavings of the above two schedules (all combinations):
      9C3 = 9C6 = 84
   2. serial schedules:
      obviously 2
   3. serializable schedules (provide and explain a good consistency constraint)
      This is slightly tricky. First we need to settle on a good consistency constraint. If all we wanted to do was preserve that database state (i.e., the A and B data elements as modified by some serial schedule), then ReportSum could be interleaved with TransferBalance in any order, since ReportSum does not perform any writes or modifications. A reasonable constraint would be to expect that, in addition, the value printed by ReportSum is the same (irrespective of even whether TransferBalance executes or not).
      
      Let us consider TransferBalance followed by ReportSum and then ReportSum followed by TransferBalance in turn:
      1. TransferBalance followed by ReportSum: The READ(A,x) of ReportSum could be moved as far back as just after WRITE(A,x) of TransferBalance which is 4 choices (including its current position). However, the two other actions of ReportSum do not have any move degrees of freedom. Thus, the number of serializable schedules equivalent to this serial schedule is 4.
      2. ReportSum followed by TransferBalance: This time, let us shift the actions of ReportSum since there are less in number. The following is a calculation tree:
         • READ(A,x) of ReportSum occurs immediately before READ(A,x) of TransferBalance: 27 combinations
           • READ(B,y) and print x+y of ReportSum both appear before WRITE(B,y) of TransferBalance: 21 (=7C2) combinations (why 7, instead of 6?; because there are two operations to be interleaved)
           • READ(B,y) of ReportSum occurs before WRITE(B,y) of TransferBalance, but print x+y occurs after: 6 combinations (the 6 positions in which the READ(B,y) of ReportSum could be placed)
         • READ(A,x) of ReportSum occurs immediately before x = x-50 of TransferBalance: 20 combinations
           • READ(B,y) and print x+y of ReportSum both appear before WRITE(B,y) of TransferBalance: 15 (=6C2) combinations
           • READ(B,y) of ReportSum occurs before WRITE(B,y) of TransferBalance, but print x+y occurs after: 5 combinations
         • READ(A,x) of ReportSum occurs immediately before WRITE(A,x) of TransferBalance: 14 combinations
           • READ(B,y) and print x+y of ReportSum both appear before WRITE(B,y) of TransferBalance: 10 (=5C2) combinations
           • READ(B,y) of ReportSum occurs before WRITE(B,y) of TransferBalance, but print x+y occurs after: 4 combinations
      Final answer: the golden age of retirement, 65 schedules, ..., whew, that was rough, now we are ready to retire :-)
   4. conflict-serializable schedules
      The number of conflict-serializable schedules among all of the serializable schedules is 65 (all of them). Notice that any one of the serializable schedules, by virtue of the way we constructed them, will lead to a serial schedule by a sequence of non-conflicting swaps.
   
   
2. (10+10=20 points) Consider the following two transactions:
   
   T1: r₁(A) r₁(B) inc₁(A) inc₁(B)
   T2: r₂(A) r₂(B) inc₂(A) inc₂(B)
   
   where inc₁(A) refers to an increment of A by transaction 1 and so on. Notice that the quantity of the increment is unknown. For example, inc₁(A) could mean `increment by 1,' `increment by 10,' `increment by B,' or something else. In other words, you cannot assume anything.
   
   
   1. How many interleavings of these transactions are conflict-serializable?
      One and only one non-conflicting swap is permitted in each of the serial schedules. Number of conflict-serializable schedules: 4 (= 2*(1+1)).
   2. If the order of the increments in T2 are reversed, how many interleavings are conflict-serializable?
      Three.
   
   
3. (5+5=10 points) Exercise 18.4.5 on p. 950 from [DBCB]: The action of multiplication by a constant factor can be modeled by an action of its own. Suppose MC(X,c) represents an atomic execution of the steps READ(X,t) t:=t*c WRITE(X,t). We can also introduce a lock mode that allows only multiplication by a constant factor.
   
   
   1. Show the compatibility matrix for read, write, and multiplication-by-a-constant locks.

      	Lock requested
      Lock held	S X M S yes no no X no no no M no no yes

   2. Show the compatibility matrix for read, write, incrementation, and multiplication-by-a-constant locks.

      	Lock requested
      Lock held	S X I M S yes no no no X no no no no I no no yes no M no no no yes

      Addition and multiplication do not commute with each other.
   
   
4. (10 points) Required only for CPS 562 students
   Exercise 18.3.4 (part b) on p. 940 from [DBCB]: Consider the following transaction:
   
   r₂(A) w₂(A) w₂(B)
   Suppose that we insert one lock and one unlock action for each database element this is accessed. Indicate how many orders of the lock, unlock, read, write actions are:
   
   
   1. consistent and two-phase locked
   2. consistent, but not two-phase locked
   3. inconsistent, but two-phase locked
   4. neither consistent nor two-phase locked
   
   (courtesy [DBCB] webpage)
   Notice that we can simplify this problem by computing the number of the various types of orders in strategic ways. First let us count the number of consistent orders. To be consistent, each read and write must have a lock to the left and an unlock to the right. Thus, the only consistent sequences are the interleavings of the two sequences
   
   
   1. l₂(A) r₂(A) w₂(A) u₂(A)
   2. l₂(B) w₂(B) u₂(B)
   
   The number of these interleavings is 35 (= 7C3 = 7C4). However, the number of consistent orders is double this number because we can permute the read and write of A in the first interleaving. Thus, the number of consistent orders (or the sum of the first two quantities we must compute) is 70.
   
   Now, let us determine how many of these are non-two-phase-locked sequences. The only way a consistent sequence is not 2PL is if the unlock at the end of subsequence (1) or (2) above precedes the lock at the beginning of the other subsequence. There are only 2 ways to interleave (1) and (2) so that all of one goes in front of all of the other (put either subsequence first). However, again, we can permute the read and write of A in the first interleaving. Thus the number of consistent, non-two-phase-locked orders is 4 (=2*2). Thus, (ii) = 4, so (i) = 66 (=70-4).
   
   Now, let us count the number of two-phase-locked orders, which is (i) + (iii). If the order is 2PL, then the two locks precede the two unlocks. We can thus pick one of two orders for the locks and one of two orders for the unlocks, for a total of 4 orders of the lock and unlock actions. The r₂(A) action can go anywhere. That is, we can choose any of 5 positions in which to insert the read action among the lock and unlock actions, ranging from before all to after all. Having placed the read action, the w₂(A) action can now be placed in any of 6 positions among the other 5 actions. Lastly, the w₂(B) action can now be placed in any of 7 positions among the other 6 actions. The total number of 2PL sequences is thus 4*5*6*7 = 840.
   
   Since (i) + (iii) = 840 and we already know (i) = 66, we deduce that (iii) = 774.
   
   The last step is to compute the total number of sequences, which is the sum of all four categories. The number of sequences of six actions is 7! = 5,040. As the number of sequences in the first three categories is 66, 4, and 774, respectively, (iv) = 4,196 (=5,040-66-4-774).
   
   Thus, in summary, the final answers are
   
   
   1. consistent and two-phase locked: 66
   2. consistent, but not two-phase locked: 4
   3. inconsistent, but two-phase locked: 774
   4. neither consistent nor two-phase locked: 4,196