Transaction States and Atomic Execution

A transaction is a unit of work: a sequence of read and write operations bracketed by an implicit or explicit `begin` and terminated by `commit` or `rollback`. The transaction state is a label maintained by the Transaction Manager that records how far a given transaction has progressed toward finishing, and what recovery obligations apply to it right now. Precisely because failures (crashes, deadlocks, constraint violations, disk errors) can strike at any instant, the database cannot simply "run the code" — it must track, at every moment, whether the transaction's partial effects are safe to keep, must be undone, or must eventually be redone. The five states are defined as follows.

• Active: the initial state; the transaction stays here while it is executing statements (reads and writes to the buffer/cache, not yet finalized to stable storage as a unit).
• Partially committed: entered immediately after the final statement executes. The transaction believes it is done, but the system has not yet confirmed that all effects are safely and durably recorded. This is the shortest-lived and most dangerous state — a crash here is exactly the scenario atomicity exists to handle.
• Committed: entered after the system confirms that all updates have been durably recorded (typically once a commit log record is flushed to stable storage). Once committed, the transaction's effects are permanent, satisfying the durability property, and cannot be rolled back.
• Failed: entered when the system discovers that normal execution can no longer proceed — a hardware error, a violated constraint, a deadlock the scheduler chose to break, or an explicit abort request.
• Aborted: entered after the system has rolled back the transaction — undone every effect it had made — restoring the database to its state before the transaction began.

The crucial structural fact is that committed and aborted are the only two states with no outgoing transitions: they are terminal. Every transaction, no matter how it started or what went wrong along the way, ends in exactly one of these two states. That guarantee — not any single piece of code — is atomicity. It is also tightly linked to the other ACID properties: durability is what "committed" certifies, and consistency is what the application logic and constraints are trusted to preserve on the committed path, while atomicity is enforced purely by this state machine plus the recovery mechanism that implements it.

The transaction manager is the component responsible for driving these transitions. It does not run application logic itself; it wraps the execution of read/write operations with bookkeeping and, critically, writes log records describing state transitions to the Write-Ahead Log before it lets those transitions take effect on the actual database. This "log first" discipline (the write-ahead logging rule) is what makes it possible to recover the correct state after a crash, and it is introduced lightly here because it is developed fully in Log-Based Crash Recovery. The state transition graph has exactly these directed edges: ``` active -> partially committed (on executing the final operation) active -> failed (on detecting an error / cannot continue) partially committed -> committed (on successful, durable completion of commit) partially committed -> failed (on system failure before commit record is durable) failed -> aborted (after rollback finishes) ``` No edge leads out of committed or aborted. No edge skips from active directly to committed — every transaction must pass through partially committed, even if that stay lasts microseconds. This forced intermediate step exists because "the application finished issuing statements" and "the system has durably recorded the outcome" are logically distinct events, separated by disk I/O and possibly a crash window.

Pseudocode: driving the transaction lifecycle

The following pseudocode models a transaction manager's handling of one transaction, `T`, showing exactly where each transition occurs and what log record accompanies it. ``` State(T) := ACTIVE write_log("start", T.id) function EXECUTE(T): while T has more operations: op := next operation of T try: if op is a write: buffer_update(op) // update goes to buffer/cache write_log("update", T.id, op.before, op.after) else if op is a read: perform_read(op) catch error: State(T) := FAILED ROLLBACK(T) return ABORTED // last statement has just executed successfully State(T) := PARTIALLY_COMMITTED return COMMIT_ATTEMPT(T)

function COMMIT_ATTEMPT(T): try: force_write_log("commit", T.id) // MUST be durable before declaring success catch io_error: State(T) := FAILED ROLLBACK(T) return ABORTED State(T) := COMMITTED flush_remaining_buffers_lazily(T) // may happen before or after, doesn't affect atomicity return COMMITTED

function ROLLBACK(T): // State(T) is FAILED when this begins for each ("update", T.id, before, after) in reverse(log entries of T): restore(before) // undo using the before-image write_log("abort", T.id) State(T) := ABORTED return ABORTED

function REQUEST_ABORT(T): // e.g., called by deadlock detector or user if State(T) == ACTIVE or State(T) == PARTIALLY_COMMITTED: State(T) := FAILED ROLLBACK(T) ``` Two details matter and are easy to miss. First, the commit log record must be forced to stable storage (`force_write_log`, i.e., an actual disk/flash flush, not just a buffer write) before the state is set to `COMMITTED` and before the transaction manager reports success to the caller. This ordering is what lets recovery, after a crash, distinguish "this transaction's commit record made it to disk, so redo its effects" from "it didn't, so undo them." Second, `ROLLBACK` always uses before-images captured at write time — this is only possible because the write-ahead log recorded the pre-update value before the update was applied to the buffer, foreshadowing the undo/redo logging discussed in Log-Based Crash Recovery.

Time complexity. State transitions themselves are $O(1)$ label updates. The real cost is proportional to the work each transition triggers. Executing a transaction with $n$ operations costs $O(n)$ for the operations plus $O(1)$ amortized log writes per operation, so the active phase is $O(n)$. The transition into committed costs $O(1)$ for the commit record plus one forced I/O (a constant-time but relatively expensive disk flush, independent of $n$). The transition through failed → aborted costs $O(k)$, where $k$ is the number of update log records written by this transaction so far, since rollback walks the log backward and undoes each one. In the worst case $k = n$, so an abort late in a long transaction costs the same order as the work already done — this is the honest price of atomicity: undoing must touch everything that was done.

