GK One-Line Question & Answer

The X/Open XA specification for distributed transaction processing: defines an interface between a transaction manager (TM) and resource managers (RM/databases) enabling global transactions that span multiple databases message queues and other XA-compliant resources using 2PC coordination

Immediate write: changes are written to disk as soon as they occur (easier recovery more I/O). Deferred write: changes are kept in memory (buffer pool) and written to disk lazily (batch I/O better performance). WAL is written immediately for durability; data pages use deferred write (buffered writes with WAL ensuring recovery)

REPEATABLE READ prevents dirty reads and non-repeatable reads (same row read twice returns same value within a transaction by holding read locks or using MVCC snapshots) but in standard SQL REPEATABLE READ allows phantom reads - though MySQL InnoDB also prevents phantoms via gap locks

ACID (Atomicity Consistency Isolation Durability) was formalized by Jim Gray and Andreas Reuter in 1992 in their book Transaction Processing: Concepts and Techniques though the individual concepts were discussed earlier by Eswaran et al in 1976 (regarding consistency and isolation) and Gray in 1978 (regarding transaction properties)

Redo log: records the AFTER-image (new value) of each change enabling REDO (replay) of committed transactions during crash recovery to bring the database to the committed state. Undo log: records the BEFORE-image (original value) of each change enabling ROLLBACK of uncommitted transactions and MVCC snapshots for concurrent readers

A nested transaction is a transaction started within another transaction; in most DBMS true nested transactions are not supported but SAVEPOINTs provide similar functionality - a ROLLBACK TO SAVEPOINT is analogous to rolling back an inner transaction while keeping the outer transaction alive

A hierarchical locking mechanism: Intention Shared (IS) and Intention Exclusive (IX) are set on higher-level objects (table page) to signal intent to lock rows within them - this avoids scanning all row-level locks to check table-level lock compatibility making table-level lock checks O(1) instead of O(rows)

When a transaction acquires too many fine-grained locks (row/page level) the DBMS automatically escalates to a coarser-grained lock (table level) to reduce lock management overhead - reduces memory used for lock structures at the cost of reduced concurrency

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