Core CS · DBMS

Two hundred rupees, two writes, one promise

A transfer is two writes, and there is no correct state of the world in which only the first one happened. You will walk one transfer through all five transaction states, cut the power halfway, and watch the log put the money back.

Move 200 rupees, then cut the power →

The database is allowed to be wrong for the length of one transaction and not one instant longer. Every letter of ACID is a rule about the two ends of that stretch.

01 The idea

One unit of work, or none of it

Almost nothing useful is one write. Moving 200 rupees from account A to account B is a debit and a credit, and the two are only meaningful together. Between them the database holds a state that is arithmetically false: 200 rupees have left A and arrived nowhere. Every database has to pass through that state, because it has no way to change two rows at the same instant.

A transaction is how you tell the database that a group of reads and writes is one act. You open it, you do the work, and you end it with COMMIT or ROLLBACK. In exchange the database promises four things about that group, and those four promises are the letters of ACID. They are not four features bolted on to each other; they are four different answers to the same question, which is what a partly finished piece of work is allowed to do to everybody else.

Keep one pair of numbers in your head for the rest of this lesson. Account A holds 1,000 and account B holds 500, so A plus B is 1,500. That total is the invariant: a transfer moves money between the accounts, it never creates or destroys any. Halfway through the transfer the total reads 1,300. Everything in this lesson is about who is allowed to see that 1,300, and what happens if the machine dies while it is on screen.

A transaction is the only stretch of time in which the database will let the data be wrong. It ends in exactly one of two ways: every write took effect, or none of them did.

TransactionA group of reads and writes the database treats as one unit. It runs from BEGIN to either COMMIT or ROLLBACK, and there is no third ending.

InvariantA statement about the data that must be true whenever no transaction is in flight. Here it is A + B = 1,500. The database can only enforce the part of an invariant you wrote down as a constraint.

LogAn append-only file the database writes before it changes a data page. Each record holds the transaction id, the item, its old value and its new one, which is exactly what is needed to undo a change or to redo it.

02 Worked example

One transfer, five states

Here is the whole transfer written out the way a textbook writes it, with the balances after every operation. read and write are the transaction talking to the database; the assignment lines happen inside the transaction and touch nothing on disk.

-- T1 : move 200 from A to B      A = 1000   B = 500   A + B = 1500read(A)                          A = 1000A := A - 200                     A = 800    inside T1 only, nothing on diskwrite(A)                         A = 800    A + B = 1300   <-- broken, and legalread(B)                          B = 500B := B + 200                     B = 700    inside T1 only, nothing on diskwrite(B)                         B = 700    A + B = 1500   <-- repaired, not promisedCOMMIT                           A = 800    B = 700    A + B = 1500  promised

Line 4 is the interesting line, not line 8. After it the two accounts hold 800 and 500, which totals 1,300, and the bank is 200 rupees short. Line 7 repairs that: 800 and 700 total 1,500 again. But repaired is not the same as promised, and the five states below exist to keep those two ideas apart.

1 · ActiveBEGIN has run and lines 2 to 7 are executing. Every write already made has its old value sitting in the log.

→

2 · Partially committedthe last statement has finished. The balances are right, and they may exist only in memory. Nothing has been promised to anybody.

→

3 · Committedthe log and the commit record are on stable storage. COMMIT returns, and no crash can take the transfer back.

4 · Failedat any point before that: a constraint fired, a deadlock, a disk error, a power cut. No more work will be done.

→

5 · Abortedthe log is read backwards and every write of T1 is undone. A is 1,000 again and B is 500.

The strip runs left to right, so two arrows are missing from it and both are examinable. Active can go straight to failed, and so can partially committed. Those are the only two ways node 4 is ever reached, which is why nothing is drawn entering it. The dot between nodes 3 and 4 is not an arrow: committed never becomes failed. The table in the next section lists every legal move.

Node 2 is highlighted because it is the one students collapse into node 3. Between them sits a disk flush. The transaction has finished thinking, the new balances are correct, and none of that is worth anything yet: the changed pages may still be in the buffer pool in memory, the commit record may not have reached disk, and if the machine dies here the transfer did not happen. Partially committed is not a formality on the way to committed. It is a state with two exits.

