Transactions Practice Questions

In Wait-Die: if the requesting transaction is OLDER (smaller timestamp) than the holder, it WAITS. If YOUNGER, it DIES (rolls back). $T_1$ has timestamp 5 (older) and $T_2$ has timestamp 10 (younger). Since $T_1$ is older, $T_1$ WAITS.

The fundamental guarantee of the TO protocol is that any schedule it produces is conflict-serializable and is specifically conflict-equivalent to the serial schedule where transactions execute in increasing order of their timestamps (assigned when each transaction begins). This is what makes the protocol correct - it enforces the timestamp ordering as the serialization order.

The TO write rule aborts Ti if: (1) TS(Ti) < R-TS(Q) - a later transaction has already read Q and would not have seen Ti's write, violating the timestamp order; OR (2) TS(Ti) < W-TS(Q) - a later transaction has already written Q, making Ti's write out of order. If neither condition holds, the write executes and W-TS(Q) is updated to TS(Ti).

Strict 2PL requires X locks to be held until commit or abort. $T_1$ holds X locks on $A$ and $B$, commits, then releases - this is exactly Strict 2PL. $T_2$ follows Basic 2PL (acquires S lock, reads, commits, releases). In an actual concurrent schedule, $T_2$ would be blocked from acquiring S(A) while $T_1$ holds X(A).

The edges listed are: $T_1 \to T_3$, $T_2 \to T_3$, $T_2 \to T_4$, $T_3 \to T_4$ - exactly 4 edges. The graph is acyclic (DAG), so the schedule is conflict serializable. One valid serial order: $T_1, T_2, T_3, T_4$.

(A) True - basic TO is deadlock-free; transactions abort instead of waiting. (B) False - Strict 2PL still acquires locks and can deadlock when two transactions wait for each other's locks. (C) True - OCC lets transactions execute freely without locks, validates before commit, and aborts if conflict detected. No waiting → no deadlock. (D) True - Thomas Write Rule is a variant of TO; it still never makes transactions wait, so it remains deadlock-free. (E) False - basic 2PL uses locking and can deadlock via circular wait.

Strict 2PL guarantees conflict serializability and recoverability. Thomas' Write Rule can allow schedules that are view serializable but not conflict serializable.

Conflicts (different transactions, at least one write, same data item): (1) $r_1(A)$ vs $w_2(A)$: $T_1 \to T_2$. (2) $w_2(A)$ vs $w_3(A)$: $T_2 \to T_3$. (3) $r_3(B)$ vs $w_1(B)$: $T_3 \to T_1$... wait: $r_3(B)$ then $w_1(B)$: $T_3 \to T_1$. (4) $w_1(B)$ vs $r_2(B)$: $T_1 \to T_2$. (5) $r_3(B)$ vs ... already counted. Distinct edges: $T_1 \to T_2$, $T_2 \to T_3$, $T_3 \to T_1$, $T_1 \to T_2$ (duplicate). Unique edges: $T_1 \to T_2$, $T_2 \to T_3$, $T_3 \to T_1$. That is 3 edges - and there's a cycle. Let me recount: (1) $r_1(A), w_2(A)$: $T_1 \to T_2$. (2) $w_2(A), w_3(A)$: $T_2 \to T_3$. (3) $r_3(B), w_1(B)$: $T_3 \to T_1$. (4) $w_1(B), r_2(B)$: $T_1 \to T_2$ (dup). Unique = 3. Answer: 3.

(A) False - TO is deadlock-free by design; no waiting means no circular wait. (B) True - a transaction that keeps getting a new (but still small) timestamp may repeatedly encounter the same abort condition, causing starvation/livelock. (C) Partially: cascading rollbacks means an uncommitted transaction's abort forces other transactions to abort - possible in basic TO. But a committed transaction reading aborted-transaction data is a recoverability violation; basic TO can have cascading rollbacks but once committed a transaction's reads are done. The exact phrasing here makes C inaccurate as stated. (D) False - TO guarantees conflict serializability. (E) True - basic TO allows Ti to read data written by Tj even if Tj has not yet committed; if Tj aborts, Ti has read dirty data and must cascade-abort.

