CS W186 Introduction to Database Systems
Spring 2020 Josh Hug, Michael Ball DIS 11
1 Recovery Q1
Consider the execution of the ARIES recovery algorithm given the following log (assume a check- point is completed before LSN 0 and the Dirty Page Table and Transaction Table for that check- point are empty):
(a) During Analysis, what log records are read? What are the contents of the transaction table and the dirty page table at the end of the analysis stage?
Solution: All records (since the last checkpoint) are read. We read through the log forwards
and add entries to the transaction table and the dirty page table. Note that lastLSN is the last LSN written by a transaction, while recLSN is the LSN which first caused a page to be dirty.
(b) During Redo, what log records are read? What data pages are read? What operations are redone (assuming no updates made it out to disk before the crash)?
Solution: Redo starts at LSN 10 (smallest recLSN in the dirty page table). All pages in the
dirty page table are read from disk (i.e. P1, P2, P3, P4). Assuming no updates made it to disk, the pageLSN of each page on disk is always less than the current LSN, so all updates and CLR¡¯s are redone. The LSN¡¯s of these operations are: 10, 20, 40, 50, 70.
(c) During Undo, what log records are read? What operations are undone? Show any new log CS W186, Spring 2020, DIS 11 1
records that are written for CLR¡¯s. Start at LSN 100. Be sure to show the undoNextLSN.
Solution: The lastLSN¡¯s in the transaction table are 80 and 70. Starting from here, we will read: 80, 70, 50, 40, 20. Of these, the update operations are: 70, 50, 40, 20. Therefore, the
new log records are:
CS W186, Spring 2020, DIS 11 2
2 Recovery Q2
Your database server has just crashed due to a power outage. You boot it up, find the following log and checkpoint information on disk, and begin the recovery process. Assume we use a STEAL/NO FORCE recovery policy.
(a) The log record at LSN 60 says that transaction 2 updated page 5. Was this update to page 5 successfully written to disk? The log record at LSN 70 says that transaction 1 updated page 2. Was this update to page 2 successfully written to disk?
Solution: The update at LSN 60 may have been written to disk. The log entry was flushed
before the write itself. It was not yet flushed at the time of the checkpoint, but may have been flushed later. The update at LSN 70 was flushed to disk. We know this because it¡¯s not in the dirty page table at the time of the checkpoint.
(b) At the end of the analysis phase, what transactions will be in the transaction table, and what pages will be in the dirty page table?
Solution: Note that P1 and P5 were already in the dirty page table during the checkpoint, and
their recLSN¡¯s do not change during analysis
CS W186, Spring 2020, DIS 11 3
(c) At which LSN in the log should redo begin? Which log records will be redone (list their LSNs)? All other log records will be skipped.
Solution: Redo should begin at LSN 40, the smallest of the recLSNs in the dirty page table.
The following log records should be redone: 40, 50, 60, 90, 110, 130, 160, 180. 30 is skipped because it precedes LSN 40. 70 is skipped because P2.recLSN = 160 > 70. Entries that are not updates are skipped. The CLR record is not skipped, nor is the LSN that it undoes.
CS W186, Spring 2020, DIS 11 4