What are common examiner traps in Transactions and Concurrency Control?

Confusing Read-Read operations as conflicts (Read-Read is non-conflicting). Assuming 2PL prevents deadlocks (Basic 2PL guarantees conflict serializability but NOT deadlock freedom). Assuming a schedule is non-recoverable just because it has dirty reads; it becomes non-recoverable ONLY if the dirty reader commits BEFORE the writer commits. Confusing 'Cascadeless' with 'Strict' (Strict requires write-write to also wait for commit/abort; cascadeless only restricts write-read). Overlooking disconnected nodes in the precedence graph when listing all conflict-equivalent serial schedules in MSQs (unconstrained nodes can be placed anywhere relative to others). Mixing up Wound-Wait (preemptive, older wounds younger) with Wait-Die (non-preemptive, older waits, younger dies). Assuming lost updates violate only Atomicity rather than Isolation and Consistency.

Transactions and Concurrency Control

25 Qs · since 2012 · 40 marks · 1.5 marks/paperMedium yield

Take topic test

Across 2012–2026, Transactions and Concurrency Control in GATE CS is heavily weighted towards testing precedence (serialization) graphs for conflict serializability, schedule class… Guide

Type

GATE CSE 2026 Set 2Q20MCQ1 markEasyConsider concurrent execution of two transactions $T1$ and $T2$ in a DBMS, both of which access a data object $A$ . For these two transactions to not conflict on $A$ , which one of the following statements must be true?
GATE CSE 2025 Set 1Q15MCQ1 markEasyA schedule of three database transactions $T_1$ , $T_2$ , and $T_3$ is shown. $R_i(A)$ and $W_i(A)$ denote read and write of data item $A$ by transaction $T_i, i = 1,2,3$ . The transaction $T_1$ aborts at the end. Which other transaction(s) will be required to be rolled back? $R_1(X) \quad W_1(Y) \quad R_2(X) \quad R_2(Y) \quad R_3(Y) \quad ABORT(T_1)$
GATE CSE 2025 Set 2Q27MSQ1 markMediumAn audit of a banking transactions system has found that on an earlier occasion, two joint holders of account $A$ attempted simultaneous transfers of Rs. 10000 each from account $A$ to account $B$ . Both transactions read the same value, Rs. 11000, as the initial balance in $A$ and were allowed to go through. $B$ …
GATE CSE 2025 Set 2Q53MSQ2 marksMediumDiagramConsider the database transactions T1 and T2, and data items X and Y. Which of the schedule(s) is/are conflict serializable?
GATE CSE 2024 Set 1Q46MSQ2 marksMediumConsider the following read-write schedule $S$ over three transactions $T_1$ , $T_2$ , and $T_3$ , where the subscripts in the schedule indicate transaction IDs: $S: r_1(z); w_1(z); r_2(x); r_3(y); w_3(y); r_2(y); w_2(x); w_2(y);$ Which of the following transaction schedules is/are conflict equivalent to…
GATE CSE 2024 Set 2Q19MCQ1 markEasyOnce the DBMS informs the user that a transaction has been successfully completed, its effect should persist even if the system crashes before all its changes are reflected on disk. This property is called
GATE CSE 2024 Set 2Q27MSQ1 markEasyWhich of the following statements about the Two Phase Locking (2PL) protocol is/are TRUE?
GATE CSE 2022Q39MCQ2 marksMediumLet $R_i(z)$ and $W_i(z)$ denote read and write operations on a data element $z$ by a transaction $T_i$ , respectively. Consider the schedule $S$ with four transactions. $S$ : $R_4(x)R_2(x)R_3(x)R_1(y)W_1(y)W_2(x)W_3(y)R_4(y)$ Which one of the following serial schedules is conflict equivalent to $S$ ?
GATE CSE 2021 Set 1Q13MSQ1 markMediumSuppose a database system crashes again while recovering from a previous crash. Assume checkpointing is not done by the database either during the transactions or during recovery. Which of the following statements is/are correct?
GATE CSE 2021 Set 1Q32MCQ2 marksMediumLet $r_i(z)$ and $w_i(z)$ denote read and write operations respectively on a data item $z$ by a transaction $T_i$ . Consider the following two schedules. $S_1 : r_1(x)\ r_1(y)\ r_2(x)\ r_2(y)\ w_2(y)\ w_1(x)$ $S_2 : r_1(x)\ r_2(x)\ r_2(y)\ w_2(y)\ r_1(y)\ w_1(x)$ Which one of the following options is…
GATE CSE 2021 Set 2Q32MCQ2 marksMediumLet S be the following schedule of operations of three transactions $T_1$ , $T_2$ and $T_3$ in a relational database system: $R_2(Y), R_1(X), R_3(Z), R_1(Y), W_1(X), R_2(Z), W_2(Y), R_3(X), W_3(Z)$ Consider the statements P and Q below: P: S is conflict-serializable. Q: If $T_3$ commits before $T_1$ …
GATE CSE 2020Q37MCQ2 marksMediumDiagramConsider a schedule of transactions $T_1$ and $T_2$ : Here, RX stands for “Read(X)” and WX stands for “Write(X)”. Which one of the following schedules is conflict equivalent to the above schedule?
GATE CSE 2019Q11MCQ1 markMediumConsider the following two statements about database transaction schedules: I. Strict two-phase locking protocol generates conflict serializable schedules that are also recoverable. II. Timestamp-ordering concurrency control protocol with Thomas' Write Rule can generate view serializable schedules that are not…
GATE CSE 2017 Set 1Q42MCQ2 marksMediumIn a database system, unique timestamps are assigned to each transaction using Lamport's logical clock. Let $TS(T_1)$ and $TS(T_2)$ be the timestamps of transactions $T_1$ and $T_2$ respectively. Besides, $T_1$ holds a lock on the resource R, and $T_2$ has requested a conflicting lock on the same resource…
GATE CSE 2017 Set 2Q44NAT2 marksHardTwo transactions $T_1$ and $T_2$ are given as $T_1: r_1(X)w_1(X)r_1(Y)w_1(Y)$ $T_2: r_2(Y)w_2(Y)r_2(Z)w_2(Z)$ where $r_i(V)$ denotes a read operation by transaction $T_i$ on a variable $V$ and $w_i(V)$ denotes a write operation by transaction $T_i$ on a variable $V$ . The total number of conflict…
GATE CSE 2016 Set 1Q22MCQ1 markEasyWhich one of the following is NOT a part of the ACID properties of database transactions?
GATE CSE 2016 Set 1Q51MCQ2 marksMediumConsider the following two phase locking protocol. Suppose a transaction $T$ accesses (for read or write operations), a certain set of objects $\{O_1, \dots, O_k\}$ . This is done in the following manner: Step 1. $T$ acquires exclusive locks to $O_1, \dots, O_k$ in increasing order of their addresses. Step 2.…
GATE CSE 2016 Set 2Q22MCQ1 markEasySuppose a database schedule $S$ involves transactions $T_1, \ldots, T_n$ . Construct the precedence graph of $S$ with vertices representing the transactions and edges representing the conflicts. If $S$ is serializable, which one of the following orderings of the vertices of the precedence graph is guaranteed to…
GATE CSE 2016 Set 2Q51MCQ2 marksMediumConsider the following database schedule with two transactions, $T_1$ and $T_2$ . $S = r_2(X); r_1(X); r_2(Y); w_1(X); r_1(Y); w_2(X); a_1; a_2$ where $r_i(Z)$ denotes a *read* operation by transaction $T_i$ on a variable $Z$ , $w_i(Z)$ denotes a *write* operation by $T_i$ on a variable $Z$ and $a_i$ …
GATE CSE 2015 Set 2Q1MCQ1 markEasyConsider the following transaction involving two bank accounts $x$ and $y$ . read(x) ; x := x - 50; write(x) ; read(y) ; y:= y + 50; write(y) The constraint that the sum of the accounts $x$ and $y$ should remain constant is that of
GATE CSE 2015 Set 3Q29MCQ2 marksMediumDiagramConsider the following partial Schedule $S$ involving two transactions $T1$ and $T2$ . Only the read and the write operations have been shown. The read operation on data item $P$ is denoted by $read(P)$ and the write operation on data item $P$ is denoted by $write(P)$ . Suppose that the transaction $T1$ …
GATE CSE 2014 Set 1Q29MCQ2 marksMediumConsider the following four schedules due to three transactions (indicated by the subscript) using $read$ and $write$ on a data item $x$ , denoted by $r(x)$ and $w(x)$ respectively. Which one of them is conflict serializable?
GATE CSE 2014 Set 2Q29MCQ2 marksMediumDiagramConsider the following schedule $\mathbf{S}$ of transactions T1, T2, T3, T4: Which one of the following statements is CORRECT?
GATE CSE 2014 Set 3Q29MCQ2 marksMediumConsider the transactions T1, T2, and T3 and the schedules S1 and S2 given below. T1: r1(X); r1(Z); w1(X); w1(Z)T2: r2(Y); r2(Z); w2(Z)T3: r3(Y); r3(X); w3(Y)S1: r1(X); r3(Y); r3(X); r2(Y); r2(Z); w3(Y); w2(Z); r1(Z); w1(X); w1(Z)…
GATE CSE 2012Q27MCQ2 marksMediumConsider the following transactions with data items $P$ and $Q$ initialized to zero: $T_1$ : read (P);read (Q);if P = 0 then Q := Q + 1 ;write (Q). $T_2$ : read (Q);read (P);if Q = 0 then P := P + 1 ;write (P).…

