Transaction Management

Transactions

• A transaction is a logical unit of work on the database.
• It transforms the database from one consistent state to another, although consistency may be violated during the transaction.

Example transactions (DreamHome)

read(staffNo = x, salary)
salary = salary * 1.1
write(staffNo = x, new_salary)

delete(staffNo = x)
for all PropertyForRent records, pno
begin
  read(propertyNo = pno, staffNo)
  if (staffNo = x) then
  begin
    staffNo = newStaffNo
    write(propertyNo = pno, staffNo)
  end
end

Transaction (b) touches many rows. If it fails half-way, some properties would point to a deleted staff member — the database would be inconsistent. Hence the need for transaction support.

Outcomes of a transaction

• Success → the transaction commits and the database reaches a new consistent state.
• Failure → the transaction aborts, and the database must be restored to the consistent state before it started. Such a transaction is rolled back (undone).
• A committed transaction cannot be aborted. If it was a mistake, a compensating transaction must be run to reverse its effects.
• An aborted transaction that is rolled back can be restarted later.

State transition diagram

ACID properties

Concurrency control

• Prevents interference when two or more users access the database concurrently and at least one is updating.
• Two transactions may each be correct on their own, but interleaving their operations may produce an incorrect result.

Three classic problems: Lost update Uncommitted dependency Inconsistent analysis

Lost update problem

A successfully completed update is overridden by another user.

T1 withdraws £10 from an account with bal_x = £100; T2 deposits £100 into the same account. Run serially, the final balance would be £190.

Both read £100. T2 writes £200, then T1 overwrites it with £90 — T2’s £100 deposit is lost.

Fix: prevent T1 from reading bal_x until after T2’s update is complete.

Uncommitted dependency (dirty read) problem

Occurs when one transaction can see intermediate results of another transaction before it has committed.

T4 updates bal_x to £200 but then aborts, so bal_x should return to £100. But T3 has already read the new value (£200) — dirty data — and uses it for its £10 reduction, giving £190 instead of £90.

Fix: prevent T3 from reading bal_x until after T4 commits or aborts.

Inconsistent analysis problem

Occurs when a transaction reads several values but a second transaction updates some of them during the execution of the first. Sometimes called a dirty read or unrepeatable read.

T6 totals balances x (£100), y (£50), z (£25) → correct total £175. Meanwhile T5 transfers £10 from bal_x to bal_z.

T6 read bal_x before the transfer (100) and bal_z after it (35), so the £10 is counted twice: result £185 — £10 too high.

Fix: prevent T6 from reading bal_x and bal_z until after T5 has completed its updates.

Serializability

• The objective of a concurrency control protocol is to schedule transactions so as to avoid interference.
• We could run transactions serially, but this limits the degree of concurrency/parallelism.
• Serializability identifies those executions of transactions guaranteed to ensure consistency.

The objective of serializability is to find nonserial schedules that allow transactions to execute concurrently without interfering — i.e. that produce the same result as some serial execution.

When does order matter?

1. If two transactions only read a data item → no conflict, order not important.
2. If two transactions read or write completely separate data items → no conflict, order not important.
3. If one transaction writes a data item and another reads or writes the same item → order is important (conflict).

Conflict serializability example

In S1 (nonserial), every conflicting pair (on bal_x and on bal_y) has T7 before T8 — the same order as the serial schedule S3. By swapping non-conflicting operations (e.g. T8’s bal_x ops with T7’s bal_y ops) S1 can be transformed into S2 and then S3. So S1 and S2 are conflict serializable.

Concurrency control techniques

• Two basic techniques: locking and timestamping.
• Both are conservative (pessimistic) approaches: they delay transactions in case they conflict.
• Optimistic methods assume conflict is rare and only check for conflicts at commit.

Locking