Nodes 3 and 5 share one property: a transaction that reaches either of them is terminated. Terminated is not a sixth thing that happens to a transaction. It is the name for having stopped: no locks held, no row in the transaction table, nothing left to decide. You can start a new transaction that does the same work, but you cannot resume this one.

03 Mechanics

The five states, and the four letters

The exam question is never “name the states”. It is “from this state, where can it legally go, and who moves it”. Read the third column as the whole answer and the fourth as the follow-up.

State	What is true of the data	Legal next states	Who makes that move
Active	BEGIN has run and statements are executing. Every write already made has its old value in the log, so all of it is undoable.	`Partially committed, or Failed`	Your statements move it forward. A constraint, a deadlock victim notice, a ROLLBACK or a crash moves it sideways.
Partially committed	`the last statement has executed. The new values may exist only in the buffer pool, and no commit record has reached stable storage`	`Committed, or Failed`	The recovery manager, by forcing the log out to disk, or by failing to.
Committed	The transaction’s log records, including its commit record, are on stable storage. The change is permanent and visible to everybody.	`none, committed is an end state`	Nothing moves it anywhere. A committed transaction is terminated on arrival, and there is no arrow back to active, failed or aborted. That missing arrow is exactly what durability buys you.
Failed	`normal execution cannot continue. No further work will be done on behalf of this transaction`	`Aborted only`	Whatever detected the failure hands it to the recovery manager. You do not get a choice here.
Aborted	Every write this transaction made has been undone from the log. The database looks exactly as it did before BEGIN.	`none, aborted is an end state`	The recovery manager gets it here by applying the undo records backwards. Once it arrives, the transaction is terminated.
Terminated (a label, not a sixth state)	The name for having reached committed or aborted, so it is not a node you can draw an arrow into. It holds no locks and has no row in the transaction table.	`none, it is over`	Nothing, because nothing is left to move. The application may start a fresh transaction that does the same work. It cannot resume this one.

Two edges in that table are the ones interviewers probe. Partially committed to failed is the first, because candidates treat the last statement finishing as the finish line. Committed back to anywhere is the second, because there is no such edge: a committed transaction cannot be returned to active, failed or aborted, by you or by recovery. Everything else in this topic is one of those two edges with a different name on it.

Now the four promises, and who inside the database actually keeps each one. The third column is the version to give an interviewer, because it is the failure and not the definition.

Letter	The promise, stated precisely	What you would see without it, on our transfer	Who provides it
A · Atomicity	Every write of the transaction takes effect, or none of them does. There is no third outcome.	`A = 800 and B = 500 after the restart: 200 rupees left A and arrived nowhere, and A + B = 1300 where 1500 was`	The recovery manager. It puts the old value in the log before each write, and applies those records backwards on abort or restart.
C · Consistency	A transaction that starts from a valid database leaves a valid database. It says nothing at all about the middle.	`a transfer that debits 200 from A and credits 150 to B: atomic, durable, and 50 rupees short`	Shared. The DBMS enforces what you declared as NOT NULL, CHECK and FOREIGN KEY. You supply the rest, inside the transaction’s own logic.
I · Isolation	Running transactions concurrently produces a result equal to running the same transactions one after another in some order.	`another session sums the accounts while A is 800 and B is still 500, and reports 1300, a total the bank never held. Reading an uncommitted value like that is a dirty read, and READ UNCOMMITTED is exactly the level that permits it`	The concurrency-control manager. Two-phase locking or multiversion snapshots, exposed to you as isolation levels.
D · Durability	Once COMMIT has returned, the change survives a crash of the process, the operating system or the machine.	`COMMIT returns, the customer’s phone says the transfer is done, the power goes out, and after the restart it did not happen`	The recovery manager again, through write-ahead logging: the log and the commit record reach stable storage before COMMIT returns.

