C H A P T E R 1 7

Recovery System

Solutions to Practice Exercises

17.1 • The recovery scheme using a log with deferred updates has the following
advantages over the recovery scheme with immediate updates:
a. The scheme is easier and simpler to implement since fewer operations
and routines are needed, i.e., no UNDO.
b. The scheme requires less overhead since no extra I/O operations need
to be done until commit time (log records can be kept in memory the
entire time).
c. Since the old values of data do not have to be present in the log-records,
this scheme requires less log storage space.
• The disadvantages of the deferred modification scheme are :
a. When a data item needs to accessed, the transaction can no longer di-
rectly read the correct page from the database buffer, because a previ-
ous write by the same transaction to the same data item may not have
been propagated to the database yet. It might have updated a local
copy of the data item and deferred the actual database modification.
Therefore finding the correct version of a data item becomes more ex-
pensive.
b. This scheme allows less concurrency than the recovery scheme with
immediate updates. This is because write-locks are held by transactions
till commit time.
c. For long transaction with many updates, the memory space occupied
by log records and local copies of data items may become too high.
17.2 The first phase of recovery is to undo the changes done by the failed transac-
tions, so that all data items which have been modified by them get back the

83
84 Chapter 17 Recovery System

values they had before the first of the failed transactions started. If several of
the failed transactions had modified the same data item, forward processing of
log-records for undo-list transactions would make the data item get the value
which it had before the last failed transaction to modify that data item started.
This is clearly wrong, and we can see that reverse prcessing gets us the desired
result.
The second phase of recovery is to redo the changes done by committed
transactons, so that all data items which have been modified by them are re-
stored to the value they had after the last of the committed transactions fin-
ished. It can be seen that only forward processing of log-records belonging to
redo-list transactions can guarantee this.

17.3 Interactive transactions are more difficult to recover from than batch transac-
tions because some actions may be irrevocable. For example, an output (write)
statement may have fired a missile, or caused a bank machine to give money to
a customer. The best way to deal with this is to try to do all output statements
at the end of the transaction. That way if the transaction aborts in the middle,
no harm will be have been done.

17.4 • Consider the a bank account A with balance $100. Consider two transac-
tions T1 and T2 each depositing $10 in the account. Thus the balance would
be $120 after both these transactions are executed. Let the transactions ex-
ecute in sequence: T1 first and then T2 . The log records corresponding to
the updates of A by transactions T1 and T2 would be < T1 , A, 100, 110 >
and < T2 , A, 110, 120 > resp.
Say, we wish to undo transaction T1 . The normal transaction undo mech-
anism will replaces the value in question — A in this example — by the old-
value field in the log record. Thus if we undo transaction T1 using the nor-
mal transaction undo mechanism the resulting balance would be $100 and
we would, in effect, undo both transactions, whereas we intend to undo
only transaction T1 .
• Let the erroneous transaction be Te .

Identify the latest checkpoint, say C, in the log before the log record
< Te , START>.

Redo all log records starting from the checkpoint C till the log record <
Te , COMMIT>. Some transaction — apart from transaction Te — would
be active at the commit time of transaction Te . Let S1 be the set of such
transactions.

Rollback Te and the transactions in the set S1 .

Scan the log further starting from the log record < Te , COMMIT> till
the end of the log. Note the transactions that were started after the
commit point of Te . Let the set of such transactions be S2 . Re-execute
the transactions in set S1 and S2 logically.
 Exercises 85

• Consider again an example from the first item. Let us assume that both
transactions are undone and the balance is reverted back to the original
value $100.
Now we wish to redo transaction T2 . If we redo the log record < T2 , A,
110, 120 > corresponding to transaction T2 the balance would become $120
and we would, in effect, redo both transactions, whereas we intend to redo
only transaction T2 .
17.5 This is implemented by using mprotect to initially turn off access to all pages,
for the process. When the process tries to access an address in a page, a pro-
tection violation occurs. The handler accociated with protection violation then
requests a write lock on the page, and after the lock is acquired, it writes the
initial contents (before-image) of the page to the log. It then uses mprotect
to allow write access to the page by the process, and finally allows the process
to continue. When the transaction is ready to commit, and before it releases
the lock on the page, it writes the contents of the page (after-image) to the log.
These before- and after- images can be used for recovery after a crash.
This scheme can be optimized to not write the whole page to log for undo
logging, provided the program pins the page in memory.
17.6 We can maintain the LSNs of such pages in an array in a separate disk page.
The LSN entry of a page on the disk is the sequence number of the latest log
record reflected on the disk. In the normal case, as the LSN of a page resides in
the page itself, the page and its LSN are in consistent state. But in the modified
scheme as the LSN of a page resides in a separate page it may not be written to
the disk at a time when the actual page is written and thus the two may not be
in consistent state.
If a page is written to the disk before its LSN is updated on the disk and the
system crashes then, during recovery, the page LSN read from the LSN array
from the disk is older than the sequence number of the log record reflected
to the disk. Thus some updates on the page will be redone unnecessarily but
this is fine as updates are idempotent. But if the page LSN is written to the
disk to before the actual page is written and the system crashes then some of
the updates to the page may be lost. The sequence number of the log record
corresponding to the latest update to the page that made to the disk is older
than the page LSN in the LSN array and all updates to the page between the
two LSNs are lost.
Thus the LSN of a page should be written to the disk only after the page
has been written and; we can ensure this as follows: before writing a page
containing the LSN array to the disk, we should flush the corresponding pages
to the disk. (We can maintain the page LSN at the time of the last flush of each
page in the buffer separately, and avoid flushing pages that have been flushed
already.)