Database Management System: ACID Properties

Desirable Properties of Transactions

• Atomicity: a transaction is performed in its entirety or not at all
• Consistency preservation: takes database from one consistent state to another
• Isolation: not interfered with by other transactions
• Durability or permanency: changes must persist in the database

Transaction States

The Lost Update Problem

• If T1 transfers 5 seat reservations from X to Y and T2 reserves 4 seats on X, the final result should be X = 79, but in the interleaving of operations, X = 84 because the update in T1 that removed the five seats from X was lost

The Temporary Update Problem

The Incorrect Summary Problem

The Unrepeatable Read Problem

• Transaction T reads the same item twice, value is changed by another transaction T between the two reads, T receives different values for the two reads of the same item

Concurrency Control Based on Timestamp Ordering

• Strict Timestamp Ordering:
  • If TS(T) > read_TS(X), then delay T until the transaction T’ that wrote or read X has terminated
  • If TS(T) > write_TS(X), then delay T until the transaction T’ that wrote or read X has terminated
• Thomas’s Write Rule:
  • If read_TS(X) > TS(T) then abort and roll-back T and reject the operation
  • If write_TS(X) > TS(T), then just ignore the write operation and continue execution
  • Else, execute write_item(X) of T and set write_TS(X) to TS(T)

Guaranteeing Serializability by Two-Phase Locking

• Two-phase locking protocol:
  • Expanding (growing) phase: new locks can be acquired but none can be released, lock conversion upgrades must be done during this phase
  • Shrinking phase: existing locks can be released but none can be acquired, downgrades must be done during this phase
• The two phases must be mutually exclusive

Variations of Two-Phase Locking

• Basic 2PL: technique described above
• Conservative (static) 2PL: requires a transaction to lock all the items it accesses before the transaction begins
• Strict 2PL: transaction does not release exclusive locks until after it commits or aborts
• Rigorous 2PL: transaction does not release any locks until after it commits or aborts

Deadlock and Starvation

• Deadlock: occurs when each transaction T in a set is waiting for some item locked by some other transaction T’
• Starvation: occurs if a transaction cannot proceed for an indefinite period of time while other transactions continue normally
• Solution: first-come-first-served queue