GK One-Line Question & Answer

A wait-for graph has one node per transaction and a directed edge T1 to T2 if T1 is waiting for a lock held by T2; a cycle in this graph indicates a deadlock; DBMS resolves by selecting a victim transaction to abort (typically the youngest cheapest or least-work-done transaction)

Ensuring deadlocks cannot occur by design without needing to detect them: (1) Wait-Die: older transaction waits younger dies/restarts; (2) Wound-Wait: older transaction wounds (forces rollback of) younger younger waits; (3) Lock ordering: all transactions acquire locks in predefined order (no circular waits possible)

Locking all rows satisfying a predicate (not just currently existing rows) to prevent phantom reads - e.g. locking all rows WHERE salary > 50000 prevents any insertion of a new row with salary=60000 by another transaction; theoretically necessary because row-level locks cannot prevent phantom insertions

A lock on the gap between index values that prevents other transactions from inserting new rows into that gap - used by InnoDB REPEATABLE READ to prevent phantom reads by locking the index ranges between existing values

A combination of a gap lock + record lock that locks both the index record AND the gap before it; used as the standard locking unit in InnoDB for REPEATABLE READ - e.g. next-key lock on value 20 locks the record 20 AND the gap (10 20)

MVCC: readers never block writers and writers never block readers (readers see old versions writers create new versions); Lock-based: readers block writers (S-lock) and writers block readers and writers (X-lock). MVCC provides higher read concurrency but uses more storage for multiple versions

A concurrency control method that builds the conflict serialization graph in real-time; commits the transaction only if its addition to the graph does not create a cycle (ensuring the resulting schedule is serializable); aborts if a cycle would be created

Centralized: all lock requests go to one lock manager node (simple consistent but single point of failure and bottleneck). Distributed: lock management responsibility spread across nodes (better scalability and fault tolerance but complex coordination and potential split-brain issues)

Deadlock: transactions are stuck waiting indefinitely (no progress possible). Livelock: transactions are active (not blocked) but keep aborting and restarting in response to each other without making progress - e.g. two transactions using Wait-Die that repeatedly abort each other

Strict 2PL holds ALL locks (both read and write) until the transaction commits or aborts instead of releasing write locks early. This prevents: cascading rollbacks (no dirty reads possible as uncommitted data is always locked) and simplifies recovery (undo only affects the aborting transaction)

Three phases: Read (execute locally no locks reads from database writes to private workspace); Validate (check if any committed transaction since start wrote to data this transaction read); Write (apply local workspace to database if validation passed)

A schedule is conflict-serializable if it is equivalent to some serial schedule; tested by building the conflict graph: edge Ti to Tj if Ti performs an operation conflicting with a later operation by Tj (both access same data item at least one is a write); schedule is conflict-serializable iff graph is acyclic

View serializability is a broader criterion: a schedule S is view-serializable if it is view-equivalent to some serial schedule (same transactions read the same values and produce the same final writes). Every conflict-serializable schedule is view-serializable but NOT vice versa

A policy where a transaction immediately aborts if any requested lock is not immediately available (rather than waiting) then restarts - eliminates deadlocks by eliminating the hold and wait condition; appropriate for: short transactions high-contention workloads where waiting is rarely productive and systems where fast retry is acceptable

A situation where a transaction is indefinitely prevented from acquiring a lock because other transactions continuously acquire the same lock preventing the waiting transaction from ever proceeding; prevented by: FIFO queuing for lock requests priority aging (waiting transactions gain priority over time)

Deliberately using a lower isolation level than SERIALIZABLE to improve performance; safe when: the application can tolerate specific anomalies (e.g. approximate counts where phantom reads are acceptable) or when transactions are read-only (no write skew possible) or when application-level controls compensate

New rows satisfying a predicate can be inserted by other transactions after the predicate is evaluated causing re-evaluation to return different rows - row-level locking cannot prevent this because the new rows do not exist yet when locks are acquired (cannot lock non-existent rows)

A concurrency control combining 2PL with two versions of data: write transactions use 2PL to synchronize with each other but read transactions read older committed versions (not the newest possibly-being-written version) allowing reads to proceed without waiting for write locks

A concurrency control combining MVCC with timestamp ordering: each write creates a new version with the writing transactions timestamp; reads access the latest version with a timestamp less than or equal to the reading transactions timestamp without blocking; conflicts resolved through timestamp ordering rules

An algorithm that detects and prevents write skew anomalies while still using snapshot isolation for reads (avoiding lock-based blocking); it tracks anti-dependency (rw) edges in the transaction graph and aborts transactions that would create dangerous structures (concurrent cycles of rw-anti-dependencies)

