Atomicity
All transaction effects become durable together, or none remain after rollback/recovery.
PART 4 • DATABASE SYSTEMS
Keep Concurrent Changes Correct and Recoverable
Reason about interleaved operations, prevent unsafe observations, resolve lock cycles and restore committed state after failure.
BY THE END, YOU CAN
- Explain each ACID guarantee.
- Trace concurrent schedules.
- Build a precedence graph.
- Apply two-phase locking.
- Recognize isolation anomalies.
- Use WAL reasoning for recovery.
A Transaction Moves the Database between Valid States
BEFOREA = ₹1,000B = ₹500Total = ₹1,500
BEGINA = A − ₹200B = B + ₹200COMMITAFTERA = ₹800B = ₹700Total = ₹1,500
Consistency
A correctly written transaction preserves declared constraints and application invariants.
Isolation
Concurrent execution is controlled so transactions do not observe disallowed intermediate effects.
Durability
After commit succeeds, recovery mechanisms preserve the transaction despite later failure.
A Schedule Preserves Each Transaction's Internal Order
T1: R(X)T1: W(X)T1: CT2: R(X)T2: W(X)T2: C
One transaction finishes before another begins. Simple but restricts concurrency.
T1: R(X)T2: R(Y)T1: W(X)T2: W(Y)T1: CT2: C
Operations overlap while each transaction's own program order remains intact.
If T2 reads a value written by T1, T2 commits only after T1 commits.
Transactions read only committed values, avoiding cascading rollback from dirty dependencies.
No other transaction reads or writes an item written by an uncommitted transaction.
Concurrency Anomalies Reveal Which Guarantee Was Missing
Read uncommitted data
T2 uses T1's new value, but T1 later rolls back.
One row changes
T1 reads the same row twice and sees a committed update by T2 between reads.
The qualifying row set changes
T1 repeats a predicate query and sees inserted, deleted or newly qualifying rows.
One write overwrites another
Two transactions derive new values from stale reads; the later write erases earlier work.
Overwrite uncommitted data
T2 overwrites a value written by active T1, making rollback unsafe.
Separate rows break one invariant
Transactions read the same condition, update different rows and jointly violate a constraint.
Conflict Serializability Becomes a Graph Problem
SAME DATA ITEMBoth operations touch X
+DIFFERENT TRANSACTIONST1 and T2
+AT LEAST ONE WRITER/W, W/R or W/W
=CONFLICTOrder matters
- Create one node per transaction.
- Scan conflicting operation pairs in schedule order.
- Add edge Ti → Tj when Ti's conflicting operation occurs first.
- If the graph has no directed cycle, the schedule is conflict-serializable.
- A topological order gives an equivalent serial order.
EXAMPLE EDGEST1 → T2T2 → T3No cycle → serial order T1, T2, T3
Locks Coordinate Readers and Writers
| Requested / Held | Shared (S) | Exclusive (X) |
|---|---|---|
| Shared (S) | Compatible | Wait |
| Exclusive (X) | Wait | Wait |
Multiple transactions can read the same item when none holds an exclusive lock.
A writer excludes other readers/writers under this simplified compatibility model.
Moving S → X may wait if another shared holder remains and can contribute to deadlock.
Row locks improve concurrency; page/table locks reduce lock-management overhead.
No lock has yet been released.
Basic 2PL acquires no new lock after the first release.
Strict 2PL: hold exclusive locks until commit or rollback. This prevents dirty reads of written items and simplifies recovery. Two-phase locking ensures conflict serializability but can create deadlocks.
Isolation Levels Balance Anomaly Protection and Concurrency
| SQL level | Dirty read | Non-repeatable read | Phantom | Typical idea |
|---|---|---|---|---|
| READ UNCOMMITTED | Possible | Possible | Possible | Weakest standard level |
| READ COMMITTED | Prevented | Possible | Possible | Each statement sees committed data |
| REPEATABLE READ | Prevented | Prevented | Standard permits phantoms | Repeated row reads remain stable |
| SERIALIZABLE | Prevented | Prevented | Prevented | Outcome equivalent to serial execution |
ROW V1₹500visible to older snapshot
→ update creates →ROW V2₹650visible to eligible newer snapshot
MVCC
Multi-version concurrency control lets readers use appropriate row versions instead of always blocking writers. Visibility rules, isolation semantics and cleanup differ by database product.
Write-Ahead Logging Records Intent before Data Pages
T7 changes account A from 500 to 650.
<T7, A, old=500, new=650>Required log information reaches stable storage before the changed data page.
Commit is acknowledged only after required log records are durable.
The changed page may be written later.
Remove incomplete effects
Use before-images or inverse information for transactions without a durable commit.
Repeat committed effects
Use after-images for committed work not yet reflected in recovered data pages.
Bound recovery work
Records recovery metadata so restart need not reason from the beginning of the entire log.
Analysis, redo, undo
Widely taught recovery approach using WAL, repeating history and compensation log records.
Transaction failure rollback that transactionSystem crash use durable log during restartMedia failure restore backup, then apply archived/logged changes
Interactive Schedule & Serializability Simulator
Choose a schedule and step through reads, writes, commits and aborts. Watch values, dependencies and the final diagnosis change.
DATABASE VALUE
STEP
STATUS
Deadlock Detection Laboratory
Build each wait-for graph step by step. A directed cycle means the transactions cannot all proceed without intervention.
Ten Formative Concept Checks
1. Atomicity means:
2. T2 reads T1's uncommitted write and T1 later aborts. This is:
3. Two operations conflict when they are from different transactions, access the same item and:
4. A precedence graph with a directed cycle is:
5. Shared locks are normally compatible with:
6. Basic two-phase locking requires:
7. In a wait-for graph, a directed cycle indicates:
8. Under SQL-standard READ COMMITTED, which anomaly is prevented?
9. Write-ahead logging requires the relevant log record to be durable:
10. After a crash, REDO is used mainly to:
Answered correctly: 0 of 10
University and Interview Questions
- Define ACID.
- What is a schedule?
- Define deadlock.
- What is WAL?
- Test conflict serializability.
- Compare recoverable, cascadeless and strict schedules.
- Explain two-phase locking.
- Trace undo and redo after a crash.
- Why can serializable transactions still retry?
- How does MVCC reduce reader/writer blocking?
- How would you investigate a deadlock?
- What does a checkpoint guarantee?
Show the transaction answer framework
- Name every transaction, item and operation.
- Preserve each transaction's program order.
- Identify conflicting pairs and dirty dependencies.
- Draw precedence or wait-for edges.
- Check cycles and commit/abort order.
- State the anomaly or correctness property.
- Choose isolation, locking or recovery action and explain the trade-off.
LEVEL 17 SUMMARY
You Can Now Reason about Concurrent Failure
- ACID defines transaction correctness and survival.
- Schedules interleave operations while preserving local order.
- Conflict graphs test serializability.
- Locks control access but may deadlock.
- Isolation defines permitted visibility.
- WAL, checkpoints, undo and redo support recovery.
COURSE CHECKPOINT
Mark this level when you can trace schedules, diagnose cycles and explain recovery decisions.
Saved in this browser only.