Topic guide

What does GATE test in Transactions and Concurrency Control?

Across 2012–2026, Transactions and Concurrency Control in GATE CS is heavily weighted towards testing precedence (serialization) graphs for conflict serializability, schedule classification (recoverable, cascadeless, strict), and locking/timestamping protocol mechanics. Questions frequently present interleaved schedules and require students to identify conflict edges, count valid topological orders, or detect recovery anomalies such as dirty reads and cascading rollbacks. Recent exams (2021–2025) feature multiple MSQs testing theoretical invariants of Two-Phase Locking (2PL), deadlock prevention protocols (Wait-Die, Wound-Wait), and real-world ACID violations.

Core concepts

Conflict operations (R-W, W-R, W-W on the same variable by distinct transactions)
Precedence (serialization) graph construction and cycle detection
Topological sorting to obtain conflict-equivalent serial schedules
Hierarchy of schedules: Strict Cascadeless Recoverable All schedules
Dirty read anomaly and cascading rollbacks upon abort
Two-Phase Locking (Basic 2PL, Strict 2PL, Rigorous 2PL, Conservative 2PL)
Deadlock prevention schemes: Wait-Die vs Wound-Wait timestamp ordering
Thomas' Write Rule and View Serializability
ACID properties (Atomicity, Consistency, Isolation, Durability) and anomaly mappings (Lost Update, Inconsistent Analysis)
Idempotency of Redo and Undo operations in log-based crash recovery