A recoverable schedule ensures that if a transaction Ti reads data written by Tj then Tj must commit before Ti commits (preventing dirty read scenario from corrupting committed data). A non-recoverable schedule allows Ti to commit before Tj commits - if Tj then aborts Ti cannot be rolled back even though it read uncommitted data creating a permanent corruption

A schedule avoids cascading aborts (ACA) if transactions only read values written by COMMITTED transactions - even if those committed transactions read from other uncommitted transactions. ACA is stronger than recoverability but weaker than strict schedules; ACA schedules never require cascading rollbacks

Isolation levels impose schedules with specific properties: READ UNCOMMITTED may produce non-recoverable schedules. READ COMMITTED produces ACA schedules (reads only committed data). REPEATABLE READ produces ACA schedules and additionally prevents non-repeatable reads. SERIALIZABLE produces strict schedules (only committed data read held until commit) and conflict-serializable execution histories

Four necessary conditions: (1) Mutual exclusion: resources held exclusively. (2) Hold and wait: transaction holds resources while waiting for more. (3) No preemption: resources cannot be forcibly taken. (4) Circular wait: cycle in the wait-for graph. ALL four must hold simultaneously

If requesting transaction Ti is OLDER than holding transaction Tj: Ti waits. If Ti is YOUNGER than Tj: Ti dies (aborts and restarts with original timestamp). Older transactions always wait; younger ones abort - ensures no circular wait since age ordering is consistent

If requesting transaction Ti is OLDER than holding Tj: Ti wounds Tj (forces Tj to abort). If Ti is YOUNGER than Tj: Ti waits. Older transactions are aggressive (preempt younger); younger transactions wait - opposite aggressiveness pattern from wait-die

Establishing a total ordering on all lockable resources and requiring ALL transactions to acquire locks in that predefined order; since every transaction acquires locks in the same order no circular wait can form

O(T + E) using DFS-based cycle detection (Depth-First Search marks visited nodes and detects back edges indicating cycles in the directed graph)

Choosing which deadlocked transaction to abort to break the deadlock; criteria: (1) minimum rollback cost (least work done) (2) youngest transaction (least invested time) (3) fewest locks held (4) starvation avoidance (do not repeatedly select the same transaction as victim)

A deadlock spanning multiple database nodes where the wait-for cycle crosses node boundaries; harder to detect because: each node only sees local waits no single node has complete global wait-for graph and communication delays can cause false deadlock detection or missed deadlocks

A false positive in distributed deadlock detection: the system detects a cycle in the global wait-for graph but by the time it acts on the detection the deadlock has already resolved (a transaction committed naturally) leading to unnecessary transaction aborts

Aborting a transaction if it has been waiting for a lock longer than a specified timeout period assuming it may be deadlocked; trade-offs: simple to implement no detection overhead but may abort non-deadlocked transactions (false positives) and may take long to detect actual deadlocks

Nodes proactively push probe messages along wait-for edges toward the transaction being waited for; if a probe returns to its origin a cycle (deadlock) is detected; avoids the need for a centralized global wait-for graph

Deadlock prevention eliminates one of the Coffman conditions (no advance knowledge needed). Deadlock avoidance requires each transaction to declare maximum resource needs in advance; the system uses this to determine if granting a request could lead to deadlock and denies unsafe requests

Coarser granularity (table locks): fewer locks per transaction = fewer potential conflicts = fewer deadlocks but less concurrency. Finer granularity (row locks): more locks per transaction = more potential for circular wait = higher deadlock probability but higher concurrency

Best practices: (1) Acquire locks in consistent order across all transactions. (2) Keep transactions short (fewer locks held for less time). (3) Access data in same order. (4) Use appropriate isolation level. (5) Use SELECT FOR UPDATE to acquire all needed locks upfront. (6) Retry logic for deadlock errors

2PL guarantees serializability but does NOT prevent deadlocks; in fact 2PL can cause deadlocks because transactions hold locks during the shrinking phase while waiting for new locks - deadlock prevention or detection must be combined with 2PL separately

A visual representation of transactions as nodes and lock wait relationships as directed edges; cycles indicate deadlocks; helps identify: which transactions are involved which specific rows/tables are the contention points what SQL statements caused conflicts and patterns suggesting application-level fixes

InnoDB has automatic deadlock detection using a wait-for graph; when detected the transaction with less undo log is chosen as victim and rolled back; deadlock information is accessible via SHOW ENGINE INNODB STATUS or the performance_schema.data_lock_waits table

Mutual exclusion means resources (data items) can only be held by one transaction at a time in write mode; for READ locks mutual exclusion can be eliminated (multiple readers allowed) via shared locks reducing deadlock probability; but write locks inherently require mutual exclusion for correctness