Part 3: Transactions, Concurrency & Indexing

1. ACID Properties (The “Gold Standard” for Transactions)

If you are asked about the reliability of a database, you must be able to explain these four pillars:

• Atomicity (“All or Nothing”): A transaction is treated as a single, indivisible unit. If any part fails, the entire transaction is rolled back.
• Mechanism: Write-Ahead Logging (WAL).
• Consistency (“Valid State”): A transaction takes the database from one valid state to another, maintaining all constraints (e.g., a bank balance cannot be negative if a CHECK constraint exists).
• Isolation (“Independent”): Concurrent transactions should not see each other’s “intermediate” or uncommitted work.
• Mechanism: Locking protocols or MVCC (Multi-Version Concurrency Control).
• Durability (“Permanent”): Once a transaction is committed, it stays committed, even in the event of a system crash or power loss.
• Mechanism: Data is flushed to non-volatile storage (disk) or a redo log.

2. Concurrency Anomalies

When multiple transactions run concurrently, they can create “anomalies” if not properly isolated. You should be able to explain these four:

• Dirty Read: A transaction reads data that has been updated by another transaction but not yet committed. If the first transaction rolls back, the second is now working with “garbage” data that never really existed.
• Non-Repeatable Read: A transaction reads the same row twice and gets two different values. This happens because another transaction modified and committed a change to that row in between the two reads.
• Phantom Read: A transaction runs a query to get a set of rows (e.g., WHERE age > 20). Another transaction inserts a new row that fits that criteria. When the first transaction runs the same query again, a “phantom” row appears.
• Lost Update: Two transactions read the same data, both calculate a new value, and both try to update it. The second write overwrites the first, causing the first transaction’s update to be “lost.”

3. Isolation Levels

The DBMS allows you to trade off performance for correctness. Higher isolation levels are safer but slower.

Isolation Level	Dirty Reads	Non-Repeatable Reads	Phantom Reads
Read Uncommitted	Possible	Possible	Possible
Read Committed	Prevented	Possible	Possible
Repeatable Read	Prevented	Prevented	Possible
Serializable	Prevented	Prevented	Prevented

• Read Committed (default in many DBs): ensures you never read uncommitted data.
• Repeatable Read (default in MySQL/InnoDB): a value read once stays the same; prevents non-repeatable reads.
• Serializable (the strongest): the outcome is the same as if transactions ran one after another. Uses range locking to prevent phantom reads.

Ladder to remember: dirty → non-repeatable → phantom, each weaker level allows the next anomaly.

4. Concurrency Control Mechanisms

How does the database actually prevent these anomalies?

• Pessimistic Concurrency Control: Assumes conflicts will happen. It locks data as soon as it is accessed.
• Shared (S) Lock: Used for reading; multiple transactions can hold these.
• Exclusive (X) Lock: Used for writing; only one transaction can hold this.
• Optimistic Concurrency Control: Assumes conflicts are rare. It doesn’t lock data during the transaction. Instead, at the moment of COMMIT, it checks: “Did anyone else change this data while I was working?” If yes, it aborts and retries.
• MVCC (Multi-Version Concurrency Control): Used by PostgreSQL and MySQL (InnoDB). Instead of locking, the database keeps multiple versions of a row. When a user reads, they see a “snapshot” of the data as it existed when their transaction started. This allows readers to never block writers, and writers to never block readers.

5. Two-Phase Locking (2PL) & Serializability

2PL is the mechanism that produces serializable schedules:

• Growing phase: a transaction may acquire locks but not release any.
• Shrinking phase: a transaction may release locks but not acquire any.
• Strict 2PL (what real DBs use): holds all locks until commit — avoids cascading rollbacks.

Conflict serializability is how you verify a schedule is correct. Two operations conflict if they’re from different transactions, touch the same data, and at least one is a write.

Precedence-graph test: draw a node per transaction; add edge Ti → Tj if Ti’s conflicting operation precedes Tj’s. Acyclic graph = conflict-serializable; a cycle = not serializable.

Worked Example

Schedule: T1: r(A)  T2:        w(A)   r(B)          w(B)

Edges: T1 → T2 (T1 reads A before T2 writes A); no edge back. Acyclic → conflict-serializable. If the graph had a cycle (e.g., T2 also wrote a value T1 later reads), the schedule could not be reordered into a serial execution — that schedule can corrupt data.

6. Deadlock vs. Livelock

• Deadlock: Transaction A holds a lock on Table X and wants Y. Transaction B holds a lock on Y and wants X. They are stuck forever.
• Detection: The DBMS uses a Wait-For Graph — a cycle means deadlock. It then kills one transaction (the “victim”) and rolls it back.
• Prevention: lock ordering, timeouts, wait-die / wound-wait schemes.
• Livelock: Two transactions are being “polite.” They both notice a conflict, both back off, and both try again at the exact same time, creating a loop.
• Solution: Introduce randomized delays (back-off) so they don’t retry at the same time.
• Cascading rollback: one transaction’s rollback forces others (that read its uncommitted data) to roll back too — avoided by strict 2PL.

7. Indexing Strategies

An index is like the index at the back of a textbook—it lets you find a specific row without reading the entire table.

• Clustered Index:
• The actual data rows are sorted in the order of the index key.
• You can only have one per table (data can only be physically sorted one way). Usually the Primary Key.
• Non-Clustered Index:
• A separate structure that stores the key and a “pointer” to the actual row location.
• You can have many per table.
• Trade-off: faster reads, slower writes (every table update must also update all non-clustered indexes).
• Sparse vs Dense:
• Dense index: an entry for every record → fast lookup, large index.
• Sparse index: an entry only for some records (works when data is sorted by key) → smaller, may need a short scan.
• B-Tree vs Hash Index:
• B-Tree: maintains sorted data; excellent for range queries (BETWEEN, >, <) and ORDER BY. The default index type.
• Hash Index: exact matches (=) only, O(1) fastest possible lookup, but cannot handle range queries.

8. WAL & Recovery (ARIES)

This is how the database survives a “hard kill” (power outage). The Write-Ahead Log records every change to disk before applying it to the data pages.

1. Redo Phase: Replays all committed transactions from the log to ensure data that was in memory but not on disk is restored.
2. Undo Phase: Rolls back any transactions that were in progress but not finished when the crash occurred, ensuring the database doesn’t stay in a “partial” state.

• Interview line: WAL gives both atomicity (undo) and durability (redo); log must hit disk before the data change.