Recurring question patterns

Precedence Graph Cycle Detection & Equivalent Serial Order
common · MCQ · 2 marks · 2025, 2024, 2022, 2021
Given one or more transaction schedules with interleaved $r_i(X)$ and $w_i(X)$ operations, determine conflict serializability by constructing the precedence graph and/or find the conflict equivalent serial schedule(s) via topological sorting.
Schedule Recoverability and Cascading Aborts Analysis
common · MCQ · 2 marks · 2025, 2021, 2016, 2015
Given an execution sequence with commit/abort events, analyze whether dirty reads occur ( $W_i(X) \to R_j(X)$ without commit), determine if the schedule is recoverable ( $T_i$ commits before $T_j$ ), cascadeless, or strict, and identify required cascading rollbacks.
Properties of Concurrency Control Protocols (2PL & Timestamps)
common · MSQ · 1 marks · 2024, 2019, 2017, 2016
Conceptual evaluation (often in MSQ or 2-statement format) of 2PL variants (Basic, Strict, Rigorous, Conservative), address-ordered locking for deadlock freedom, Thomas' Write Rule generating view serializable schedules, or Wait-Die / Wound-Wait schemes.
ACID Properties & Concurrency Anomalies
occasional · MCQ · 1 marks · 2025, 2024, 2016, 2015
Application scenarios (e.g., banking transfers, lost updates, uncommitted reads) mapping anomalies to specific ACID property violations (Atomicity, Consistency, Isolation, Durability).
Combinatorial Interleaving & Serializability Counting
rare · NAT · 2 marks · 2017
Counting the total number of conflict serializable schedules out of all possible interleavings $\binom{n_1 + n_2}{n_1}$ by finding cycle-inducing relative orders.
Log-Based Recovery & Crash Semantics
rare · MSQ · 1 marks · 2021
Analyzing behavior of DBMS crash recovery, idempotency of undo/redo actions, and state preservation when crashes occur during recovery without checkpoints.