Write-ahead logging is two ordering rules, not one, and both of them are worth stating out loud. First: the log record describing a change must reach stable storage before the changed data page does. That is what makes undo possible, because if the page went out first and the machine died, nothing on disk would say what the old value had been. Second: all of a transaction’s log records, including its commit record, must reach stable storage before COMMIT returns to your application. That is what makes redo possible, and it is exactly the promise durability makes. The instant the second rule is satisfied is the commit point, and it is the line the whole lesson runs along.

Written in SQL the entire mechanism is four keywords. What you never write is the interesting part.

BEGIN;                                              -- state: ACTIVE  UPDATE account SET bal = bal - 200 WHERE id = 'A';   -- 1000 -> 800  UPDATE account SET bal = bal + 200 WHERE id = 'B';   --  500 -> 700COMMIT;                    -- PARTIALLY COMMITTED, flush, then COMMITTED -- anything at all goes wrong between lines 1 and 4:ROLLBACK;                  -- FAILED, then ABORTED. A is 1000 again, B is 500. -- the part of consistency the database can hold for you:ALTER TABLE account ADD CONSTRAINT bal_min CHECK (bal >= 0);-- the part it cannot: that the 200 you subtract is the 200 you add.

Line 4 is three states in one keyword: the transaction becomes partially committed when the last statement before it finished, the log is forced to disk, and only then is it committed and COMMIT allowed to return. Line 7 is the other branch, and notice you did not have to say what to undo: the log already knows, because line 2 wrote A was 1000 before it touched the page. Line 10 is the slice of consistency that can be declared once and is then tested on every write by every writer. Line 11 is the slice that cannot, and no database has ever solved it.

Three vendor differences worth one clause each, because interviewers use them to check whether you have typed this or only read it. BEGIN is START TRANSACTION in standard SQL and both work in PostgreSQL and MySQL, while Oracle has neither: a transaction there starts implicitly at your first executable SQL statement. DDL like line 10 commits implicitly in Oracle and MySQL, so it silently ends any transaction it lands inside, while PostgreSQL and SQL Server keep DDL inside the transaction, so on those two a schema change can be rolled back. And a CHECK is tested on the statement that writes the row rather than held back until COMMIT, which matters because it decides whether a violation aborts you at line 2 or at line 4; PostgreSQL, MySQL and SQL Server do not let you defer a CHECK at all, and Oracle does.

Two components, four letters. The recovery manager holds atomicity and durability, and it does both with one file: the log. The concurrency-control manager holds isolation, with locks or snapshots. Consistency is the only letter with your name on it, and it is the one interviewers use to find out whether you learned the acronym or the subject.

05 Cheat sheet

ACID on one card

Four rows. Column two is a sentence you can say in one breath, column three is what you name when they ask how, and column four is the follow-up that is coming whether you are ready for it or not.

Letter	Say this	Name this mechanism	The follow-up they ask
A · Atomicity	“All the writes happen or none of them do. There is no half.”	`the log: an undo record before every write, applied backwards on abort or restart`	“It was partially committed when the machine died. Is that safe?”
C · Consistency	“Valid before, valid after. It says nothing about the middle.”	`declared constraints for the part you can write down, the transaction’s own logic for the rest`	“So whose job is C, yours or the database’s?”
I · Isolation	“Concurrent transactions give the same result as some serial order of them.”	`two-phase locking or MVCC, exposed to you as isolation levels`	“What does a level below SERIALIZABLE actually let in?”
D · Durability	“Once COMMIT returns, a crash cannot take it back.”	`write-ahead logging: log and commit record on stable storage before COMMIT returns`	“Can you switch that off, and what do you get for it?”

The five states in one breathActive, then partially committed, then committed is the path where everything works. Active or partially committed, then failed, then aborted is the other one. Both endings are called terminated, which is a label for having stopped rather than a sixth state. Learn the two edges nobody expects: partially committed can still go to failed, and nothing at all leads back out of committed.

Consistency is the odd letter outAtomicity, isolation and durability are delivered by components you can point at and name. Consistency is shared: the database enforces the rules you wrote down as constraints, and the rest lives in your transaction’s own arithmetic. Say that before they ask, because the question is coming.

