Real-life analogy: Bank transfer

Transferring money requires two steps: deduct from A, add to B. If the system crashes after step 1 but before step 2, money vanishes — inconsistent state. A transaction groups both steps: either BOTH succeed (COMMIT) or NEITHER happens (ROLLBACK). This is Atomicity.

ACID Properties

BEGIN TRANSACTION;

UPDATE Account SET Balance = Balance - 1000
WHERE AccountID = 'A' AND Balance >= 1000;

-- Check if sufficient balance existed
-- If not: ROLLBACK TO SAVEPOINT and raise error

UPDATE Account SET Balance = Balance + 1000
WHERE AccountID = 'B';

COMMIT;  -- Both updates committed atomically
-- On any error: ROLLBACK (reverts both updates)

-- Isolation levels:
-- READ UNCOMMITTED:  Sees uncommitted changes (dirty reads allowed)
-- READ COMMITTED:    Only sees committed data. PostgreSQL default.
-- REPEATABLE READ:   Same query gives same result within transaction
-- SERIALIZABLE:      Full isolation — as if ran one after another

Concurrency anomalies and Two-Phase Locking

Two-Phase Locking (2PL): Growing phase — acquire locks, never release. Shrinking phase — release locks, never acquire new ones. If all transactions follow 2PL, the schedule is guaranteed conflict-serialisable. Strict 2PL: Hold all exclusive locks until commit/abort — prevents cascading rollbacks.

Deadlock — GATE numerical question type: Deadlock: T1 holds lock on A, waits for B; T2 holds lock on B, waits for A — circular wait. Detection: Wait-for graph — cycle = deadlock. Resolution: abort the youngest transaction (victim). Prevention: Wait-Die or Wound-Wait protocols.

Serializability and precedence graph

from collections import defaultdict

def is_conflict_serializable(schedule):
    """
    Schedule: list of (transaction_id, operation, data_item)
    Conflicts: same data item, different transactions, at least one write.
    Add edge Ti→Tj if Ti has conflicting op before Tj on same item.
    Cycle in graph = NOT serializable.
    """
    graph = defaultdict(set)
    for i in range(len(schedule)):
        ti, op_i, item_i = schedule[i]
        for j in range(i+1, len(schedule)):
            tj, op_j, item_j = schedule[j]
            if ti != tj and item_i == item_j and (op_i == 'W' or op_j == 'W'):
                graph[ti].add(tj)

    # DFS cycle detection
    visited, rec = set(), set()
    def dfs(node):
        visited.add(node); rec.add(node)
        for nb in graph[node]:
            if nb not in visited:
                if dfs(nb): return True
            elif nb in rec: return True
        rec.discard(node); return False

    txns = set(t for t,_,_ in schedule)
    return not any(dfs(t) for t in txns if t not in visited), dict(graph)

schedule = [('T1','R','A'),('T2','R','A'),('T1','W','A'),('T2','W','A')]
ok, g = is_conflict_serializable(schedule)
print(f"Serializable: {ok}, Graph: {g}")  # True, {T1:{T2}}

Conflict serializability is not the whole story. A schedule is view serializable if it is view-equivalent to some serial schedule (same reads-from relationships and same final writes). Every conflict-serializable schedule is view serializable, but not vice versa — the gap consists of schedules with blind writes (writes without a preceding read). Testing view serializability is NP-complete, which is why real systems enforce the stricter but cheaply-checkable conflict serializability.

GATE: the class hierarchy: Strict ⊂ Cascadeless ⊂ Recoverable. And serializability is orthogonal to recoverability — a schedule can be serializable yet non-recoverable, or recoverable yet non-serializable. Questions love pairing the two dimensions: always check them independently.

MVCC — how real databases actually implement isolation

Textbook 2PL blocks readers with writer locks, but PostgreSQL, MySQL InnoDB, and Oracle mostly don't work that way. They use Multi-Version Concurrency Control (MVCC): every write creates a new version of the row, and each transaction reads the version that was current at its snapshot time. The killer property: readers never block writers and writers never block readers — a long analytics query can scan a table while thousands of updates proceed underneath it.

• PostgreSQL keeps old row versions in the table itself (dead tuples cleaned by VACUUM); InnoDB reconstructs old versions from undo logs.
• MVCC's REPEATABLE READ is really snapshot isolation — stronger than the SQL-standard level, but still admits write skew: two transactions each read overlapping data, make disjoint writes based on what they read, and jointly violate a constraint neither violated alone (the classic two-doctors-both-going-off-call example).
• PostgreSQL's SERIALIZABLE uses Serializable Snapshot Isolation (SSI): it runs optimistically and aborts a transaction only when it detects a dangerous read-write dependency pattern — no read locks, occasional serialization-failure retries.

Interview trap: In PostgreSQL and MySQL, "REPEATABLE READ" does not behave like the textbook lock-based level — it is snapshot isolation, which prevents phantom reads in practice but permits write skew. If asked "does REPEATABLE READ allow phantoms?", the correct answer is: per the SQL standard yes, in PostgreSQL's implementation no. Precision here is what interviewers are probing.

Crash recovery — WAL, checkpoints, and ARIES in one pass

Durability and atomicity are implemented by the write-ahead log (WAL): before any data page is modified on disk, the log record describing the change is flushed first. On COMMIT, only the log must reach disk — data pages can follow lazily. After a crash, the recovery manager replays the log: redo committed transactions whose changes hadn't reached data pages, undo uncommitted transactions whose changes had.

Practice questions (GATE-style)

1. Precedence graph has cycle T1→T2→T3→T1. Is it conflict-serializable? (Answer: No — a cycle in the precedence graph means NOT conflict-serializable.)
2. Which ACID property is enforced by write-ahead logging (WAL)? (Answer: Durability — WAL writes changes to disk log before modifying actual data. Crashed system replays log on recovery.)
3. T1 holds a Shared (S) lock on X. Can T2 acquire an Exclusive (X) lock on X? (Answer: No — S-X locks conflict. T2 must wait. S-S: compatible. X-X: incompatible. S-X: incompatible.)
4. Strict 2PL vs regular 2PL: (Answer: Strict 2PL holds all exclusive locks until commit/abort. Regular 2PL can release locks during shrinking phase before commit. Strict 2PL prevents cascading rollbacks.)
5. Difference between dirty read and non-repeatable read: (Answer: Dirty read = reading uncommitted data from another transaction. Non-repeatable read = reading same row twice in one transaction and getting different results because another COMMITTED transaction modified it.)
6. Schedule: W1(X), R2(X), C2, C1. Is it recoverable? (Answer: No — T2 read X from uncommitted T1 and committed BEFORE T1. If T1 subsequently aborts, T2 has committed based on data that never existed. Recoverable requires T2 to commit only after T1 commits.)
7. A schedule is view serializable but not conflict serializable. What must it contain? (Answer: A blind write — a write on a data item by a transaction that never read it. Without blind writes, view serializability and conflict serializability coincide.)
8. Under steal/no-force buffer management, which log-based operations are needed at recovery? (Answer: Both undo AND redo. Steal means uncommitted changes may be on disk → undo needed. No-force means committed changes may not be on disk → redo needed.)
9. Two transactions under snapshot isolation each read rows A and B, then T1 updates A and T2 updates B, violating a constraint on A+B. Which anomaly is this and does SERIALIZABLE prevent it? (Answer: Write skew. Snapshot isolation permits it because the write sets are disjoint. True SERIALIZABLE (e.g., PostgreSQL SSI) detects the dangerous read-write dependency cycle and aborts one transaction.)