Formulas GATE uses

Total Interleavings of Two Transactions

\text{Total Schedules} = \binom{n_1 + n_2}{n_1} = \frac{(n_1 + n_2)!}{n_1! \, n_2!}

Used when counting total possible concurrent schedules formed by two transactions of length $n_1$ and $n_2$ operations preserving intra-transaction order.

Conflict Condition Definition

(O_i(X), O_j(X)) \text{ is in conflict iff } T_i \neq T_j \land (O_i = \text{Write} \lor O_j = \text{Write})

Used to add directed edges $T_i \to T_j$ in a precedence graph whenever $O_i(X)$ appears before $O_j(X)$ in schedule $S$ .

Recoverability Rule

\forall T_i, T_j \; [W_i(X) <_S R_j(X) \implies C_i <_S C_j]

Used to check whether a schedule is recoverable by verifying that the writer transaction $T_i$ commits before the reader transaction $T_j$ commits.

Cascadelessness Rule (Avoids Cascading Aborts)

\forall T_i, T_j \; [W_i(X) <_S R_j(X) \implies C_i <_S R_j(X)]

Used to verify that every read operation only reads committed data (no dirty reads).

Strict Schedule Rule

\forall T_i, T_j \; [W_i(X) <_S O_j(X) \implies (C_i <_S O_j(X) \lor A_i <_S O_j(X))] \text{ where } O_j \in \{R_j, W_j\}

Used to verify that no transaction reads or overwrites uncommitted written data.

Examiner traps in Transactions and Concurrency Control

Confusing Read-Read operations as conflicts (Read-Read is non-conflicting).
Assuming 2PL prevents deadlocks (Basic 2PL guarantees conflict serializability but NOT deadlock freedom).
Assuming a schedule is non-recoverable just because it has dirty reads; it becomes non-recoverable ONLY if the dirty reader commits BEFORE the writer commits.
Confusing 'Cascadeless' with 'Strict' (Strict requires write-write to also wait for commit/abort; cascadeless only restricts write-read).
Overlooking disconnected nodes in the precedence graph when listing all conflict-equivalent serial schedules in MSQs (unconstrained nodes can be placed anywhere relative to others).
Mixing up Wound-Wait (preemptive, older wounds younger) with Wait-Die (non-preemptive, older waits, younger dies).
Assuming lost updates violate only Atomicity rather than Isolation and Consistency.

How questions are asked

