CSEP 544 Homework 4
Objectives
To understand query execution, recovery and concurrency control.
Reading Assignments
Chapters 16,17,18 from R&G and Chapter 18 from DS:CB.
Number of points:
100
Due Date
Wednesday, Nov 10, at 12:01 am. Submit a pdf file containing the answers via https://catalyst.uw.edu/collectit/dropbox/joyleung/11920.
Notes
Questions
  1. [15 points] After a system’s crash, the undo-log using non-quiescent checkpointing contains the following data:
    < START T1 >
    < T1, X1, 1 >
    < START CKPT ???? >
    < START T2 >
    < T2, X2, 2 >
    < T1, X1, 3 >
    < START T3 >
    < COMMIT T1 >
    < END CKPT >
    < START CKPT ???? >
    < T2, X2, 4 >
    < T3, X3, 5 >
    < START T4 >
    < COMMIT T2 >
    < T4, X4, 6 >
    < COMMIT T3 >
    < END CKPT >
    < START T5 >
    < T5, X5, 7 >
    < START CKPT ???? >
    < T4, X4, 8 >
    CRASH !!!
    1. What are the correct values of the three < START CKPT ???? > records ? You have to provide three correct values for the three “????”s.
    2. Assuming that the three < START CKPT ??? > records are correctly stored in the log, according to your answer at a., show which elements are recovered by the undo recovery manager and compute their values after recovery.
    3. Indicate what fragment of the log the recovery manager needs to read.
  2. [10 points] (Exercise 18.2.4 DS:CB) For each of the following schedules:

      a) r1(A); r2(A); r3(B); w1(A); r2(C); r2(B); w2(B); w1(C);
      b) r1(A); w1(B); r2(B); w2(C); r3(C); w3(A);
      d) r1(A); r2(A); w1(B); w2(B); r1(B); r2(B); w2(C); w1(D);
    Answer the following questions:

      i. What is the precedence graph for the schedule?
      ii. Is the schedule conflict-serializable? If so, what are all the equivalent serial schedules?
  3. [15 points] (Exercise 18.2.5 DS:CB) Say that a transaction T precedes a transaction U in a schedule S if every action of T precedes every action of U in S. Note that if T and U are the only transactions in S, then saying T precedes U is the same as saying that S is the serial schedule (T, U). However, if S involves transactions other than T and U, then S might not be serializable, and in fact, because of the effect of other transactions, S might not even be conflict-serializable. Give an example of a schedule S such that:

      i. In S, T1 precedes T2, and
      ii. S is conflict-serializable, but
      iii. In every serial schedule conflict-equivalent to S, T2 precedes T1.
  4. [15 points] (Exercise 18.8.1 DS:CB) Below are several sequences of events, including start events, where st1; means that transaction T1 starts. These sequences represent real time, and the timestamp scheduler will allocate timestamps to transactions in the order of their starts. Tell what happens as each executes.

      a) st1; st2; r1(A); r2(B); w2(A); w1(B);
      b) st1; r1(A); st2; w2(B); r2(A); w1(B);
      c) st1; st2; st3; r1(A); r2(B); w1(C); r3(B); r3(C); w2(B); w3(A);
      d) st1; st3; st2; r1(A); r2(B); w1(C); r3(B); r3(C); w2(B); w3(A);
  5. [15 points] (Exercise 18.9.1 DS:CB) In the following sequence of events, we use Ri(X); to mean "transaction Ti starts, and its read set is the list of database elements X." Also, Vi means "Ti attempts to validate," and Wi(X); means that "Ti finishes, and its write set was X." Tell what happens when each sequence is processed by a validation-based scheduler.

      a) R1(A, B); R2(B, C); V1; R3(C, D); V3; W1(A); V2; W2(A); W3(B);
      b) R1(A, B); R2(B, C); V1; R3(C, D); V3; W1(A); V2; W2(A); W3(D);
      c) R1(A, B); R2(B, C); V1; R3(C, D); V3; W1(C); V2; W2(A); W3(D);
  6. [15 points] R&G (pp. 574) Exercise 17.2
  7. [15 points] R&G (pp. 598)
    1. Exercise 18.4
    2. Exercise 18.5


File translated from TEX by TTH, version 3.89.
On 27 Oct 2010, 18:21.