| Database System Implementation
|
Solutions for Chapter 8
Solutions for Section 8.1
Solutions for Section 8.2
Solutions for Section 8.3
Solutions for Section 8.4
Solutions for Section 8.5
Return to Top
Solutions for Section 8.1
Exercise 8.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 8.2
Exercise 8.2.2(a)
There are five events of interest, which we shall call:
- A: database element A is written to disk.
- B: database element B is written to disk.
- LA: the log record for A is written to disk.
- LB: the log record for B is written to disk.
- C: the commit record is written to disk.
The undo rules imply the following constraints:
- C must be last.
- LA is before A.
- LB is before B.
- 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 8.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 8.2.6
One problem is that if, as in Exercise 8.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 8.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 8.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 8.3
Exercise 8.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 8.2.2(a), the legal sequences of events
are LA,LB,C,A,B and LA,LB,C,B,A.
Exercise 8.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 8.4
Exercise 8.4.2(a)
We shall use the notation developed for Exercise 8.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 8.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 8.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 8.5
Exercise 8.5.1(b)
Since the log is a redo log, and the dump completed before T_1
did, we know that no changes by that transaction can have reached disk.
Therefore, no changes by T_1 could be in the archive.
As for any recovery with a redo log, we ignore incomplete transactions,
so T_1 is made to abort and there is no need to perform any
changes to the database concerned with T_1.
Return to Top