Given a schedule string, determine if it is conflict serializable and/or recoverable
Select all conflict-equivalent serial orders from a given set (MCQ/MSQ)
Match locking/timestamping protocols to their guarantees (serializability, deadlock-freedom, starvation-freedom)
Count the number of conflict serializable schedules using combinatorics (NAT)
Identify which transactions must cascade-abort when a specific transaction fails
Scenario-based identification of violated ACID properties upon a concurrent failure

Paper trends

Shift from single-answer MCQs identifying a unique serial order to MSQs where multiple serial orders are valid due to disconnected DAG components or independent transactions.
2024, 2022
Increased focus on multi-concept MSQs combining 2PL phase rules, deadlock possibilities, and transaction abort ripple effects (cascading rollbacks).
2025, 2024
Contextual scenario-based questions (e.g., banking system audit logs) testing nuanced distinctions between Isolation and Consistency violations rather than pure rote definitions.
2025, 2015

Difficulty notes

Easy: Direct definition matching of ACID properties, identifying conflict pairs ( $R-W, W-R, W-W$ ), or checking 2-node precedence graphs for cycles. Medium: Multi-transaction (3 or 4 transactions) precedence graphs with branching topological orders, classifying schedules across the hierarchy (Strict vs Cascadeless vs Recoverable), or evaluating 2PL / Wound-Wait protocol claims in MSQ format. Hard: Combinatorial enumeration (NAT) of non-serializable interleavings against total permutations $\binom{\sum n_i}{n_1, n_2, \dots}$ or subtle view serializability edge cases involving blind writes.

Transactions and Concurrency Control

25 Qs · since 2012 · 40 marks · 1.5 marks/paperMedium yield

Take topic test

Across 2012–2026, Transactions and Concurrency Control in GATE CS is heavily weighted towards testing precedence (serialization) graphs for conflict serializability, schedule class… Guide

Type

Topic guide

What does GATE test in Transactions and Concurrency Control?

Core concepts

Conflict operations (R-W, W-R, W-W on the same variable by distinct transactions)
Precedence (serialization) graph construction and cycle detection
Topological sorting to obtain conflict-equivalent serial schedules
Hierarchy of schedules: Strict Cascadeless Recoverable All schedules
Dirty read anomaly and cascading rollbacks upon abort
Two-Phase Locking (Basic 2PL, Strict 2PL, Rigorous 2PL, Conservative 2PL)
Deadlock prevention schemes: Wait-Die vs Wound-Wait timestamp ordering
Thomas' Write Rule and View Serializability
ACID properties (Atomicity, Consistency, Isolation, Durability) and anomaly mappings (Lost Update, Inconsistent Analysis)
Idempotency of Redo and Undo operations in log-based crash recovery

Recurring question patterns

Precedence Graph Cycle Detection & Equivalent Serial Order
common · MCQ · 2 marks · 2025, 2024, 2022, 2021
Given one or more transaction schedules with interleaved $r_i(X)$ and $w_i(X)$ operations, determine conflict serializability by constructing the precedence graph and/or find the conflict equivalent serial schedule(s) via topological sorting.
Schedule Recoverability and Cascading Aborts Analysis
common · MCQ · 2 marks · 2025, 2021, 2016, 2015
Given an execution sequence with commit/abort events, analyze whether dirty reads occur ( $W_i(X) \to R_j(X)$ without commit), determine if the schedule is recoverable ( $T_i$ commits before $T_j$ ), cascadeless, or strict, and identify required cascading rollbacks.
Properties of Concurrency Control Protocols (2PL & Timestamps)
common · MSQ · 1 marks · 2024, 2019, 2017, 2016
Conceptual evaluation (often in MSQ or 2-statement format) of 2PL variants (Basic, Strict, Rigorous, Conservative), address-ordered locking for deadlock freedom, Thomas' Write Rule generating view serializable schedules, or Wait-Die / Wound-Wait schemes.
ACID Properties & Concurrency Anomalies
occasional · MCQ · 1 marks · 2025, 2024, 2016, 2015
Application scenarios (e.g., banking transfers, lost updates, uncommitted reads) mapping anomalies to specific ACID property violations (Atomicity, Consistency, Isolation, Durability).
Combinatorial Interleaving & Serializability Counting
rare · NAT · 2 marks · 2017
Counting the total number of conflict serializable schedules out of all possible interleavings $\binom{n_1 + n_2}{n_1}$ by finding cycle-inducing relative orders.
Log-Based Recovery & Crash Semantics
rare · MSQ · 1 marks · 2021
Analyzing behavior of DBMS crash recovery, idempotency of undo/redo actions, and state preservation when crashes occur during recovery without checkpoints.