Write-ahead logging is two rulesOne, the log record for a change reaches stable storage before the changed data page does, which is what makes undo possible. Two, all of a transaction’s log records including its commit record reach stable storage before COMMIT returns, which is what makes redo possible. PostgreSQL calls that file the WAL, MySQL InnoDB the redo log, Oracle the redo log with undo kept separately.

06 Where & why

Where COMMIT actually costs you something

Durability is the only letter with a price tag you can read off a config file, and every serious engine gives you a knob for it. Knowing where those knobs are is the difference between a candidate who has read the four words and one who has watched a commit wait on a disk.

PostgreSQL

Where a commit is a disk flush, and where you can buy speed by giving that up

Every commit writes the transaction’s records and its commit record to the write-ahead log and flushes them before COMMIT returns. Setting synchronous_commit = off lets COMMIT return before that flush: atomicity, consistency and isolation are untouched, and you agree to lose the last fraction of a second of committed transactions if the machine dies. It is the clearest example anywhere of trading one letter for throughput on purpose. PostgreSQL also keeps DDL inside the transaction, so you can BEGIN, ALTER TABLE, and roll the schema change back. SQL Server allows that too; Oracle and MySQL commit the instant the DDL runs.

MySQL · InnoDB

The storage engine decides whether you have transactions at all

InnoDB gives you all four letters, with a redo log doing the job PostgreSQL’s WAL does. MyISAM, the old default, gives you none of them: no working ROLLBACK, no crash recovery of this kind, and BEGIN that buys you nothing. On InnoDB the durability knob is innodb_flush_log_at_trx_commit: 1 writes and flushes at every commit, 2 and 0 flush roughly once a second and trade durability for speed. Two traps to remember: DDL commits implicitly, so a CREATE TABLE inside your block ends the transaction, and the default isolation level is REPEATABLE READ where most other engines use READ COMMITTED.

Oracle

No BEGIN, and undo kept as a structure of its own

A transaction starts implicitly at your first executable SQL statement, which in day-to-day work means your first INSERT, UPDATE or DELETE; there is no BEGIN statement to type, and you end it with COMMIT or ROLLBACK. DDL commits implicitly here too. Oracle keeps undo data in dedicated undo tablespaces rather than mixing it into the redo log, which is how another session is served the pre-change version of a row instead of waiting behind your uncommitted write. SAVEPOINT lets you undo part of a transaction, and the levels on offer are READ COMMITTED, the default, and SERIALIZABLE. READ UNCOMMITTED is not on the menu.

SQLite

One file, no server, and the cost of durability made visible

SQLite keeps a rollback journal or a WAL file beside the database, so a transfer interrupted by a power cut is undone the next time the file is opened, with no server and no DBA anywhere. Its trap is autocommit: every statement you run outside an explicit BEGIN is its own transaction with its own flush to disk. That is why a loop of ten thousand inserts is painfully slow in SQLite and fast the moment you wrap the loop in one BEGIN and one COMMIT. You are not switching durability off there; you are asking for it ten thousand times fewer.

COMMIT is not punctuation at the end of your code. It is the one instant where the database stops being able to take back what you did, and all four letters are defined relative to it. If you can say where the commit point is and what the log holds on either side of it, most of this topic answers itself.

07 Interview questions

What they actually ask

Transactions come up in almost every DBMS interview, usually as “what is ACID” and almost always answered as four expanded words. The candidates who get through name the component behind each letter and can point at the exact instant the guarantee starts.

What is a transaction?

A group of reads and writes that the database treats as one unit of work: it either takes effect completely or not at all. In SQL it runs from BEGIN to either COMMIT or ROLLBACK, and there is no third ending. The reason for drawing the boundary at all is that the data is allowed to be inconsistent inside it and is not allowed to be inconsistent outside it.

Why is a bank transfer the standard example of one?

