Database Systems: The Complete Book
Solutions for Chapter 17

Solutions for Section 17.1
Solutions for Section 17.2
Solutions for Section 17.3
Solutions for Section 17.4
Solutions for Section 17.5

Solutions for Section 17.1

Exercise 17.1.1(a)

Let a and b be the initial values of A and B, respectively. The values of A and B at the end of these two steps are a+b and a+2b, respectively. Since we may assume 0 <= a <= b, it is easy to show 0 <= a+b <= a+2b. Thus, consistency is preserved.

Return to Top

Solutions for Section 17.2

Exercise 17.2.2(a)

There are five events of interest, which we shall call:

  1. A: database element A is written to disk.
  2. B: database element B is written to disk.
  3. LA: the log record for A is written to disk.
  4. LB: the log record for B is written to disk.
  5. C: the commit record is written to disk.

The undo rules imply the following constraints:

  1. C must be last.
  2. LA is before A.
  3. LB is before B.
  4. LA is before LB.
Note that (4) comes from the fact that we assume log records are written to disk in the order created.

We can conclude that LA is first; every other event must be preceded by something. Either A or LB can be next. In the first case, the only possible order of events is LA,A,LB,B,C. In the second case, A and B can then be written in either order, giving us the following two sequences: LA,LB,A,B,C and LA,LB,B,A,C, or a total of 3 possible sequences.

Exercise 17.2.4(b)

U is identified as committed, while T is not. Thus, T must be undone. Scanning the log backwards, we set C to 30 and A to 10. Then, we write an <ABORT> T record on the log.

Exercise 17.2.6

One problem is that if, as in Exercise 17.2.4(b), the crash occurs after U's commit record was preserved on the log, but before T's was, then as in Exercise 17.2.4(b), we set the value of A to 10. However, it appears as if T never ran, but U did. Thus, the value of A after crash recovery should be whatever U wrote.

As hinted at by the statement of the exercise, the reason things didn't go right can not be blamed directly on the undo logging rules. Rather, it was that T and U were both writing A at about the same time. Even had there been no crash, it is quite possible that the value of A after both transactions wrote would not reflect the actions of both.

Exercise 17.2.7(b)

T is the only active transaction, so the log record is <START CKPT(T)>. We can write the <END CKPT> record after the <COMMIT T> record. If the crash occurs after that time, we have to search back only to the <START CKPT(T)>. However, for crashes prior to the <COMMIT T> record, the search must continue back as far as the <START T> record, since that is the (lone) transaction that was active at the start of the checkpoint.

Return to Top

Solutions for Section 17.3

Exercise 17.3.2(a)

With redo logging, the writing of the elements A and B must occur after all log records are written. Thus, the only option is which element gets written first. Using the notation from Exercise 17.2.2(a), the legal sequences of events are LA,LB,C,A,B and LA,LB,C,B,A.

Exercise 17.3.3(b)

Since T is not complete, we can be sure that none of its changes reached disk, and we can ignore log records about T. On the other hand, U was committed, and its log record reached disk, so some of its changes may have reached disk. To be sure, we must redo all of the actions of U. Thus, we first set B to 20 and then set D to 40.

Return to Top

Solutions for Section 17.4

Exercise 17.4.2(a)

We shall use the notation developed for Exercise 17.2.2(a). The only constraints that undo/redo logging requires are that LA appears before A, and LB appears before B. Of course the log records must be written to disk in the order in which they appear in the log: LA,LB,C. The eight orders consistent with these constraints are: LA,A,LB,B,C, LA,A,LB,C,B, LA,LB,A,B,C, LA,LB,A,C,B, LA,LB,B,A,C, LA,LB,C,A,B, LA,LB,B,C,A, and LA,LB,C,B,A.

To check that we have all possible orders, start with the fixed sequence LA,LB,C. The action B can be placed either before or after the C (two choices). Whichever choice we make for B, we can place A in any of four positions, from immediately after LA to the right end. Thus, there are 2*4 = 8 legal orders.

Exercise 17.4.3(b)

Since U is committed, we redo its actions, setting B to 21 and D to 41. Then, since T is uncommitted, we undo its actions from the end moving backwards; we set C to 30 and A to 10.

Exercise 17.4.5(b)

i. The END CKPT record could appear anywhere after the record <T,A,61,62>. The reason is that the writing of dirty blocks can be performed independent of whatever actions the transactions are performing in the interrum.

ii. The only active transaction when the checkpoint began was T. If the crash occurs after the END CKPT, then we need only go back as far as the start of T. However, if the crash occurs before the checkpoint ended, then any transaction that was active when the previous checkpoint ended may have written some but not all of its data to disk. In this case, the only other transaction that could qualify is S, so we must look back to the beginning of S, i.e., to the beginning of the log in this simple example.

Return to Top

Solutions for Section 17.5

Exercise 17.5.1(b)

Since the log is a redo log, and the dump completed before T1 did, we know that no changes by that transaction can have reached disk. Therefore, no changes by T1 could be in the archive. As for any recovery with a redo log, we ignore incomplete transactions, so T1 is made to abort and there is no need to perform any changes to the database concerned with T1.

Return to Top