Space complexity. The transaction manager needs $O(1)$ space to store the current state label per active transaction, plus $O(n)$ space in the log for the update records of a transaction with $n$ writes (necessary so rollback has something to undo from). Systems bound this in practice with log truncation and checkpointing once a transaction commits, which is part of what Log-Based Crash Recovery covers.

Correctness argument. The claim to prove is: no execution can leave the database in a state that reflects only some of a transaction's writes, once the transaction manager reports a final outcome. The proof rests on three invariants maintained by the state machine and its pseudocode: 1. Single-terminal-state invariant. Every transaction's `State(T)` sequence, read as a path in the transition graph, ends at `COMMITTED` or `ABORTED`, and once there, no code path assigns a different value (inspect the pseudocode: only `COMMIT_ATTEMPT` sets `COMMITTED`, only `ROLLBACK` sets `ABORTED`, and neither calls the other). This rules out a transaction being reported as both, or neither, forever. 2. Durability-precedes-report invariant. `State(T)` is set to `COMMITTED` only after `force_write_log("commit", …)` returns successfully. Because this is a synchronous, blocking call in the pseudocode, no external observer can see a commit acknowledgment before the commit record is durable. Consequently, if the system crashes at any point before this call finishes, the commit record is not on stable storage, `State(T)` was never set to `COMMITTED`, and the recovery procedure (run at restart) is entitled to treat `T` as if it never finished — it undoes `T`'s updates using the same before-images, producing exactly the outcome `ROLLBACK` would have produced had the crash not occurred but the failure detector fired instead. This is precisely why partially committed is modeled as a distinct, separate state from committed: it is the window during which this race exists, and the invariant says the observable outcome is well-defined regardless of exactly when in that window the crash lands. 3. Undo completeness invariant. `ROLLBACK` iterates over every update log record for `T`, in reverse order, before setting `State(T) := ABORTED`. By induction on the number of updates undone, after processing all of them the database's state for every item `T` touched equals its pre-transaction value. The base case (zero updates) is trivial; the inductive step holds because each undo step restores exactly the before-image recorded at write time, and updates from other concurrently running transactions are assumed (via concurrency control, developed in Serializability and Schedules) not to have overwritten `T`'s items in a way that invalidates the before-image — a guarantee provided by locking or another concurrency-control protocol, not by the state machine itself. Together these invariants establish atomicity: the observable end state of any transaction, under any interleaving of failures, is exactly "all its writes are visible and durable" or exactly "none of its writes are visible," with the transition point unambiguously marked by the durability of the commit record.

Honest tradeoffs. Forcing the commit log record to disk is a genuine latency cost — it is the reason systems batch commits ("group commit") to amortize the flush over many transactions. Rollback cost being proportional to work done means long-running transactions that abort late are expensive to undo; this motivates keeping transactions short. The model also assumes a competent concurrency-control layer underneath; the state machine alone does not prevent one transaction's rollback from being invalidated by another transaction reading or overwriting its uncommitted data — that is the job of isolation, covered separately.

Consider transaction `T1`, a funds transfer: debit account `A` by 50, credit account `B` by 50, both initially holding 100.

Now trace the failure branch: suppose the system crashes at step 7, immediately after the last statement but before the commit record is forced (i.e., while `State(T1)` is still partially committed). On restart, the recovery procedure scans the log, finds `` and two update records but no `` record. By the durability-precedes-report invariant, `T1` must be treated as never having successfully finished. Recovery undoes `T1`: it applies the before-images in reverse — restore `B` to 100, then restore `A` to 100 — and (conceptually) transitions `T1` to failed then aborted. The final disk state is A=100, B=100, exactly as if `T1` had never run. No partial transfer (money debited from `A` but never credited to `B`) is ever observable, which is the concrete payoff of the state machine: atomicity held even though a real crash occurred mid-transaction. Contrast this with a crash at step 9, after the commit record was forced but before the lazy flush of buffered pages completes. Recovery now finds `` in the log, so `T1` is treated as committed; recovery redoes any updates not yet reflected on disk using the after-images (`A=50`, `B=150`), guaranteeing the committed effect survives. This redo side of recovery is developed fully in Log-Based Crash Recovery; the point here is only that the state at the moment of crash — determined entirely by whether the commit record was durable — completely determines which recovery action (undo vs. redo) is correct.

The transaction state model and its guarantee of atomicity emerged from the practical demands of early database and transaction-processing systems, where hardware failures were frequent and the cost of losing or corrupting financial records was unacceptable.

Every production relational database — PostgreSQL, MySQL/InnoDB, Oracle, SQL Server — implements exactly this state machine internally, exposing it to applications only through `BEGIN`, `COMMIT`, and `ROLLBACK` statements while enforcing the durability-precedes-report invariant via write-ahead logging (WAL) or equivalent mechanisms. Distributed systems extend the same core states across multiple nodes: two-phase commit protocols add a "prepared" sub-state that refines partially committed into a coordinator-visible checkpoint, ensuring atomicity across machines rather than just across disk writes on one machine. NoSQL and NewSQL systems that offer multi-document or multi-row transactions (MongoDB with multi-document transactions, Google Spanner, CockroachDB) implement the same lifecycle, often layering it under stronger isolation guarantees. Financial systems, airline reservation systems, and e-commerce checkout flows all depend on this state machine to guarantee that a payment, a booking, or an order is never left half-applied. Understanding this lifecycle is also the necessary prerequisite for understanding how Log-Based Crash Recovery decides, after a crash, which transactions to redo and which to undo, and how Serializability and Schedules reasons about the interleavings of many active transactions running through these same states concurrently.

Ask the tutor: How does the "partially committed" state interact with two-phase commit in distributed transactions?