Because it is the smallest piece of work that takes two writes and still has to count as one act. Moving 200 rupees debits one row and credits another, and the invariant is arithmetic you can check in your head: A plus B was 1,500 and must still be 1,500. Every failure in this topic can be shown by stopping that transfer between the two writes, and every letter of ACID can be named on the state it leaves behind.

Walk me through the states a transaction goes through.

Active from BEGIN while the statements run. Partially committed once the last statement has executed but before the commit record is safely on disk. Committed once it is. If anything stops normal execution instead, the transaction goes to failed, and from failed the only move is aborted, which is reached by undoing every one of its writes from the log. A transaction that is committed or aborted is terminated: it holds no locks and has no slot in the transaction table.

A transaction is partially committed. Can it still fail?

Yes, and that is exactly why partially committed is a separate state rather than a synonym for committed. At that point the last statement has run and the answer is right in memory, but the commit record may not have reached stable storage, so the database has promised nothing to anybody. A failed flush, a power cut, or a constraint check that was deferred to the end of the transaction all move it straight from partially committed to failed, and from there it is undone like any other loser.

What is the commit point?

The instant the transaction’s log records, including its commit record, are known to be on stable storage. It matters because it is where the database stops being able to take the work back: one instant before it a crash means the transfer did not happen, one instant after it a crash means the transfer did happen and recovery will redo it if the data pages never made it out. COMMIT does not return to your application until that point has passed, which is why a commit costs a disk flush.

Atomicity and consistency sound like the same thing. Distinguish them.

Atomicity is about the set of writes; consistency is about the state they leave behind. A transfer that debits 200 from A and credits 150 to B is perfectly atomic, because both writes land together and survive a crash, and completely inconsistent, because 50 rupees vanished. No constraint you can declare would catch that, which is the other half of the answer: atomicity is entirely the database’s job and consistency is only partly its job.

Define isolation without using the word isolation.

Running a set of transactions at the same time must leave the same database as running that same set one after another in some order. Which order is not specified, and you do not get to choose it. The practical version is that no transaction should be able to observe another one’s half-finished work, so the moment where A is 800 and B is still 500 is not an answer anybody else can be given.

What is write-ahead logging, and which letters of ACID does it buy?

It is two rules about ordering, and it buys atomicity and durability. First, the log record describing a change must reach stable storage before the changed data page does, which is what makes undo possible: if the page went out first and the machine died, nothing on disk would say what the old value was. Second, all of a transaction’s log records including its commit record must reach stable storage before COMMIT returns, which is what makes redo possible and is precisely the promise durability makes.

Which part of the DBMS gives you which letter?

The recovery manager gives you atomicity and durability, and it does both with one file, the log: undo records for atomicity, the commit record and redo for durability. The concurrency-control manager gives you isolation, using two-phase locking or multiversion snapshots, and exposes it to you as isolation levels. Consistency is shared, because the database enforces the constraints you declared and you supply the rest inside the transaction.

Can you roll back a transaction that has already committed?

No, and the state diagram says why: there is no arrow out of committed. Once the commit record is on stable storage the database has promised, and that promise is what durability means, so it cannot be withdrawn by a later statement or by recovery. What you do instead is run a compensating transaction that makes the opposite change. That is not the same thing, because in between the two the wrong state was real and other sessions could read it.

Do I have to write BEGIN and COMMIT, or is it automatic?

Hard

A payments team commits far fewer transfers a second than it needs to, because every COMMIT waits on a disk flush. Three changes are proposed: (1) configure the engine to flush the log about once a second instead of at every commit; (2) group 500 transfers into one transaction instead of running 500 transactions; (3) drop from the default isolation level to READ UNCOMMITTED. For each one, name the letter of ACID it weakens, describe in a single sentence what a customer could observe because of it, and say which of the three you would put into production.

Follow-up

Two of the three weaken a letter and one weakens none of them, and the one that weakens none still carries a cost serious enough to decide whether you may use it. Name that cost, then say which two things get worse as you raise 500 to 5,000.

Show the hint

For each change, write out the sentence the bank would have to be willing to say to a customer out loud. Two of the three produce a sentence no bank will say.