Q9Data Base Management System

(a) Serializability of schedules

When multiple transactions execute concurrently, the DBMS interleaves their read and write operations to improve throughput, producing what is called a (non-serial) schedule. A schedule is said to be serializable if the net effect of executing it is guaranteed to be equivalent to the effect of running the same set of transactions one after another in some serial order (with no interleaving). Serializability is the gold-standard correctness criterion for concurrent execution, since any serial execution is trivially correct (each transaction sees a consistent state left by the previous one), and a serializable interleaved schedule inherits that same correctness while still allowing the performance benefits of concurrency.

The most practically useful and easily testable form is conflict serializability, which is based on the notion of conflicting operations: two operations from different transactions conflict if they access the same data item and at least one of them is a write. A schedule is conflict-serializable if it can be transformed into some serial schedule by successively swapping pairs of adjacent, non-conflicting operations, without changing the relative order of any conflicting pair. Conflict serializability is tested using a precedence graph (also called a serialization graph): a directed graph with one node per transaction, where an edge is drawn from Ti to Tj whenever Ti has an operation that conflicts with, and occurs before, a corresponding operation of Tj on the same data item. The schedule is conflict-serializable if and only if this precedence graph contains no cycle; if it is acyclic, a valid serial order equivalent to the schedule can be obtained by any topological sort of the graph.

As a worked example, consider two transactions: T1 reads and then writes data item X, and T2 also reads and then writes X, interleaved as: T1 reads X; T2 reads X; T1 writes X; T2 writes X. Since T1's write of X occurs before T2's write of X, and both are writes on the same item, we draw an edge T1 to T2 for the write-write conflict; also T1's read of X precedes T2's write of X (a read-write conflict), giving again T1 to T2. Since all conflicting pairs consistently point from T1 to T2 and there is no edge from T2 back to T1, the precedence graph is acyclic (a single edge T1 -> T2), so the schedule is conflict-serializable and equivalent to running T1 fully followed by T2. If, however, the schedule were instead T1 reads X; T2 writes X; T2 reads X (say a different item Y written earlier by T1); T1 writes Y, such that conflicts existed both from T1 to T2 and from T2 to T1 on different items, the precedence graph would contain a cycle T1 -> T2 -> T1, and the schedule would not be conflict-serializable, meaning it could produce a result inconsistent with any serial execution and would therefore need to be disallowed by the concurrency control manager.

(b) Recovery techniques and the role of the log

Database recovery techniques ensure that, after a system crash or transaction failure, the database can be restored to a consistent state in which the effects of all committed transactions are preserved (durability) and the effects of any uncommitted transactions are completely undone (atomicity). Almost all recovery techniques rely on a transaction log (or journal), a sequential, append-only file recording information about every update made to the database.

• Log record types: a typical log contains records such as [start, T], [write, T, X, old_value, new_value] (or just new_value for deferred update), [commit, T], and [abort, T], where T identifies the transaction and X the data item modified.
• Write-Ahead Logging (WAL) protocol: the fundamental rule that a log record describing a change to the database must be written to stable storage before the corresponding data change is written to the database on disk, ensuring that there is always enough information in the log to undo an update if the transaction that made it never commits.

Two broad classes of log-based recovery techniques exist, distinguished by when updates are actually applied to the database on disk.

• Deferred update (NO-UNDO/REDO) technique: updates made by a transaction are recorded in the log but are not applied to the actual database until the transaction commits; since the database on disk is never modified by an uncommitted transaction, no UNDO is ever needed on recovery - only REDO of the operations of transactions that committed but whose changes had not yet been flushed to disk at the time of the crash.
• Immediate update (UNDO/REDO) technique: updates may be written to the database on disk even before the transaction commits, so upon recovery both UNDO (to remove the effects of transactions that were active/uncommitted at the time of the crash) and REDO (to reapply the effects of transactions that had committed but whose updates might not have been physically flushed to disk yet) may be needed; the before-image and after-image of each write recorded in the log make both operations possible.
• Checkpointing: periodically, the DBMS writes a checkpoint record to the log (after forcing all log records and modified buffers up to that point to disk), which records exactly which transactions were active at that moment; on recovery, the system only needs to examine the log from the most recent checkpoint onward, rather than the entire log history, drastically reducing recovery time.
• Shadow paging: an alternative to logging that maintains two page tables - a current page table used during normal transaction execution, and a shadow page table that always points to the pages as they were at the last commit point; updates are made to new copies of pages, and only when the transaction commits is the current page table made the new shadow page table (an atomic pointer switch); if a crash occurs mid-transaction, the old shadow page table is simply used, automatically discarding uncommitted changes without needing UNDO.

As a concrete recovery example, suppose the log at crash time contains: [start,T1], [write,T1,X,10,20], [commit,T1], [start,T2], [write,T2,Y,5,15]. Since T1 has a commit record, its effect (X=20) must be REDONE if not already reflected on disk. Since T2 has no commit record at the point of the crash, its effect (Y changed from 5 to 15) must be UNDONE by restoring Y to its before-image value of 5, and T2 must eventually be resubmitted. This scan-log, REDO-committed, UNDO-uncommitted procedure, applied from the last checkpoint forward, is the essence of log-based crash recovery.