Transactions And Concurrency
Transactions in Depth
PARTIALLY COMMITTED ──► COMMITTED happens when
JrCodex·6 min read
Jr Codex DBMS Notes
Level: Advanced Prerequisites: Module 6, Chapter 4; Module 1, Chapter 4 Time to complete: ~20 minutes
Table of Contents
- The Transaction Lifecycle
- Schedules
- Serialisability
- Conflict Serialisability and the Precedence Graph
- Recoverability
- Why Databases Relax This
- Summary & Next Steps
1. The Transaction Lifecycle
The States
─────────────────────────────────────────
BEGIN
│
▼
┌─────────┐
│ ACTIVE │◄──── reads and writes
└────┬────┘
┌──────┴──────┐
▼ ▼
┌────────────┐ ┌────────┐
│ PARTIALLY │ │ FAILED │
│ COMMITTED │ └───┬────┘
└─────┬──────┘ │ rollback
│ log flushed ▼
▼ ┌──────────┐
┌───────────┐ │ ABORTED │
│ COMMITTED │ └──────────┘
└───────────┘
─────────────────────────────────────────
The Line That Matters
─────────────────────────────────────────
PARTIALLY COMMITTED ──► COMMITTED happens when
the LOG is durably flushed, not when the tables
are updated (Module 1, Chapter 4).
Before that line, a crash means the transaction
never happened. After it, a crash means the
transaction is replayed on recovery.
There is no in-between state visible to anyone.
─────────────────────────────────────────
2. Schedules
The Vocabulary
─────────────────────────────────────────
SCHEDULE the interleaved order in which
operations from several
transactions actually execute
SERIAL transactions run one after another,
with no interleaving. Trivially
correct — and terrible for
throughput.
CONCURRENT operations interleave. Fast, and
correct only if it behaves like
SOME serial order.
─────────────────────────────────────────
Notation
─────────────────────────────────────────
R₁(A) transaction 1 reads item A
W₁(A) transaction 1 writes item A
C₁ transaction 1 commits
A SERIAL schedule:
R₁(A) W₁(A) C₁ R₂(A) W₂(A) C₂
A CONCURRENT schedule:
R₁(A) R₂(A) W₁(A) W₂(A) C₁ C₂
↑ T₂ overwrote T₁'s
write — the LOST
UPDATE
─────────────────────────────────────────
3. Serialisability
The Definition
─────────────────────────────────────────
A schedule is SERIALISABLE if its effect is
identical to SOME serial ordering of the same
transactions.
Note "some" — it need not match the order they
started in. Any serial order will do.
This is the correctness standard for
concurrency. It is what isolation in ACID means
at full strength.
─────────────────────────────────────────
Why It Is the Right Standard
─────────────────────────────────────────
If every schedule is serialisable, then a
developer can reason about ONE transaction at a
time and be correct.
That is an enormous simplification. Without it,
every piece of code must be analysed against
every other piece of code that might run
concurrently — which nobody does successfully.
This is why weakening isolation (Chapter 2) is
such a consequential decision: it moves that
reasoning burden onto you.
─────────────────────────────────────────
4. Conflict Serialisability and the Precedence Graph
Serialisability is expensive to test directly. Conflict serialisability is a stricter condition that can be checked mechanically.
Conflicting Operations
─────────────────────────────────────────
Two operations CONFLICT if they:
- are from DIFFERENT transactions
- access the SAME data item
- and at least one is a WRITE
So:
R-R no conflict — order does not matter
R-W CONFLICT
W-R CONFLICT
W-W CONFLICT
─────────────────────────────────────────
The Test
─────────────────────────────────────────
Build a PRECEDENCE GRAPH:
- one node per transaction
- an edge Tᵢ → Tⱼ whenever an operation of Tᵢ
conflicts with, and comes BEFORE, an
operation of Tⱼ
The schedule is conflict-serialisable
⟺ the graph has NO CYCLE.
If acyclic, any topological sort of the graph is
an equivalent serial order.
─────────────────────────────────────────
def is_conflict_serialisable(schedule):
"""schedule: list of (txn, op, item) with op in {'R','W'}."""
edges, seen = set(), []
for txn, op, item in schedule:
for ptxn, pop, pitem in seen:
if ptxn != txn and pitem == item and ('W' in (op, pop)):
edges.add((ptxn, txn)) # earlier conflicts with later
seen.append((txn, op, item))
txns = {t for t, _, _ in schedule}
return not has_cycle(txns, edges), edges
schedule = [('T1','R','A'), ('T2','R','A'), ('T1','W','A'), ('T2','W','A')]
print(is_conflict_serialisable(schedule))
# (False, {('T1','T2'), ('T2','T1')}) ← a cycle: NOT serialisableReading That Result
─────────────────────────────────────────
T1 → T2 because T1's read of A precedes T2's
write of A.
T2 → T1 because T2's read of A precedes T1's
write of A.
A cycle. No serial order produces this outcome,
so the schedule is incorrect — and the concrete
symptom is the lost update from Section 2.
─────────────────────────────────────────
5. Recoverability
Serialisability is not sufficient on its own. A schedule must also survive aborts.
Three Levels
─────────────────────────────────────────
RECOVERABLE
A transaction commits only AFTER every
transaction whose data it read has committed.
Otherwise: T2 reads T1's uncommitted write and
commits; then T1 aborts. T2 committed a value
that never existed — and it is already
committed, so it cannot be undone.
CASCADELESS (avoids cascading rollback)
A transaction reads only COMMITTED data.
Otherwise aborting T1 forces aborting T2, which
forces T3 — an abort cascade.
STRICT
No transaction may read OR write a data item
until the transaction that last wrote it has
committed or aborted.
Makes undo trivial: just restore the before
image.
─────────────────────────────────────────
What Real Databases Use
─────────────────────────────────────────
STRICT schedules, essentially always.
Strict two-phase locking (Chapter 3) produces
them automatically, which is a large part of why
it is the standard protocol.
─────────────────────────────────────────
6. Why Databases Relax This
The Cost of Full Serialisability
─────────────────────────────────────────
Enforcing it requires either:
- extensive LOCKING, which makes transactions
wait on each other (Chapter 3), or
- detecting conflicts and ABORTING transactions
that would violate it (Chapter 4)
Both reduce throughput. Under contention,
substantially.
─────────────────────────────────────────
The Trade Databases Offer
─────────────────────────────────────────
A DIAL: isolation levels. Weaker levels permit
specific anomalies in exchange for concurrency.
And the defaults are weaker than serialisable:
PostgreSQL READ COMMITTED
MySQL/InnoDB REPEATABLE READ
Oracle READ COMMITTED
SQL Server READ COMMITTED
So unless you changed it, your application is NOT
running at the correctness standard this chapter
described.
That is a defensible engineering choice — but
only if you know you made it, and Chapter 2 is
about knowing exactly what it permits.
─────────────────────────────────────────
7. Summary & Next Steps
Key Takeaways
- A transaction becomes committed when its log is durably flushed, not when the tables are updated; there is no partially-visible state.
- A schedule is serialisable if its effect matches some serial order, which is what lets a developer reason about one transaction at a time.
- Conflict serialisability is checked mechanically with a precedence graph: a cycle means no equivalent serial order exists.
- Every mainstream database defaults to an isolation level weaker than serialisable, so the correctness standard in this chapter is not what your code is getting unless you asked for it.
Concept Check
- Why is R-R not a conflict while R-W is?
- Build the precedence graph for
R₁(A) W₁(A) R₂(A) W₂(A) R₂(B) W₂(B) R₁(B) W₁(B)and say whether it is serialisable. - Why is serialisability alone insufficient without recoverability?
Next Chapter
→ Chapter 2: Anomalies and Isolation Levels
Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index | Back to DBMS Index