ARIS solution

Q1. A transaction writes to a page with $PageLSN=500$. The log contains the following LSNs: $480$, $490$, $510$, $520$. Which log entries will be redone if a crash occurs?

• Concept: The redo phase reapplies log records to ensure updates are on disk. An update logged with LSN $L$ is redone on a page $P$ only if $L>PageLSN(P)$.
• Analysis:
  • LSN $480$: $480\ngtr 500$. Not redone.
  • LSN $490$: $490\ngtr 500$. Not redone.
  • LSN $510$: $510>500$. Redone.
  • LSN $520$: $520>500$. Redone.
• Answer: Log entries with LSNs $510$ and $520$ will be redone.

Q2. Consider a transaction $T1$ that made the following updates: - LSN $100$ → Page $A$ - LSN $120$ → Page $B$ - LSN $140$ → Page $C$ If $T1$ crashes before committing, what will be the sequence of undo operations?

• Concept: Undo proceeds backward through the transaction’s log records.
• Analysis: $T1$ is a “loser” transaction. The undo phase will process its updates in reverse order of their LSNs.
  1. Undo the action at LSN $140$ (Page $C$).
  2. Undo the action at LSN $120$ (Page $B$).
  3. Undo the action at LSN $100$ (Page $A$).
• Answer: The undo operations will be performed in the sequence corresponding to LSNs $140$, $120$, and $100$.

Q3. If a system takes a checkpoint every $100$ transactions and a crash occurs after $550$ transactions, how many transactions need to be analyzed during recovery?

• Concept: The analysis phase starts from the last complete checkpoint and scans to the end of the log to identify dirty pages and transactions that were active at the time of the crash.
• Analysis: The last checkpoint would likely have been taken around the completion of transaction $500$. The analysis phase needs to examine the log records generated since that checkpoint. This includes transactions $501$ through $550$.
• Answer: At least $50$ transactions ($T501$ to $T550$) need to be analyzed. Potentially more if some transactions started before $T501$ were still active during the checkpoint or at the time of the crash. However, based on the interval, $50$ is the most direct answer.

Q4. A system logs the following dirty pages at a checkpoint: - Page $A$ (first modified at LSN $300$) - Page $B$ (first modified at LSN $350$) If a crash occurs at LSN $450$, from which LSN should the redo phase start?

• Concept: The redo phase must start from the minimum $RecLSN$ (Recovery LSN, the LSN of the first log record that made the page dirty) of all pages listed in the Dirty Page Table (DPT) at the checkpoint.
• Analysis: The $RecLSN$s are $300$ (for Page $A$) and $350$ (for Page $B$). The minimum of these is $min(300,350)=300$.
• Answer: The redo phase should start from LSN $300$.

Q5. Each log record in ARIES takes $32$ bytes. If a transaction generates $500$ log records, how much space will it consume?

• Concept: Total space = Number of records × Size per record.
• Calculation: $500\text{ records}\times 32\text{ bytes/record}=16000\text{ bytes}$.
• Answer: It will consume $16000$ bytes (or $16$ KB) of log space.

Q6. A transaction $T2$ performs the following operations: 1. Writes Page $X$ at LSN $600$. 2. Writes Page $Y$ at LSN $650$. 3. Encounters an error and rolls back to LSN $600$. How is this handled in ARIES?

• Concept: During rollback (normal operation or recovery undo), ARIES writes Compensation Log Records (CLRs) for each undone action. CLRs are not undone themselves.
• Handling:
  1. $T2$ initiates rollback.
  2. It needs to undo the operation at LSN $650$ (Write Page $Y$).
  3. ARIES writes a CLR to the log. This CLR describes the undo action for LSN $650$, restores Page $Y$ to its previous state, and contains a pointer ($UndoNextLSN$) to the LSN of the previous update by $T2$ (which is related to LSN $600$, stored in the $PrevLSN$ field of the LSN $650$ record).
  4. The actual undo operation for Page $Y$ is performed.
  5. Since the rollback is specified to LSN $600$, the operation at LSN $600$ itself is not undone. The rollback process for $T2$ stops after undoing LSN $650$.
• Answer: ARIES writes a Compensation Log Record (CLR) describing the undo of the LSN $650$ update. The change to Page $Y$ is physically undone. The CLR ensures this undo operation won’t be repeated and points to the next LSN to consider for undo (related to LSN $600$), but since the rollback target was LSN $600$, the process stops.

