- Atlas
- Computer Science
- Transaction Processing
Transaction Processing
A transaction is a group of database operations that the system treats as a single, indivisible unit: either all of it happens or none of it does.
13 frameworks, from 1975 to today · Databases · Computer Science
- Two-Phase Locking 1975-Present
- Isolation 1976-Present
- Serializability Theory 1976-Present
- Timestamp-based concurrency control 1976-1995
- Multiversion Concurrency Control 1978-Present
- Two-phase commit protocol 1978-Present
- Optimistic Concurrency Control 1981-Present
- ACID 1983-Present
- Weak Isolation Levels 1992-Present
- Write-Ahead Logging and ARIES Recovery 1992-Present
- CAP Theorem and BASE 2000-Present
- Eventual consistency and BASE 2000-Present
- Deterministic Transaction Execution 2008-Present
Overview
A transaction is a group of database operations that the system treats as a single, indivisible unit: either all of it happens or none of it does123. Transaction processing is the set of techniques that make this promise real when many users act at once, when machines crash mid-write, and when data is spread across many computers1. The stakes are concrete. If a bank debits one account and crashes before crediting another, money vanishes; if two people book the last airline seat simultaneously, one must be told no. Almost every idea in this history is an answer to one of those two problems — concurrency (keeping simultaneous users from corrupting each other's work) and recovery (surviving crashes) — and to the tension between correctness and speed1.
Files, Locks, and the First Commercial Systems (1950s–1960s)
Early business computing ran batch jobs on magnetic tape: records were processed in sequence, one job at a time, so concurrency barely existed. The move to disk drives and interactive terminals in the early 1960s changed that. Disk storage allowed random access, and time-sharing allowed many users to touch the same files. The first commercial systems to face this — IBM's airline reservation work and the Sabre system, developed with American Airlines and operational by 1960 — had to prevent two agents from selling the same seat.
The practical answer was locking: before changing a record, a program claimed it, and other programs waited. But locks brought their own hazards. If two programs each held one lock and waited for the other's, both froze — a deadlock1. Early systems also had no principled notion of what a "correct" interleaving of operations even was, so designers argued from intuition. The theoretical groundwork came from E. F. Codd's relational model (1970), which gave data a clean logical form, and from early work on concurrency in operating systems. What was missing was a definition of correctness that a system could enforce mechanically.
Serializability: Defining Correctness (1970s)
The key idea, developed in the mid-1970s, was serializability. A schedule — the interleaved order in which the system actually executes operations from several transactions — is serializable if its effect is identical to running the transactions one after another in some order1. Since nobody disputes that serial execution is correct, serializability gives a precise, checkable standard for concurrent execution.
Researchers including K. P. Eswaran, Jim Gray, Raymond Lorie, and Irving Traiger at IBM published the central paper in 1976, introducing the conflict-based theory: two operations conflict if they touch the same data item and at least one writes it, and a schedule is serializable exactly when the conflicts can be ordered consistently. The same era produced the two-phase locking (2PL) protocol, in which a transaction acquires all its locks before releasing any — a growing phase, then a shrinking phase. 2PL guarantees serializability, and it became the workhorse of commercial databases. Its cost is blocking and the ever-present risk of deadlock, which systems detect by watching for cycles in the "waits-for" graph and aborting a victim.
A competing family, timestamp ordering, avoided locks entirely: each transaction got a timestamp at start, and the system checked each operation against the timestamps of operations already done on that item, aborting transactions that arrived "too late." It never blocks, but it aborts more under contention. Both approaches, and the theory behind them, were synthesized in Philip Bernstein and Nathan Goodman's influential survey work at the end of the decade.
ACID, Recovery, and the System R Legacy (1970s–1980s)
Alongside concurrency came the vocabulary of guarantees. Theo Härder and Andreas Reuter's 1983 paper named the ACID properties — atomicity (all or nothing), consistency (transactions move the database between valid states), isolation (concurrent transactions don't see each other's partial work), and durability (committed work survives crashes)4. The acronym crystallized ideas already embodied in IBM's System R prototype (mid-1970s), the project that also produced SQL and demonstrated that a relational system with transactions could perform well.
Durability and atomicity demanded recovery. The dominant technique became write-ahead logging: before a changed page is written to disk, a record of the change goes to a sequential log. After a crash, the log is replayed5. The culmination was ARIES, published by C. Mohan and colleagues at IBM in 1992, which combined write-ahead logging, repeating history during recovery, and fuzzy checkpointing so that recovery could proceed correctly even while the system kept accepting new work. ARIES-style recovery remains the standard architecture in most major database engines.
Distributed systems added a second problem: a transaction spanning several machines must commit everywhere or nowhere6. Two-phase commit (2PC) solved it with a coordinator that first asks all participants to prepare (and promise they can commit), then tells them all to commit7. Its weakness is equally famous: if the coordinator dies after some participants have prepared, they may block indefinitely. 2PC became the standard for distributed transactions, and its fragility motivated decades of later work.
Isolation Levels and the Cost of Correctness (1980s–1990s)
Full serializability is expensive: locks block, and blocking hurts throughput18. In 1976 Gray and colleagues had already proposed weaker isolation levels — read uncommitted, read committed, repeatable read, serializable — trading some anomalies for speed. The SQL standard later codified them, though ambiguously. In 1995 Hal Berenson, Phil Bernstein, Jim Gray, Jim Melton, Elizabeth O'Neil, and Patrick O'Neil published "A Critique of ANSI SQL Isolation Levels," showing that the standard's definitions were inconsistent and that real systems offered guarantees the standard didn't name. Their paper introduced snapshot isolation, a scheme in which each transaction reads from a consistent snapshot of the database as of its start. Snapshot isolation prevents many anomalies and never blocks readers, but it permits write skew — two transactions each reading data the other modifies, producing a state no serial order could reach — so it is not fully serializable.
Snapshot isolation's practical appeal grew with multiversion concurrency control, which keeps older versions of records so readers can see a stable past without waiting910. The idea dates to the late 1970s, but it became mainstream in the 1990s and 2000s as storage cheapened and read-heavy workloads dominated. Optimistic concurrency control, proposed by H. T. Kung and John Robinson in 1981, took the opposite stance to locking: let transactions run freely, validate at commit time, and abort conflicts. It suits workloads with low contention and became influential in main-memory systems decades later.
Replication, BASE, and the NoSQL Turn (2000s)
As web companies scaled across data centers, the cost of distributed coordination became the central issue. Eric Brewer's CAP theorem (conjectured 2000, proved by Seth Gilbert and Nancy Lynch in 2002) stated that a distributed system facing a network partition must sacrifice either consistency or availability11. In practice, large internet systems chose availability, and the resulting style was labeled BASE — basically available, soft state, eventual consistency — by Armando Fox and Eric Brewer around 2008, as an explicit counterpoint to ACID. Eventual consistency means replicas may diverge temporarily but converge if updates stop12. Systems such as Amazon's Dynamo (2007) embraced it. The trade-off was real: applications now had to reason about stale reads and conflicting writes themselves12.
Determinism, NewSQL, and the Present (2010s–today)
The reaction arrived quickly. A wave of systems — VoltDB, founded by Michael Stonebraker and colleagues around 2008–2010, and Calvin, published by Daniel Abadi and colleagues in 2012 — pursued deterministic transaction execution: if every replica processes the same transactions in the same order, no locking or distributed commit protocol is needed at execution time. Ordering becomes the hard problem, solved by consensus protocols such as Paxos and Raft. Meanwhile, "NewSQL" systems like Google Spanner (2012) showed that globally distributed, externally consistent transactions were achievable at scale by using synchronized clocks and consensus, narrowing the gap CAP had seemed to force open.
Today the field is plural. Main-memory engines exploit cheap RAM to run optimistic and multiversion schemes at high speed; cloud databases offer snapshot isolation by default and serializable mode on request; deterministic and consensus-replicated designs underpin globally distributed services; and weaker consistency remains the pragmatic choice for many large-scale applications. The open questions are familiar in shape: how to give programmers strong guarantees without paying serializability's price, how to make distributed commit cheap and non-blocking, and how to specify isolation precisely enough that a user knows what they are actually getting.
References
- Transaction processing (introduction, Description, Deadlocks), Wikipedia
- Database transaction, Wikipedia
- Atomicity (database systems), Wikipedia
- ACID, Wikipedia
- Algorithms for Recovery and Isolation Exploiting Semantics, Wikipedia
- Distributed transaction, Wikipedia
- Two-phase commit protocol, Wikipedia
- Concurrency control, Wikipedia
- Snapshot isolation, Wikipedia
- Multiversion concurrency control, Wikipedia
- CAP theorem (introduction, History), Wikipedia
- Eventual consistency, Wikipedia
The frameworks of Transaction Processing
Each framework is a way of working the field has used: when it held, and the question it answers.
- 1975-Present
Two-Phase Locking
How do locks make concurrent transactions serializable?
- 1976-Present
Isolation
What guarantees does a transaction get against other transactions?
- 1976-Present
Serializability Theory
When is a concurrent execution equivalent to a serial one?
- 1976-1995
Timestamp-based concurrency control
Can concurrency be controlled without locks?
- 1978-Present
Multiversion Concurrency Control
How can readers see a stable past without blocking writers?
- 1978-Present
Two-phase commit protocol
How can a transaction commit everywhere or nowhere?
- 1981-Present
Optimistic Concurrency Control
Can transactions run freely and be checked at commit?
- 1983-Present
- 1992-Present
- 1992-Present
Write-Ahead Logging and ARIES Recovery
How does a system recover after a crash mid-write?
- 2000-Present
CAP Theorem and BASE
What must a distributed system give up under partition?
- 2000-Present
- 2008-Present
Deterministic Transaction Execution
Can ordering transactions in advance remove coordination?
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
Serializability Theory influenced by Two-Phase Locking
The conflict-based serializability theory of Eswaran, Gray, Lorie, and Traiger was built to characterize exactly what two-phase locking guarantees. 2PL served as the canonical protocol that the theory proved correct.
Carried by K. P. Eswaran; Jim Gray; Raymond Lorie.
ACID influenced by Isolation
Härder and Reuter's ACID paper made isolation one of the four named properties, drawing on the isolation levels and serializability work already in the literature. The I in ACID is the isolation concept developed in the 1970s.
Carried by Theo Härder; Andreas Reuter.
Weak Isolation Levels grew out of Isolation
Berenson, Bernstein, Gray, Melton, O'Neil, and O'Neil's critique of ANSI isolation levels refined the earlier isolation-level framework, showing the standard's definitions were inconsistent and introducing snapshot isolation as a named level. Weak isolation levels grew directly out of the 1976 isolation-level scheme.
Carried by Hal Berenson; Phil Bernstein; Jim Gray.
Weak Isolation Levels influenced by Multiversion Concurrency Control
Snapshot isolation, introduced in the isolation-levels critique, is a multiversion scheme in which each transaction reads a consistent snapshot. The paper drew on multiversion concurrency control to define and analyze the new level.
Carried by Hal Berenson; Phil Bernstein.
CAP Theorem and BASE reacted against ACID
Brewer's CAP theorem framed the consistency-versus-availability trade-off that large internet systems used to justify abandoning ACID guarantees. The theorem and the BASE style it inspired defined themselves against ACID's strong consistency.
Carried by Eric Brewer.
Eventual consistency and BASE reacted against ACID
BASE was coined by Fox and Brewer as an explicit counterpoint to ACID, embracing basically available, soft state, eventual consistency. Eventual consistency became the practical alternative to ACID's strong guarantees for replicated systems.
Carried by Armando Fox; Eric Brewer.
Timestamp-based concurrency control rival of Two-Phase Locking
Two-phase locking and timestamp ordering were the two dominant concurrency-control families of the late 1970s, competing on blocking versus abort rates. Both aimed at serializability by different means.
Optimistic Concurrency Control reacted against Two-Phase Locking
Kung and Robinson proposed optimistic concurrency control explicitly as an alternative to locking, arguing that validation at commit time avoids the blocking and deadlock overhead of two-phase locking. The paper frames its method against the lock-based approach.
Carried by H. T. Kung; John Robinson.
ACID influenced by Two-Phase Locking
The ACID properties crystallized guarantees already embodied in System R, whose transaction manager used two-phase locking. Härder and Reuter named the properties that lock-based systems had been providing.
Carried by Theo Härder; Andreas Reuter.
Write-Ahead Logging and ARIES Recovery influenced by Two-Phase Locking
ARIES recovery was designed to work with the fine-grained locking used by commercial systems, and its repeating-history phase must restore lock and log state consistently with two-phase locking. The recovery architecture assumes the lock manager's transaction state.
Carried by C. Mohan.
Deterministic Transaction Execution reacted against Two-Phase Locking
Deterministic transaction execution was proposed as a way to avoid locking and distributed commit entirely by ordering transactions in advance. It defines itself against the lock-based and two-phase-commit architectures that dominated transaction processing.
Carried by Michael Stonebraker; Daniel Abadi.
Timestamp-based concurrency control influenced by Serializability Theory
Timestamp ordering was designed and justified within the same conflict-serializability framework, using the theory's conflict relation to check whether operations arrived in a serializable order. The protocol is a lock-free way to achieve the correctness criterion the theory defined.
Carried by Philip Bernstein; Nathan Goodman.
Multiversion Concurrency Control influenced by Serializability Theory
Multiversion concurrency control was formalized by extending serializability theory to histories over multiple versions, defining multiversion serializability and proving protocols correct against it. The one-copy serializability criterion grew directly out of the earlier conflict theory.
Carried by Philip Bernstein; Nathan Goodman.
Optimistic Concurrency Control influenced by Serializability Theory
Kung and Robinson's optimistic concurrency control validated transactions at commit time against the serializability criterion, aborting any whose reads and writes could not be ordered consistently. The protocol is defined and justified in the vocabulary of the conflict theory.
Carried by H. T. Kung; John Robinson.
ACID influenced by Serializability Theory
The consistency and isolation components of ACID rest on the serializability theory that defined when concurrent execution is correct. Härder and Reuter's formulation assumes the serializability criterion as the standard for isolation.
Carried by Theo Härder; Andreas Reuter.
Multiversion Concurrency Control rival of Timestamp-based concurrency control
Timestamp ordering and multiversion concurrency control were contemporaneous lock-free approaches to serializability, competing to avoid blocking while controlling conflicts. Multiversion schemes extended timestamp ideas to multiple versions.
Deterministic Transaction Execution reacted against Two-phase commit protocol
Deterministic execution aims to eliminate the two-phase commit protocol's blocking and coordinator failure by making every replica process the same ordered transaction stream. The approach is framed as an alternative to 2PC for distributed transactions.
Carried by Michael Stonebraker; Daniel Abadi.
Beyond the field
Where Transaction Processing's ideas came from in other fields, and what they led to there: the strongest 12 of 36 links.
Optimistic Concurrency Control influenced by Database transaction in Database Theory
Kung and Robinson's optimistic concurrency control was formulated directly for database transactions, using the transaction as its unit of validation and serializability as its correctness criterion. The paper appeared in ACM TODS in 1981 and built on the transaction concept developed in the 1970s.
Carried by H. T. Kung; John T. Robinson; On Optimistic Methods for Concurrency Control (1981).
ACID grew out of Database transaction in Database Theory
ACID properties were formulated as a summary of the guarantees that database transaction systems already provided; the transaction concept is the object whose properties ACID names.
Carried by Theo Härder; Andreas Reuter; Principles of Transaction-Oriented Database Recovery (1983).
Weak Isolation Levels grew out of Transaction processing and ACID in Databases
Weak isolation levels are the graded weakening of the isolation property in transaction processing and ACID, trading serializability for concurrency.
Carried by ANSI SQL-92.
Weak Isolation Levels grew out of Transactions and ACID in Reliability Fault Tolerance
Weak isolation levels were defined by weakening the isolation guarantee of ACID transactions; the ANSI SQL-92 isolation levels and later work by Berenson et al. specify anomalies permitted when full serializability is not enforced.
Carried by ANSI SQL-92; Hal Berenson; A Critique of ANSI SQL Isolation Levels (1995).
Write-Ahead Logging and ARIES Recovery grew out of Transaction processing and ACID in Databases
Write-ahead logging and ARIES are the recovery mechanism that delivers atomicity and durability in transaction processing systems; ARIES was developed on and for such systems.
Carried by C. Mohan.
Write-Ahead Logging and ARIES Recovery grew out of Transactions and ACID in Reliability Fault Tolerance
ARIES recovery was designed to enforce the atomicity and durability of ACID transactions, using write-ahead logging, repeating history and fuzzy checkpointing. The 1992 ARIES paper by Mohan et al. states these transaction properties as its goal.
Carried by C. Mohan; ARIES (1992).
Deterministic Transaction Execution influenced by Database transaction in Database Theory
The database transaction concept, with its begin/commit/abort semantics and serializability criterion, is the object that deterministic execution systems re-implement without locking; the later work takes the transaction abstraction and its correctness conditions directly from database theory.
Two-Phase Locking influenced by Shared-Memory Concurrency with Locks in Concurrency Models
Two-phase locking adapted the lock/unlock discipline of shared-memory concurrent programming, notably Eswaran et al.'s 1976 formulation building on earlier mutual-exclusion locking practice.
Carried by Kapali P. Eswaran; Jim N. Gray; Raymond A. Lorie.
Two-Phase Locking influenced Distributed transaction in Distributed Databases
Two-phase locking provided the local concurrency control mechanism that distributed transaction systems extended across sites. Distributed locking protocols built on the same lock-point discipline to ensure global serializability.
Isolation influenced by Relational model in Databases
The relational model's shared-table access motivated the isolation concept, which was formulated for relational database systems in the mid-1970s.
Carried by Jim N. Gray; Raymond A. Lorie.
Isolation influenced by Relational model in Database Theory
Isolation was defined against the relational model's concurrent access to shared relations, with Gray, Lorie and Putzolu framing consistency in relational database terms.
Carried by Jim N. Gray; Raymond A. Lorie; Irving L. Traiger.
Serializability Theory influenced Distributed Systems Correctness Theory in Distributed Databases
Serializability theory supplied the formal correctness criterion that distributed systems correctness theory extended to replicated and partitioned data. The theory of serial schedules was carried into distributed settings.

Transaction Processing is a planet in Nousfarer
Its city has a tower for each of these 13 frameworks. Land, walk in, and climb one concept at a time.
Land on Transaction ProcessingRelated fields
Fields its ideas are linked to
- Database Theory 7 links
- Databases 7 links
- Distributed Databases 6 links
- Distributed Systems 5 links
- Reliability Fault Tolerance 5 links
- Concurrency Models 4 links
- Distributed Algorithms 1 link
- Storage Systems 1 link
More in Databases
See where Transaction Processing sits on the Map of Human Knowledge