Formulas GATE uses

Total Interleavings of Two Transactions

\text{Total Schedules} = \binom{n_1 + n_2}{n_1} = \frac{(n_1 + n_2)!}{n_1! \, n_2!}

Used when counting total possible concurrent schedules formed by two transactions of length $n_1$ and $n_2$ operations preserving intra-transaction order.

Conflict Condition Definition

(O_i(X), O_j(X)) \text{ is in conflict iff } T_i \neq T_j \land (O_i = \text{Write} \lor O_j = \text{Write})

Used to add directed edges $T_i \to T_j$ in a precedence graph whenever $O_i(X)$ appears before $O_j(X)$ in schedule $S$ .

Recoverability Rule

\forall T_i, T_j \; [W_i(X) <_S R_j(X) \implies C_i <_S C_j]

Used to check whether a schedule is recoverable by verifying that the writer transaction $T_i$ commits before the reader transaction $T_j$ commits.

Cascadelessness Rule (Avoids Cascading Aborts)

\forall T_i, T_j \; [W_i(X) <_S R_j(X) \implies C_i <_S R_j(X)]

Used to verify that every read operation only reads committed data (no dirty reads).

Strict Schedule Rule

\forall T_i, T_j \; [W_i(X) <_S O_j(X) \implies (C_i <_S O_j(X) \lor A_i <_S O_j(X))] \text{ where } O_j \in \{R_j, W_j\}

Used to verify that no transaction reads or overwrites uncommitted written data.

Examiner traps in Transactions and Concurrency Control

Confusing Read-Read operations as conflicts (Read-Read is non-conflicting).
Assuming 2PL prevents deadlocks (Basic 2PL guarantees conflict serializability but NOT deadlock freedom).
Assuming a schedule is non-recoverable just because it has dirty reads; it becomes non-recoverable ONLY if the dirty reader commits BEFORE the writer commits.
Confusing 'Cascadeless' with 'Strict' (Strict requires write-write to also wait for commit/abort; cascadeless only restricts write-read).
Overlooking disconnected nodes in the precedence graph when listing all conflict-equivalent serial schedules in MSQs (unconstrained nodes can be placed anywhere relative to others).
Mixing up Wound-Wait (preemptive, older wounds younger) with Wait-Die (non-preemptive, older waits, younger dies).
Assuming lost updates violate only Atomicity rather than Isolation and Consistency.

How questions are asked

Given a schedule string, determine if it is conflict serializable and/or recoverable
Select all conflict-equivalent serial orders from a given set (MCQ/MSQ)
Match locking/timestamping protocols to their guarantees (serializability, deadlock-freedom, starvation-freedom)
Count the number of conflict serializable schedules using combinatorics (NAT)
Identify which transactions must cascade-abort when a specific transaction fails
Scenario-based identification of violated ACID properties upon a concurrent failure

Paper trends

Shift from single-answer MCQs identifying a unique serial order to MSQs where multiple serial orders are valid due to disconnected DAG components or independent transactions.
2024, 2022
Increased focus on multi-concept MSQs combining 2PL phase rules, deadlock possibilities, and transaction abort ripple effects (cascading rollbacks).
2025, 2024
Contextual scenario-based questions (e.g., banking system audit logs) testing nuanced distinctions between Isolation and Consistency violations rather than pure rote definitions.
2025, 2015