Transactions Practice Questions

View serializability is more general (less strict).

(i) TRUE: In MGL, intention locks are set top-down - acquire IX/IS on ancestors before locking the target node. (ii) TRUE: Locks are released bottom-up - release the leaf lock first, then ancestor intention locks. (iii) FALSE: IS and X on the same node are INCOMPATIBLE. (iv) FALSE: IX and S are INCOMPATIBLE (S means exclusive read of entire subtree; IX means writes below). So (i) and (ii) only.

(i) TRUE: wait-for graph cycle detection is the standard deadlock detection method. (ii) TRUE: Wait-Die and Wound-Wait use timestamps to prevent deadlocks. (iii) TRUE: Conservative 2PL pre-acquires all locks, eliminating deadlocks. (iv) FALSE: Strict 2PL holds locks longer but does NOT prevent deadlocks - it only prevents dirty reads. Transactions can still form wait cycles. So (i), (ii), (iii).

After unlock(A), the shrinking phase has begun. Acquiring lock-X(C) after releasing lock on A violates 2PL - no new locks can be acquired once any lock has been released. The lock-X(C) acquisition must occur before any unlock to comply with 2PL.

(i) Dirty read: possible in Basic 2PL (X locks released early); prevented in Strict 2PL. (ii) Cascading abort: caused by dirty reads - same as above. (iii) Non-repeatable read: can occur in both Basic and Strict 2PL if S locks are released early (Strict only holds X locks). (iv) Lost update: prevented by both since X locks prevent concurrent writes. So (i) and (ii) are prevented by Strict but not Basic 2PL.

In Wound-Wait: if requesting transaction is OLDER, it WOUNDS (preempts) the holder - the holder is rolled back. If YOUNGER, it WAITS. $T_1$ (timestamp 5) is older than $T_2$ (timestamp 10), so $T_1$ wounds $T_2$ - $T_2$ is rolled back and $T_1$ gets the lock.

Rigorous 2PL is the most restrictive (holds all locks until commit), producing the fewest schedules. Strict 2PL is less restrictive (holds only X locks until commit). Basic 2PL is the least restrictive (just requires two phases). So: Rigorous 2PL ⊂ Strict 2PL ⊂ Basic 2PL in terms of allowed schedules.

Write rule check: (1) TS(Ti)=12 < R-TS(Q)=15? Yes → Ti must abort. Since the first condition is already violated, Ti is aborted immediately. The second condition (TS < W-TS) need not even be checked. Ti aborts because a later transaction (with timestamp > 12) has already read Q, and allowing Ti's write would violate timestamp order.

Thomas Write Rule: when Ti issues write(Q) and TS(Ti) < W-TS(Q), a later transaction Tj has already written Q. In a serial execution ordered by timestamps, Ti's write would occur before Tj's and be immediately overwritten, so Ti's write has no observable effect and can be safely skipped. Ti continues without abort. Note: if TS(Ti) < R-TS(Q), the abort still occurs - the Thomas Write Rule does not help in that case.

Trace: (1) T3 read(A): TS=3 >= W-TS(A)=0 → proceed; R-TS(A)=3. (2) T2 write(A): TS=2 < R-TS(A)=3 → ABORT T2. (3) T1 write(A): TS=1 < R-TS(A)=3 → ABORT T1. (4) T3 write(B): TS=3 >= R-TS(B)=0 and TS=3 >= W-TS(B)=0 → proceed; W-TS(B)=3. (5) T1 read(B): T1 is already aborted - not executed. Total aborted: T1 and T2 → 2 transactions.

Under the basic TO write rule, Ti is aborted when TS(Ti) < W-TS(Q) because a later transaction has already written Q. The Thomas Write Rule recognizes that Ti's write is obsolete in this case - it would be immediately overwritten in any serial ordering consistent with timestamps - so Ti's write is safely ignored and Ti is allowed to continue. However, the condition TS(Ti) < R-TS(Q) still causes an abort even under the Thomas Write Rule.

Wait-Die and Wound-Wait are timestamp-based deadlock prevention schemes. Wait-Die: older transaction waits; younger dies (rolls back). Wound-Wait: older wounds (forces rollback of) younger; younger waits. Both assign timestamps at transaction start and use them to resolve conflicts without letting deadlocks form.

Read rule check: TS(Ti) = 5 < W-TS(X) = 3? No (5 > 3) → no abort. Read proceeds. R-TS(X) = max(R-TS(X), TS(Ti)) = max(8, 5) = 8. The R-TS does not decrease - it stays at 8 because a transaction with a larger timestamp (8) had already read X. Note: the read rule only compares TS(Ti) against W-TS(X), not against R-TS(X).

Deadlock requires a cycle of transactions waiting for each other's resources. In the TO protocol, a transaction is never made to wait - if it cannot proceed (due to a timestamp conflict), it is immediately aborted and restarted. Since no transaction waits, no circular wait can form, and deadlock is impossible by design.

$T_2$ (ts=10, younger) requests lock held by $T_1$ (ts=5, older): younger requests from older → $T_2$ DIES. $T_3$ (ts=3, older) requests lock held by $T_2$ (ts=10, younger): older requests from younger → $T_3$ WAITS. Only $T_2$ is rolled back. Answer: 1.

(i) TRUE: Strict 2PL releases S locks before commit; Rigorous holds all. (ii) FALSE: Both Strict and Rigorous 2PL prevent cascading aborts (Strict holds X locks preventing dirty reads; Rigorous holds all). (iii) TRUE: correct distinction. (iv) TRUE: both prevent dirty reads - Strict because X locks prevent others from reading uncommitted writes; Rigorous because all locks held. So (i), (iii), (iv).

In Conservative 2PL, a transaction must acquire ALL its locks before execution. The minimum to allow at least one transaction to start is 2 locks (the number needed by one transaction). If 2 locks are available, at least one transaction can acquire all its needed locks and proceed. Answer: 2.

2PL guarantees conflict serializability - any schedule produced by transactions following 2PL is conflict serializable. However, 2PL does NOT prevent deadlocks (transactions can still hold locks and wait for each other). Deadlock prevention requires additional mechanisms like timestamps or lock ordering.