Assignment
4
Consider a system
that uses LSN-based operation logging with fuzzy checkpoints and logging of
undo’s, as described in the lecture
slides and in Chapter 7 of the textbook. Assume that there is no analysis pass
before recovery (so there is no dirty page table in the checkpoint record), and
that CLR’s (i.e. undo records) are treated as normal updates and do not splice out a portion of the log (as
shown on lecture slide 33).
The following
sequence of records is found in a database log after a system failure. Data
values, such as before and after images, are omitted. The notation P1/r1 means
record r1 on page P1.
LSN Trans Operation
Type Page/Record Trans backpointer
8 T0 Update P0/r0 null
9 T1 Update P1/r1 null
10 T2 Update P2/r3 null
11 T2 Update P1/r2 10
12 T2 CLR P1/r2 11
13 T1 Update P2/r4 9
14 T2 CLR P2/r3 12
15 T3 Update P0/r5 null
16 checkpoint log record, Active
transactions: [T0, 8], [T1,13], [T2, 14], [T3, 15]
17 T0 Commit
18 T2 End
Abort
19 T1 Update P3/r6 13
20 T3 Update P3/r7 15
21 T3 CLR P3/r7 20
22 checkpoint log record, Active
transactions [T1,19], [T3, 21]
23 T4 Update P2/r3 null
24 T4 Update P0/r8 23
25 T1 Commit
Answer each of the
following. In each case, explain briefly why it’s the right answer.
a.
Show the
log records that must be written by the recovery process, in the proper order,
and briefly explain why they must be written. The new log records should have
LSNs numbered sequentially starting with 26.
b.
What LSN
is on each page after recovery?
c.
Based on
what is in the log, what is the smallest LSN of any log record that might have
to be redone?
d.
What
pages are fetched from disk by the recovery process?
e.
Does the
log give you enough information to tell whether record-level or page-level lock
granularity is being used? If so, which is it and how can you tell? If not,
explain why not.
f.
Suppose
LSN 23 were performed by T3 instead of T4. What does this tell you about the
execution of T3?
g.
It would
be unexpected (i.e., an error) for LSN 24 to update P0/r5. Why?
Now suppose we
modify the example so that it uses an analysis pass.
Each checkpoint
record now includes a dirty page table as follows:
·
In LSN
16, Dirty page table = [P0:8, P1:12, P2:13]
·
In LSN 22,
Dirty page table = [P3:19]
h.
At the
time of the second checkpoint, what LSN is on each page on disk?
i.
It would
be unexpected to find [P0:15] in the dirty page table of LSN 22. Why?
j. Which updates and CLRs may have to be redone?