The SuperSQL database system stores its undo log file in a table, with the follo

Question

The SuperSQL database system stores its undo log file in a table, with the following schema:

Log(N, T, E, V)

where N is the entry number (0, 1, 2, 3, ...), T is the transaction id, E is the element id, and V is the old value. A log entry of the form <T, E, V> is simply represented by the tuple (N, T, E, V), where N is the entry number and E>0 for an ordinary element id. The log entries <START T>, <COMMIT T>, and <ABORT T> are represented by a tuple (N, T, E, null), where E = -1 for START, E = -2 for COMMIT, and E = -3 for ABORT. For example, the log:

<START T1>
<T1, X1, 55>
<START T2>
<T2, X2, 99>
<COMMIT T1>
...........

is represented by the table:

Recall that each transaction starts and ends at most once; for example, a sequence <START T> ... <COMMIT T> ... <START T>... will not occur in the log. Moreover, any update by the transaction T will occur between its <START T> and <COMMIT T>, or between <START T> and <ABORT T> respectively. Finally, once a transaction has ended in COMMIT or ABORT and the corresponding log record is on disk, the transaction has completed and does not need to be undone.

Write a SQL query that can be run during database recovery, after a system crash. The answer to your query should return a table with two attributes, E, and V, indicating which elements have to be updated with what values. You should include each element E at most once in your answer: otherwise it would be ambiguous how to update it.

Explanation / Answer

First START CKPT: < START CKPT (T1, T2) >
Second START CKPT: < START CKPT (T2, T4) >

Since the second START CKTP does not have an associated END CKPT, we cannot be sure that
committed transactions prior to the start of this checkpoint had their changes written to disk.
Thus, we must search for the previous checkpoint. In the previous START CKPT, T1 and T2
were the two active transactions. Both transactions committed and must thus be redone. T1
was the first one to start. The recovery manager must thus read the log record starting from <
START T1 > and must read until the end of the log file.

Assuming that the two < START CKPT ??? > records are correctly stored in
the log, according to your answer above, show which elements are recovered by the redo recovery
manager and compute their values after recovery.

We must redo the changes made by all committed transactions there were either active during
the first START CKPT or that started after that point. T1 and T4 were active during the first
START CKPT and comitted. T3 and T4 started after the checkpoint but only T4 committed. We
must thus redo the changes by T1, T2, and T4. Elements N, T, E, V, and H are thus recovered.

Let us take the case where each log record is an update record of an uncommitted
transaction and each record belongs to a different transaction. This means there
are n records of n different transactions, each of which has to be undone. During
recovery, we have to add a CLR record of the undone action and an end transaction
record after each CLR. Thus, we can write a maximum of 2n log records before
restart completes.
The oldest begin checkpoint referenced in any fuzzy dump or master log record.
One needs to ensure that there is enough to hold twice as many records as the
current number of log records. If necessary, do a fuzzy dump to free up some log
records whenever the number of log records goes above one third of the available
space

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.