Computer Science › Section J · Database systems › Topic J.5
Maintaining database integrity: transactions
A bank's database serves thousands of users at once and must survive power cuts mid-operation. Transactions, logs and locks are how a DBMS keeps its data correct regardless.
Why integrity is hard
If a small personal database, such as a list of recipes, goes wrong, its owner can fix a few entries or reload last week's backup. A bank, an airline or a university runs a database used by thousands of people at once, where lost or wrong data can cost real money and real harm. Two threats stand out. An operation may be only partly finished when a failure strikes, and two operations running at the same time may interfere with each other. Guarding against both, so that the database stays accurate, is one of the main jobs of a DBMS.
Transactions and ACID
A transaction is a group of database steps that must be treated as a single unit. Moving $200 from Ana's account to Ben's takes two steps, a debit and a credit, and between them $200 has briefly vanished. A DBMS gives transactions four guarantees, known as ACID. Atomicity: either every step happens or none does. Consistency: a transaction takes the database from one valid state to another, so rules such as "no negative balance" still hold. Isolation: transactions running at the same time do not see each other's half-finished work. Durability: once a transaction is committed, its changes survive any later crash.
The log and the commit point
To deliver atomicity and durability, the DBMS keeps a log on non-volatile storage, such as a disk or SSD. Before a transaction changes the database, the intended change is written to the log. The moment at which every step of a transaction has been recorded there is its commit point. From then on, the DBMS is committed: even if the machine fails before the database itself is fully updated, the log holds enough to finish the job. After a crash, the DBMS uses the log to redo the work of committed transactions and to undo, or roll back, the partial work of transactions that had not reached their commit point.
Rolling back
Rollbacks are not only for crashes; they are a normal part of running a DBMS. A transaction may be rolled back because one of its steps breaks a rule, because it tried to reach data it has no right to see, or because the DBMS chose it to break a deadlock. Rolling back can spread. If transaction T1 updated a balance and T2 then read that new value and acted on it, undoing T1 means T2 was built on a value that never officially existed, so T2 must be undone too, and so on: a cascading rollback. A simple defence is to keep other transactions from reading a change until the transaction that made it has committed.
Worked example: a transaction in SQLite
Table: Account(Id, Owner, Balance) with CHECK (Balance >= 0), holding Ana 500 and Ben 300. Steps: (1) BEGIN; then UPDATE Account SET Balance = Balance - 200 WHERE Id = 1; Inside the transaction the balances are 300 and 300, a total of 600: money is missing. (2) ROLLBACK; restores 500 and 300. (3) Repeat: BEGIN; the same debit, then UPDATE Account SET Balance = Balance + 200 WHERE Id = 2; then COMMIT; The balances are now 300 and 500, a total of 800 again. (4) Try BEGIN; UPDATE Account SET Balance = Balance - 600 WHERE Id = 1; The DBMS refuses with "CHECK constraint failed", and ROLLBACK; leaves 300 and 500. Standard SQL writes START TRANSACTION, which SQLite rejects; it uses BEGIN. From Python, connect with isolation_level=None so sqlite3 leaves BEGIN to you.
Interleaving transactions
Running transactions strictly one at a time would be safe but slow, because a transaction spends much of its time waiting for mass storage. Most large DBMSs therefore include a scheduler that interleaves the steps of several transactions, using one transaction's waiting time to advance another, much as an operating system interleaves processes (see "Coordinating the machine: processes and scheduling"). Uncontrolled interleaving causes two classic errors. In the lost update problem, two transactions read the same value, and the second write overwrites the first. In the incorrect summary problem, a transaction totalling balances reads some before and some after another transaction's changes.
Worked example: a lost update and a wrong total
An account holds $500. T1 withdraws $100 and T2 withdraws $150, so the correct result is $250. Steps: (1) T1 reads 500. (2) T2 reads 500 before T1 writes. (3) T1 writes 500 − 100 = 400. (4) T2 writes 500 − 150 = 350, overwriting T1's change. The final balance is $350: T1's withdrawal is lost, and the bank is $100 short. Had T2 written first, the result would be $400. Now the summary problem: Ana has $500 and Ben $300, a true total of $800. (5) A transfer debits Ana $200. (6) A report adds the balances: 300 + 300 = $600. (7) The transfer credits Ben. The report is $200 too low, though every balance it read was real.
Shared and exclusive locks
To prevent such clashes, the scheduler uses a locking protocol, marking items in use. A transaction that will only read an item asks for a shared lock; one that will change it asks for an exclusive lock. The rules: a shared lock is granted if the item is unlocked or has only shared locks, so many readers can proceed together. An exclusive lock requires the item to be completely unlocked; otherwise the request waits or is refused. In the lost update, T1's exclusive lock on the account forces T2 to wait until T1 finishes, so T2 reads 400 and writes 250. Locks are released when the transaction finishes with the item, commonly at commit.
Deadlock and the wound-wait protocol
Waiting for locks can cause deadlock: T1 holds an exclusive lock on account A and wants B, while T2 holds B and wants A, so neither can move. The conditions are those in "Competition among processes: semaphores and deadlock". Many DBMSs detect such cycles and roll back one victim. Another approach gives older transactions priority. Under the wound-wait protocol, each transaction keeps the timestamp of its first start. If an older transaction needs an item held by a younger one, the younger is wounded: rolled back via the log and restarted. If a younger one needs an item held by an older one, it waits. Waits only ever run young to old, so no cycle can form, and a restarted transaction keeps its timestamp, so it eventually becomes the oldest and finishes.
Common mistakes to avoid
Thinking a transaction is a single statement; it can bundle many steps into one unit. Believing committed means written to the main data files; it means fully recorded in the log, which is enough to finish the job. Assuming a rollback affects only one transaction; others that read its changes may need rolling back too. Granting an exclusive lock when shared locks are present; exclusive needs an unlocked item. In wound-wait, mixing up the directions: old wounds young, young waits for old.
Key takeaways
A transaction is a unit of work with the ACID guarantees: atomicity, consistency, isolation and durability. Changes are written to a log first; at the commit point the DBMS takes responsibility for finishing the transaction, and after a failure it redoes committed work and rolls back the rest. Rollbacks can cascade when others read uncommitted values. A scheduler interleaves transactions for speed, and shared and exclusive locks prevent lost updates and incorrect summaries. Deadlocks are broken by rolling back a victim, or avoided by wound-wait, where old wounds young and young waits for old.
Flashcards
Flashcard
A group of database steps treated as one unit
Test your understanding
Question 1 of 5
A balance is $800. T1 withdraws $200 and T2 withdraws $300. Both read $800 before either writes, then T1 writes and T2 writes. What is the final balance?
Question 2 of 5
An item already has two shared locks. What happens to a new request for an exclusive lock on it?
Question 3 of 5
The machine crashes. Transaction T had recorded all its steps in the log, but the data files were not yet fully updated. What does the DBMS do on restart?
Question 4 of 5
Under wound-wait, a younger transaction requests an item locked by an older one. What happens?
Question 5 of 5
Which ACID property is broken if a crash leaves a transfer's debit recorded but not its credit?
