The Transaction Concept

A transaction is a unit of program execution that accesses, and possibly updates, various data items in a database. It is the basic unit of change in a database system: everything a database engine does to enforce reliability and consistency is expressed in terms of transactions, not individual instructions. A transaction is typically delimited explicitly, for example by `begin transaction` and `end transaction` (or `commit`) statements, or implicitly, where each individual SQL statement submitted by an application is treated as its own transaction unless the programmer groups several statements together. Internally, a transaction is built from two fundamental low-level operations on the database:

• `read(X)`: transfers the data item `X` from the database (on disk) into a variable, also usually called `X`, in the buffer belonging to the program that executes the transaction.
• `write(X)`: transfers the value of the local buffer variable `X` back into the database, either immediately or, more commonly, at some later point managed by the buffer manager and recovery subsystem.

A transaction is thus a sequence of these operations interleaved with ordinary computation — arithmetic, comparisons, conditional logic — performed by the surrounding program. What makes this sequence special is not the individual operations themselves (any program does reads and writes) but the guarantee the system attaches to the sequence as a whole: the DBMS promises that the transaction's effect on the database is atomic. Either every `write` that the transaction issues is durably reflected in the database, or none is — there is no partial, half-finished state visible to anyone, ever, even across crashes. This is fundamentally different from an ordinary program. If a text editor crashes halfway through saving a file, the user expects to inspect the damage and possibly recover manually. A database cannot offer that luxury at scale: thousands of transactions run per second, many of them touching overlapping data, and no human can supervise each one. The transaction concept exists precisely so that the system, not the programmer or the user, is responsible for guaranteeing this all-or-nothing behavior, no matter what failures occur mid-execution. This foundational promise — atomicity — together with three companion guarantees (consistency, isolation, durability) is formalized as the ACID Properties in the next stage of this material; here we focus purely on establishing what the unit being protected actually is.

Consider again the classic example: transferring an amount from account `A` to account `B`. Both accounts are stored as data items in the database. The transaction consists of exactly two updates, expressed using the primitive `read`/`write` operations, wrapped around the arithmetic that computes the new balances. ``` transaction Transfer(A, B, amount): begin transaction read(A) // load A's balance into local variable A A := A - amount // ordinary program computation write(A) // request that A's new value be recorded read(B) // load B's balance into local variable B B := B + amount // ordinary program computation write(B) // request that B's new value be recorded if sufficient_funds_check_failed: rollback // abort: undo any effects, as if nothing happened else: commit // all operations become permanent, as a unit ``` Two outcomes are legal for this transaction: 1. Commit: both `write(A)` and `write(B)` take effect; the database reflects the transfer completely. 2. Abort (rollback): neither update takes effect; the database looks exactly as if the transaction had never run. No third outcome is acceptable. A run where `A` is debited but `B` is never credited is a violation of the transaction concept itself, regardless of why it happened — a crash, a deadlock, a constraint violation, or a program-level decision to cancel. The mechanism that makes this possible relies on the DBMS tracking, for every transaction, which data items it has read and which values it intends to write, before those values become permanent. Conceptually the system maintains a log of these intended changes so that, if the transaction cannot finish, its partial writes can be undone; and so that, once a transaction commits, its writes survive even a subsequent crash. The precise machinery for this — write-ahead logging, buffer management, undo/redo — belongs to later material on recovery; what matters at this foundational level is why such machinery is unavoidable: because a transaction is defined as an indivisible unit, the system must be prepared to either finish all of its writes or erase all of its writes, and it must be able to do so even if power is lost mid-operation. ``` GENERIC TRANSACTION EXECUTION MODEL Input: a sequence of operations op_1, op_2, ..., op_n each op_i is either read(X_i) or write(X_i) begin transaction for i = 1 to n: execute op_i if op_i fails (e.g., disk error, constraint violation, deadlock victim): abort transaction // system undoes all writes done so far return FAILURE // all operations completed successfully commit transaction // system makes all writes permanent, as one unit return SUCCESS ``` The key structural fact this pseudocode encodes: the decision to commit or abort is made exactly once, for the transaction as a whole, never per-operation. That single decision point is what "unit of execution" means.

Time cost. A transaction consisting of `n` primitive `read`/`write` operations requires, at minimum, `n` I/O-relevant accesses to data items plus bookkeeping overhead proportional to `n` for logging enough information to undo or redo the transaction's writes. So the intrinsic work of executing the transaction body is `O(n)` in the number of operations it performs — this is unavoidable since each operation must at least be touched once. The overhead introduced by the transaction concept itself (as opposed to the raw reads/writes) is the cost of recording, for each `write(X)`, the old and/or new value of `X` so recovery is possible; this is a constant factor per write, not an asymptotic blow-up. Committing or aborting is `O(1)` bookkeeping at the transaction-management level (flip a status flag, though the underlying log flush for durability costs `O(1)` amortized I/O per commit in typical write-ahead logging schemes, deferred to the recovery material).

