Solving Transaction Problems in DBMS Interviews

In database system interviews, few challenges are as revealing as schedule analysis problems. Presented with a sequence of read and write operations from multiple concurrent transactions, you must determine whether the execution is correct, identify potential anomalies, and understand the subtle interplay between isolation, consistency, and performance.

Schedule analysis is the foundation of all transaction-related interview problems. Before you can test for serializability, analyze locking behavior, or detect deadlocks, you must first be able to read and interpret transaction schedules with precision. This page builds that foundational skill systematically.

A transaction schedule (also called a history) is a sequence of operations from one or more transactions that represents a particular interleaving of their execution. Understanding schedules requires mastering their components, notation, and the constraints that govern valid schedules.

Transactions and Operations

A transaction is a logical unit of work comprising a sequence of database operations. Each transaction has a unique identifier (T₁, T₂, etc.) and consists of:

• Read operations: R_i(X) — Transaction T_i reads data item X
• Write operations: W_i(X) — Transaction T_i writes data item X
• Commit: C_i — Transaction T_i successfully completes
• Abort: A_i — Transaction T_i is rolled back

A schedule interleaves these operations while preserving the internal order of operations within each transaction. This internal ordering constraint is fundamental—a schedule cannot reorder operations from the same transaction.

Schedule Notation Systems

Different textbooks and interview problems use varying notations. The ability to fluently translate between them demonstrates mastery:

Subscript notation (most common in academia):

R₁(A) W₁(A) R₂(A) W₂(A) C₁ C₂

Functional notation:

read(T1, A) write(T1, A) read(T2, A) write(T2, A) commit(T1) commit(T2)

Tabular notation (common in interviews):

Time  T1      T2
1     R(A)
2     W(A)
3             R(A)
4             W(A)
5     Commit
6             Commit

Shorthand notation:

r1[A] w1[A] r2[A] w2[A] c1 c2

Understanding the distinction between complete and partial schedules is crucial for interview problem-solving. Many problems present partial schedules and ask you to reason about possible completions.

Complete Schedules

A schedule S is complete if and only if:

1. All operations included: For every transaction T_i participating in S, all operations of T_i appear in S
2. Termination for all: Every transaction either commits (C_i) or aborts (A_i)
3. Abort semantics respected: If T_i aborts, no other transaction reads values written by T_i (unless cascading aborts are explicitly permitted)

Partial Schedules

A partial schedule represents an incomplete execution—transactions may have pending operations or may not have terminated. Interview problems often present partial schedules to test your ability to:

• Identify what operations are still pending
• Determine if the partial schedule can be completed correctly
• Analyze whether conflicts can be resolved through different completion orderings

Serial Schedules: The Correctness Baseline

A serial schedule is one where transactions execute one at a time—there's no interleaving. For n transactions, there are n! possible serial schedules. Serial schedules are trivially correct because each transaction sees a consistent database state.

Example of serial schedules for T₁ and T₂:

Serial order T₁ → T₂:

R₁(A) W₁(A) R₁(B) C₁ R₂(A) W₂(A) C₂

Serial order T₂ → T₁:

R₂(A) W₂(A) C₂ R₁(A) W₁(A) R₁(B) C₁

Serial schedules serve as the gold standard for correctness. We consider concurrent schedules correct if they produce results equivalent to some serial schedule—this is the foundation of serializability theory.

Conflict identification is the core skill of schedule analysis. Two operations are said to conflict if they satisfy ALL of the following conditions:

1. Different transactions: They belong to different transactions (T_i ≠ T_j)
2. Same data item: They access the same data item (both operate on X)
3. At least one is a write: At least one operation is a write

This means there are exactly three types of conflicts:

Non-Conflicting Operations

Critically, Read-Read (RR) operations do NOT conflict, even on the same data item by different transactions. Reads don't modify state, so their relative ordering doesn't affect the final outcome.

This distinction is frequently tested in interviews:

R₁(A) R₂(A)  ← NOT a conflict (both reads)
R₁(A) W₂(A)  ← IS a conflict (read-write, same item, different transactions)
W₁(A) W₁(B)  ← NOT a conflict (same transaction)
W₁(A) W₂(B)  ← NOT a conflict (different data items)

Beyond identifying conflicts, senior-level schedule analysis requires tracing data values through the schedule. This skill is essential for understanding anomalies and verifying correctness.

The Data Flow Trace Technique

To trace data flow through a schedule:

1. Initialize values: Assign initial values to all data items (often provided or assumed)
2. Process chronologically: Walk through the schedule operation by operation
3. Track reads and writes: For each read, note what value is read; for each write, note the new value
4. Identify dependencies: Note which transactions' writes affect which transactions' reads

This technique reveals the actual data relationships that determine whether a schedule's outcome matches a serial execution.

Reads-From Relationship

The reads-from relationship captures data dependencies between transactions. We say transaction T_j reads-from transaction T_i on data item X if:

1. T_i writes X before T_j reads X in the schedule
2. No other transaction writes X between T_i's write and T_j's read

This relationship is fundamental to understanding schedule correctness. When T_j reads-from T_i, T_j's behavior depends on T_i's write.

Notation: T_j reads X from T_i, or RF(T_i, T_j, X)

The Initial Transaction (T₀)

For analysis purposes, we often define a hypothetical initial transaction T₀ that wrote all initial values. This simplifies reads-from analysis—if a transaction reads a value that no other transaction has written, it reads-from T₀.

Schedule analysis problems often require identifying specific anomalies that indicate isolation violations. Each anomaly has a characteristic pattern that, once internalized, becomes instantly recognizable.

The Classic Anomalies

These four anomalies form the basis of isolation level definitions and are frequently tested in interviews:

Anomaly Detection Technique

To systematically detect anomalies in a schedule:

1. List all reads: For each read, identify what value is being read and from which write
2. Check for dirty reads: Does any read get a value from a transaction that later aborts?
3. Check for non-repeatable reads: Does any transaction read the same item twice with different values?
4. Check for lost updates: Are there RR-WW patterns on the same item from different transactions?
5. Check for phantoms: Are there range queries that could be affected by concurrent inserts/deletes?

When facing schedule analysis problems in interviews, follow this systematic approach to demonstrate both competence and methodical thinking.

The Five-Step Schedule Analysis Protocol

Let's practice with a more complex schedule that tests your ability to apply all concepts covered.

Problem Statement

Given the following schedule S involving three transactions, perform complete analysis:

S: R₁(A) R₂(B) W₁(A) R₃(A) W₂(B) R₃(B) W₃(A) W₃(B) C₁ C₂ C₃

Transaction definitions:

• T₁: Read A, Write A (double it)
• T₂: Read B, Write B (add 10)
• T₃: Read A, Read B, Write A = A+B, Write B = A-B

Solution

Conflict Analysis:

On data item A:

• W₁(A) → R₃(A): WR conflict
• W₁(A) → W₃(A): WW conflict
• R₃(A) → (nothing after by other T): No additional conflict

On data item B:

• W₂(B) → R₃(B): WR conflict
• W₂(B) → W₃(B): WW conflict

Total conflicts: 4

Data Flow (assuming initial A=10, B=5):

Final state: A = 35, B = 5

Anomalies: None detected - All reads occur after the writes they depend on are complete, and no aborts occur.

Schedule analysis is the foundation upon which all transaction-related problem-solving rests. Let's consolidate the essential skills:

What's Next:

With schedule analysis mastered, we'll move to Serializability Testing—the formal methods for determining whether a given schedule is correct (equivalent to some serial schedule). You'll learn the precedence graph construction technique, conflict serializability testing, and view serializability fundamentals.