Consider the execution of the ARIES recovery algorithm given the following log:
ID: 3575287 • Letter: C
Question
Consider the execution of the ARIES recovery algorithm given the following log:
a) What is done during Analysis? Be precise about the points at which Analysis begins and ends and describe the contents of any tables constructed in this phase. What log records are read? What are the contents of the Dirty Page Table (DPT) and the transaction table at the end of the analysis stage?
b) What is done during REDO? Be precise about the points at which REDO begins and ends. What log records are read? What data pages are read? What operations are redone? (Assume no updates made it out to disk before the crash, except updates written to disk as part of a transaction commit.)
c) What is done during UNDO? Be precise about the points at which UNDO begins and ends. What log records are read? What operations are undone?
LSN Log Record 00 begin checkpoint 05 end checkpoint 10 Update: T2 writes P4 20 Update: T1 writes P3 30 Update: T3 writes P1 40 Update: T4 writes P3 50 T1 abort 60 CLR: Undo T1 LSN 20 70 Update: T2 writes P3 80 T2 commit 90 T1 end X crash, restartExplanation / Answer
a) The analysis of the above given data specifies that the last begin_checkpoint was at LSN 00 and starts at the corresponding end_checkpoint (LSN 05). The transaction Table records for the above given data re denoted as (transID, lastLSN, status) whereas the Dirty Page Table records are denoted as (pageID, recLSN) sets. Analysis phase runs till LSN 90 and does the following:
LSN 10 Adds (T2, 10, U) to TT and (P4,10) to DPT.
LSN 20 Adds (T1, 20, U) to TT and (P3,20) to DPT.
LSN 30 Adds (T3, 30, U) to TT and (P1,30) to DPT.
LSN 40 Adds (T4, 40, U) to TT and (P3,40) to DPT.
LSN 50 Changes (T1, 20, U) to (T1, 50, A).
LSN 60 Undo T1 LSN 60
LSN 70 Adds (T2,70,U) to TT and (P3,70) to DPT
LSN 80 Changes (T2, 70, U) to (T2, 80, C).
LSN 90 Deletes entry for T1 from Transaction Table
The final Transaction Table has three entries: (T2, 70, U) ,(T3, 30, U),(T4,40,U)
The final Dirty Page Table has three entries (P4,10) ,(P3,70),(P1,30) .
b) REDO
LSN 10 P4 is retrieved and its pageLSN is checked. If the page had been written to disk before the crash (i.e. if pageLSN >= 10), nothing is redone otherwise the changes are redone.
LSN 20 P3 is retrieved and its pageLSN is checked. If the page had been written to disk before the crash (i.e. if pageLSN >= 20), nothing is redone otherwise the changes are redone.
LSN 30 P1 is retrieved and its pageLSN is checked. If the page had been written to disk before the crash (i.e. if pageLSN >= 30), nothing is redone otherwise the changes are redone.
LSN 40 P3 is retrieved and its pageLSN is checked. If the page had been written to disk before the crash (i.e. if pageLSN >= 40), nothing is redone otherwise the changes are redone.
LSN 50 No action
LSN 60 No action
LSN 70 P3 is retrieved and its pageLSN is checked. If the page had been written to disk before the crash (i.e. if pageLSN >= 70), nothing is redone otherwise the changes are redone.
LSN 80 No action
LSN 90 No action
c) UNDO phase starts at LSN 90 (highest lastLSN in TT). The ToUndo consists of LSNs 90,30 and 40 for loser transactions T1,T3 and T4 respectively.