11.10 Chapter Summary
Database recovery is the process of restoring the database to a correct state after a failure. Concurrency control is the ability to allow simultaneous use of the database without having users interfere with one another. Recovery procedures and concurrency control are used to protect the database and keep data in a consistent state.
A transaction is a logical unit of work that takes the database from one consistent state to another. Transactions can terminate successfully and commit or terminate unsuccessfully and be aborted. Aborted transactions must be undone or rolled back. Committed transactions cannot be rolled back.
Without concurrency control, problems such as the lost update problem, the uncommitted update problem, the inconsistent analysis problem, the nonrepeatable read problem, and the phantom data problem can arise. Serial execution means executing one transaction at a time, with no interleaving of operations. There will be more than one possible serial execution for two or more transactions, and they might not all produce the same results, but they are all considered correct. A schedule is used to show the timing of the operations of one or more transactions. A schedule is serializable if it produces the same results as if the transactions were performed serially in some order. A precedence graph shows the order of conflicting read and write operations in a schedule and proves conflict serializability if it has no cycles. It also shows possible equivalent serial ordering of transactions.
Two methods that guarantee serializability are locking and timestamping. Shared locks are sufficient if a transaction needs only read access, but exclusive locks are necessary for write access. A lock compatibility matrix shows which types of lock requests can be granted simultaneously. Transactions might be required to wait until locks are released before their lock requests can be granted. Because transactions can wait for locks, deadlock can occur. A deadlock is a situation in which two or more transactions wait for locks being held by one another to be released. Deadlock detection schemes use a wait-for graph to identify deadlock. A deadlock is resolved by choosing a victim, which is a transaction that will be made to fail. Starvation is a problem that arises when a transaction is made to wait an indeterminate amount of time for a lock it needs, while other overlapping transactions are granted their requested locks.
Two-phase locking is a widely used locking protocol. Every transaction acquires all locks in a growing phase before releasing any locks in the shrinking phase. Once the shrinking phase begins, no more new locks can be acquired. Variations to standard two-phase locking include strict and rigorous locking. Another variation allows transactions to begin by acquiring shared locks and upgrading them to exclusive locks just before a write. Upgrading can be done only during the growing phase. In the shrinking phase, a transaction can downgrade an exclusive lock to a shared lock. The purpose of this refinement is to maximize concurrent access. A tree can be used to represent the granularity of locks in a system that allows different-sized objects to be locked. When an object is locked, all its descendants in the tree are also locked. When a transaction requests a lock, an intention lock is placed on all the ancestors of any node being locked. Therefore, if a node does not have an intention lock, none of its descendants are locked. Serializability is ensured by using a two-phase locking protocol.
In a timestamping protocol, each transaction is given a timestamp, a unique identifier that gives the relative order of the transaction, and each data item has a Read-Timestamp and a WriteTimestamp. Problems arise when a transaction tries to read an item already updated by a younger transaction, or when a transaction tries to write an item whose value has already been read or updated by a later transaction. The protocol takes care of these problems by rolling back transactions that cannot execute correctly. If multiple versions of data items are kept, late reads can be done.
Optimistic techniques can be used in situations where conflicts are rare. Each transaction starts with a read phase, during which it reads all variables it needs, stores them as local variables, and writes to the local copy only. After the read phase, the transaction moves to a validation phase, during which the system determines whether there was any interference. If not and if the transaction is an update, it moves on to a write phase, during which the updates to the transaction’s local copy are applied to the database. If there was interference, the transaction is aborted instead of moving to the write phase.
To facilitate recovery, the system keeps a log containing transaction records that identify the start of transactions, give information about write operations, and identify the end of transactions. Using an incremental log with deferred updates, writes are done initially to the log only, and the log records are used to perform actual updates to the database. If the system fails, it examines the log to determine which transactions it needs to redo, namely those that committed but might not have been written to the database. There is no need to undo any writes. At a checkpoint, all modified pages in the database buffers are written to disk, all log records are written to disk, and a checkpoint record identifying all transactions active at that time is written to disk. If a failure occurs, the checkpoint records identify which transactions need to be redone. Using an incremental log with immediate updates, updates can be made to the database itself at any time after a log record for the update is written. The log can be used to undo as well as to redo transactions in the event of failure.
Shadow paging is a recovery technique that uses no logs. Instead, updates are made to a new copy of each page. A current page table points to the new page. A shadow page table continues to point to the old page until the transaction commits, at which time the current page table becomes the shadow page table. The ARIES recovery algorithm is a highly sensitive and flexible algorithm that does recovery by attempting to recreate the exact state the database was in at the time of failure, and then applying undo and redo operations as needed.
Oracle handles concurrency control by using a variety of locking and timestamping techniques, including multiversioning and logging but no read locks. It uses undo data segments for both concurrency and recovery. Transaction IDs are used to identify transactions, and system change numbers (SCNs) are used to identify and give the order of consistent states of the database. The Oracle recovery manager, RMAN, maintains control files, rollback segments, redo logs, and archived redo logs for recovery. Oracle Flashback technology can also be used for recovery.