• A transaction uses locks to deny access to other transactions and so prevent incorrect updates.
• The most widely used approach to ensure serializability.
• A transaction must claim a shared (read) or exclusive (write) lock on a data item before reading or writing it.
• A lock prevents another transaction from modifying the item — or even reading it, in the case of a write lock.

Basic rules

• Shared lock (S) → can read but not update the item.
• Exclusive lock (X) → can read and update the item.
• Reads cannot conflict, so many transactions can hold shared locks on the same item simultaneously.
• An exclusive lock gives a transaction exclusive access to the item.
• Some systems allow upgrading a shared lock to exclusive, or downgrading exclusive to shared.

Lock compatibility matrix

Only S + S is compatible. Locks must be held for the duration of access.

Two-Phase Locking (2PL)

• Growing phase — acquires all locks but cannot release any.
• Shrinking phase — releases locks but cannot acquire new ones.
• Ensures serializability, but not freedom from deadlocks.
• May seriously reduce parallelism.

It can be proved that if every transaction in a schedule follows 2PL, the schedule is guaranteed to be conflict serializable.

Preventing lost update with 2PL

T2 obtains an exclusive lock first; T1’s lock request is not granted, so T1 waits until T2 commits and releases the lock.

Preventing uncommitted dependency with 2PL

T3 cannot read bal_x until T4’s rollback has completed and released the lock, so it reads the correct value (100).

Preventing inconsistent analysis with 2PL

T5 precedes its reads with exclusive locks; T6 precedes its reads with shared locks. When T5 starts it obtains X on bal_x; T6’s S-lock request on bal_x must WAIT until T5 commits and unlocks bal_x and bal_z. T6 then reads 90 + 50 + 35 = 175 ✓.

Deadlock

Database recovery

Need for recovery control

• Two types of storage: volatile (main memory) and non-volatile (disk).
• Volatile storage does not survive system crashes.
• Stable storage = information replicated on several non-volatile media.

Types of failure

• System crashes → loss of main memory
• Media failures → loss of parts of secondary storage
• Application software errors
• Natural physical disasters
• Carelessness or unintentional destruction of data/facilities

Transactions and recovery

• Transactions are the basic unit of recovery.
• The recovery manager is responsible for atomicity and durability.
• If failure occurs after commit but before the buffers are flushed to disk → to ensure durability the recovery manager must REDO (roll forward) the transaction’s updates.
• If the transaction had not committed at failure → to ensure atomicity it must UNDO (roll back) the transaction’s effects.
• Partial undo — only one transaction has to be undone. Global undo — all transactions have to be undone.

Example

A bar ending in | = committed. Orange = still active at the crash; blue = committed between the checkpoint and the crash.

The DBMS starts at t0 and fails at t_f. Assume data for T2 and T3 have been written to secondary storage.

Recovery facilities

The DBMS should provide:

• Backup mechanism — makes periodic backup copies of the database.
• Logging facilities — keep track of the current state of transactions and database changes.
• Checkpoint facility — enables updates in progress to be made permanent.
• Recovery manager — restores the database to a consistent state after a failure.

Log file

Contains information about all updates to the database: transaction records and checkpoint records. Often used for other purposes too (e.g. auditing).

Transaction records contain:

• Transaction identifier
• Type of log record (transaction start, insert, update, delete, abort, commit)
• Identifier of the data item affected (for insert, delete and update)
• Before-image of the data item (used for UNDO)
• After-image of the data item (used for REDO)
• Log management information (pointers to previous/next record of the same transaction)

Sample log file

Notice: an INSERT has only an after-image; a DELETE has only a before-image. The checkpoint record lists the transactions active at that moment (T2, T3).

Checkpointing

• A checkpoint record is created containing the identifiers of all active transactions.
• When failure occurs: redo all transactions that committed since the checkpoint, and undo all transactions active at the time of the crash.
• In the example with a checkpoint at t_c, changes by T2 and T3 are already on disk, so only redo T4 and T5, and undo T1 and T6.

Quick review