Q7. A data page has $PageLSN=1000$. The log contains: - LSN $950$ (Update to Page $A$) - LSN $1050$ (Update to Page $A$) - LSN $1100$ (Update to Page $B$) Which entries will be redone?

• Concept: Redo applies log record $L$ to page $P$ if $L>PageLSN(P)$. This check is done for each update record encountered during the redo scan.
• Analysis: Assume Page $A$ has $PageLSN=1000$.
  • LSN $950$ (Page $A$): Is $950>1000$? No. This update will not be redone on Page $A$.
  • LSN $1050$ (Page $A$): Is $1050>1000$? Yes. This update will be redone on Page $A$. Page $A$‘s $PageLSN$ will then be set to $1050$.
  • LSN $1100$ (Page $B$): This affects Page $B$. It will be redone if LSN $1100>PageLSN(\text{Page }B)$. We don’t know Page $B$‘s $PageLSN$, but this log record is a candidate for redo during the redo phase scan.
• Answer: LSN $1050$ (Update to Page $A$) will definitely be redone based on the given $PageLSN$. LSN $1100$ (Update to Page $B$) will also be processed during redo and applied if $1100$ exceeds Page $B$‘s $PageLSN$ at that time. LSN $950$ will not be redone for Page $A$.

Q8. A system follows Write-Ahead Logging (WAL). If a transaction commits at LSN $700$, what is the latest LSN that must be written to disk before committing?

• Concept: The WAL principle requires that log records describing changes (including the commit record) must be written to stable storage (disk log) before the corresponding changes (or the commit acknowledgment) are finalized.
• Analysis: The commit record itself (LSN $700$) finalizes the transaction. According to WAL, this record and all preceding log records for the transaction must be persistent before the commit succeeds.
• Answer: LSN $700$ must be written to the stable log on disk before the commit is considered complete.

Q9. A parent transaction $T3$ spawns a nested transaction $T4$. The following LSNs are logged: - $T3$ starts (LSN $300$) - $T4$ starts (LSN $320$) - $T4$ writes Page $P$ (LSN $350$) - $T4$ commits (LSN $400$) - $T3$ crashes before committing What happens during recovery?

• Concept: In many nested transaction models (like ARIES), a nested transaction’s commit is relative to its parent. If the parent aborts, the nested transaction’s effects are also rolled back, even if it logged a ‘commit’.
• Analysis: $T3$ crashed, making it a loser transaction. Since $T4$ is nested within $T3$, its fate is tied to $T3$. Even though $T4$ logged a commit (LSN $400$), $T3$‘s crash means $T4$‘s effects must be undone.
• Recovery:
  1. Analysis phase identifies $T3$ as a loser.
  2. Redo phase might reapply $T4$‘s write (LSN $350$) if needed ( LSN $350>PageLSN(P)$ ).
  3. Undo phase processes $T3$ backward. It will encounter LSN $350$ ($T4$‘s write) and undo it because $T3$ is a loser. A CLR will be written for this undo action.
• Answer: $T3$ is identified as a loser. During the undo phase, the update made by the nested transaction $T4$ at LSN $350$ will be undone, despite $T4$ having a commit record (LSN $400$), because the parent transaction $T3$ aborted.

Q10. Consider two transactions, $T5$ and $T6$, with the following logs: - $T5$ updates Page $Q$ (LSN $800$) - $T6$ updates Page $R$ (LSN $850$) - $T5$ commits (LSN $900$) - $T6$ crashes before committing What will happen during the redo phase?

• Concept: The redo phase repeats history based on the log, starting from the calculated $RedoLSN$. It reapplies updates irrespective of whether the transaction ultimately committed or aborted.
• Analysis: The redo phase scans forward.
  • It encounters LSN $800$ ($T5$ update). It will redo this update on Page $Q$ if $800>PageLSN(Q)$.
  • It encounters LSN $850$ ($T6$ update). It will redo this update on Page $R$ if $850>PageLSN(R)$.
  • It encounters LSN $900$ ($T5$ commit). This marks $T5$ as committed but doesn’t involve a page update redo.
• Answer: During the redo phase, the updates for both $T5$ (at LSN $800$) and $T6$ (at LSN $850$) will be potentially reapplied, depending on the $PageLSN$ checks for Page $Q$ and Page $R$, respectively. The final status (committed/crashed) of the transactions does not affect the redo logic itself. (The effects of the crashed transaction $T6$ will be removed later during the undo phase).