Space cost. Space overhead is `O(n)` in the number of writes performed, since the system must retain enough log information — old values, new values, or both — to reverse or redo every write until the transaction's fate (commit or abort) is durably recorded. This is a fixed, small multiplicative overhead per data item written, not a function of the database's total size.

Correctness argument. The correctness property we care about at this foundational level is precisely stated as an invariant on the visible state of the database: > Invariant (all-or-nothing visibility). At any point in time, for any transaction `T`, the database reflects either all of `T`'s writes or none of `T`'s writes — never a strict, nonempty subset. Why must a transaction mechanism maintain this invariant, and how does the sketch above achieve it?

• Necessity. Consider the transfer transaction. Suppose the invariant were violated: `write(A)` took effect but `write(B)` did not, because of a crash between the two statements. The database now shows $500 removed from `A` and never added to `B`. Since the database is the sole source of truth for every subsequent computation, this partial state is not a temporary annoyance — it is a permanent, undetectable loss of$500 unless some external, ad hoc audit finds it. The invariant is therefore not a nicety; it is required for the data to have any coherent meaning as "the state of the accounts."

• Sufficiency of the commit/abort discipline. The pseudocode above ensures the invariant by construction: it defers the permanent effect of a transaction's writes to a single, atomic decision point (`commit`), and it guarantees that if execution is interrupted before that point — by an explicit `rollback` or by any failure — every write attempted so far is undone. Formally, if we let `W(T)` denote the set of writes issued by transaction `T`, the system maintains the invariant by ensuring:

at every observable instant, where `visible(T)` is the subset of `T`'s writes reflected in the database as seen by any other transaction or by a post-crash restart. The mechanism achieves this because no write becomes durable-and-visible except as part of the single commit action, and the commit action itself is made durable atomically (conceptually, by writing one commit record whose presence or absence is itself all-or-nothing at the level of a single disk block/log record — the deepest recovery mechanics are developed separately).

• Honesty about what this does NOT yet guarantee. This foundational transaction concept, by itself, does not yet address what happens when two transactions run concurrently and interleave their reads and writes on the same data items — that is the domain of isolation and concurrency control. Nor does it explain the exact internal states (active, partially committed, failed, aborted, committed) a transaction passes through, or precisely how consistency is preserved across the whole database schema. Those refinements are exactly the content of ACID Properties and Transaction States and Atomic Execution. What is established here is narrower but essential: why operations must be grouped into an indivisible unit at all, and what that unit looks like mechanically.

Trace the transfer of $500 from account `A` (starting balance 1000) to account `B` (starting balance 200), under two scenarios: a normal successful run, and a run that crashes mid-transaction.

Scenario 1 — normal execution (commit).

After step 7, any other transaction reading `A` or `B` sees the new values, and this remains true even if the machine crashes one microsecond later — the commit record is the atomic switch that makes both writes durable together.

Scenario 2 — crash before commit (abort/recovery).

Notice the crucial asymmetry: in Scenario 2 the transaction never reached `write(B)` at all, yet the recovery procedure treats the entire transaction as void, including the already-issued `write(A)`. This is the invariant from the previous section in action: since no commit record exists, `visible(T) = ∅`, not the partial set `{write(A)}`. If the system instead left `A = 1000 - 500 = 500` on disk after this crash while `B` stayed at 200, $500 would have been permanently destroyed — exactly the failure the transaction concept exists to prevent.

The transaction concept as a formal database abstraction emerged from the practical demands of early online systems — airline reservations, banking, and later general-purpose database engines — that needed reliable updates from unreliable hardware and fallible programs. The person most closely associated with formalizing this idea, along with the surrounding theory of concurrency control and recovery, is Jim Gray, whose work at IBM and later Tandem Computers turned an ad hoc engineering practice into rigorous theory.

Every commercial relational database — PostgreSQL, MySQL/InnoDB, Oracle, Microsoft SQL Server, IBM Db2 — implements the transaction concept as its core execution model, exposing it directly through `BEGIN`, `COMMIT`, and `ROLLBACK` statements. Banking cores, stock exchange order-matching engines, airline and hotel reservation systems, and e-commerce checkout pipelines all rely on transactions to guarantee that money, seats, and inventory are never silently duplicated or destroyed, even under crashes and power failures. Distributed systems extend the idea further: two-phase commit protocols and modern distributed databases (Google Spanner, CockroachDB, Amazon Aurora) generalize the single-machine transaction concept across multiple machines, still preserving the same all-or-nothing guarantee at a much larger scale. Even outside classical databases, the transaction concept has influenced designs such as journaling filesystems, blockchain ledgers, and application-level "saga" patterns in microservices, all of which borrow the same fundamental idea: group risky, multi-step changes into a unit that either fully happens or leaves no trace. This foundational concept is the direct prerequisite for understanding the ACID Properties that formalize its guarantees, and the Transaction States and Atomic Execution model that describes precisely how a transaction moves from start to commit or abort — both natural next steps built entirely on the definition established here.

Ask the tutor: How does the system decide exactly when a transaction's commit becomes durable, even if the machine crashes one instruction later?