(A) True - TO and 2PL allow different (overlapping but incomparable) sets of serializable schedules. (B) True - basic TO always produces conflict-serializable schedules. (C) True - strict TO prevents any transaction from reading or writing uncommitted data, ensuring both recoverability and freedom from cascading rollbacks. (D) True - with Thomas Write Rule, some writes are skipped, producing schedules that are view serializable but not necessarily conflict serializable; this is a classic and frequently tested result. (E) False - basic TO allows a transaction to read data written by an uncommitted transaction (dirty read), which is why cascading rollbacks are possible.

In the TO read rule: if TS(Ti) < W-TS(Q), it means a later transaction Tj (with TS(Tj) > TS(Ti)) has already written Q. Ti is attempting to read a value that has been overwritten in timestamp order, violating serializability. Therefore Ti is aborted and restarted with a new, larger timestamp. TO never makes transactions wait - they either proceed or abort.

Conservative 2PL (pre-claiming) requires a transaction to acquire ALL locks it will ever need before it starts executing. If any lock is unavailable, the transaction waits without holding any locks. This eliminates deadlocks but requires prior knowledge of all data items to be accessed.

Basic 2PL can release X locks before commit, allowing other transactions to read uncommitted (dirty) data. If the writer aborts, the reader must also abort - cascading rollback. Strict 2PL holds X locks until commit, preventing dirty reads and cascading aborts entirely.

(A) True - TO is deadlock-free; no waiting, only abort-or-proceed. (B) True - TO produces conflict-serializable schedules equivalent to a serial order based on timestamps. (C) False - basic TO does not guarantee recoverability; a transaction can read dirty data from an uncommitted transaction, leading to cascading rollbacks on abort. (D) True - a transaction repeatedly restarted may keep encountering the same timestamp conflict causing starvation/livelock. (E) True - Thomas Write Rule ignores obsolete writes instead of aborting, allowing more transactions to complete successfully.

Write rule checks for Ti (TS=5): Is TS(Ti)=5 < R-TS(Q)=3? No (5 > 3). Is TS(Ti)=5 < W-TS(Q)=8? Yes. Under basic TO: both conditions checked - since 5 < 8, Ti is aborted. Under Thomas Write Rule: the condition TS(Ti) < R-TS(Q) is checked first - 5 < 3 is false, so no abort from that. Then TS(Ti) < W-TS(Q) → 5 < 8, but Thomas Write Rule says ignore the write instead of aborting Ti. Ti continues without abort and without updating W-TS(Q).

Trace: (1) T1 write(X): TS=10, R-TS(X)=0, W-TS(X)=0. TS >= R-TS and TS >= W-TS → execute. W-TS(X)=10. (2) T2 write(X): TS=20, R-TS(X)=0, W-TS(X)=10. TS=20 >= 0 and TS=20 >= 10 → execute. W-TS(X)=20. (3) T1 write(X) again: TS=10, R-TS(X)=0, W-TS(X)=20. TS=10 < R-TS(X)=0? No. TS=10 < W-TS(X)=20? Yes → Thomas Write Rule: IGNORE this write. Not executed. Total executions: 2 (first T1 write and T2 write).

(i) Edges: $r_2(A) \to w_1(A)$: $T_2 \to T_1$; $w_1(A) \to w_2(A)$: $T_1 \to T_2$. Cycle - NOT serializable. (ii) Edges: $r_1(A) \to w_2(A)$: $T_1 \to T_2$; $w_1(A) \to w_2(A)$ (dup). Acyclic ($T_1 \to T_2$). Serializable. (iii) Edges: $r_1(A) \to w_2(A)$: $T_1 \to T_2$; $r_2(B) \to w_1(B)$: $T_2 \to T_1$. Cycle - NOT serializable. (iv) Edges: $w_1(B) \to r_2(B)$: $T_1 \to T_2$; $r_1(A) \to w_2(A)$: $T_1 \to T_2$. Acyclic. Serializable. Answer: (ii) and (iv).

The lock point is the point in time at which the transaction has acquired all the locks it needs (end of the growing phase / beginning of the shrinking phase) and holds the maximum number of locks. The serial order of transactions equivalent to a 2PL schedule corresponds to the order of their lock points.