Assignment 4


ReadingRead Chapter 7 of the textbook.


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?