Transaction Rollback and Restart Recovery - Transaction Processing - page 80

1. R EC -LSN .p/ M ODIFIED -LSN .p/ ,where M ODIFIED -LSN .p/ is the LSN of the log
record of the most recent update found on the log disk that turned p from an
unmodified page into a modified page.
2. If n is the LSN of an update on page p with n< R EC -LSN .p/ ,then n
P AGE -LSN .p/ ,where P AGE -LSN .p/ is the P AGE -LSN of the disk version of page
p at the time when the last log record found on the log disk was written.
3. The disk version of page p at the time of the failure contains all updates on that
page with LSN slessthan R EC -LSN .p/ .
Proof The active-transaction and modified-page tables are initialized from the
contents of the tables logged when taking the checkpoint, as is apparent from
Algorithm 4.13 . The log surviving on the log disk is then scanned forward.
Upon encountering a log record “n: h T; B i ,” the transaction record for a forward-
rolling transaction T with U NDO -N EXT -LSN D n is inserted into the active-
transaction table; upon encountering a log record “n: h T; A i ,” the state of T is
changed to “backward-rolling,” and upon encountering a log record “n: h T; C i ,”
the record for T is deleted. Thus the active-transaction table being reconstructed
indicates which transactions were forward-rolling or backward-rolling at any time
after the checkpoint was taken and until the last log record surviving on the log disk
was written.
Upon encountering a log record with LSN n for an update action by T or an undo
action by T on page p,the U NDO -N EXT -LSN value of T in the active-transaction
table is updated accordingly: the new value of U NDO -N EXT -LSN is the LSN n of the
redo-undo log record for a forward-rolling update action and the U NDO -N EXT -LSN n 0
of the redo-only log record for an undo action. Also, the entry .p; R EC -LSN D n/ is
inserted into the modified-page table if there is not yet any entry for p in the table.
Obviously, if upon encountering a log record for an update on page p there is no
entry for page p in the modified-page table being reconstructed, either page p was
not in the buffer at the time the checkpoint was taken or it resided there unmodified;
in any case the update encountered must be one that turned p from an unmodified
page into a modified one, so that R EC -LSN .p/ D M ODIFIED -LSN .p/ at that timepoint.
For pages p having an entry in the modified-page table logged at the checkpoint,
the associated R EC -LSN value is M ODIFIED -LSN .p/ current at the time of taking the
checkpoint if the entry was inserted into the table during normal processing, and, by
induction, less than or equal to M ODIFIED -LSN .p/ if the entry was inserted during an
analysis pass.
In any case, an entry .page-id; R EC -LSN / once inserted into the modified-page
table being reconstructed in the analysis pass is not changed or deleted during
the pass, because the analysis pass does not observe any flushings of pages from
the buffer onto disk that may have occurred during normal processing before the
failure. We conclude that condition (1) holds. By the definition of M ODIFIED -LSN ,
this in turn implies condition (2). By the definition of P AGE -LSN , this in turn implies
condition (3).

t