Transaction states in DBMS Theory - Time & Space Complexity

Time Complexity: Transaction states

O(n)

Understanding Time Complexity

When working with transactions in a database, it is important to understand how the time taken changes as the transaction moves through different states.

We want to know how the processing time grows as the transaction progresses from start to finish.

Scenario Under Consideration

Analyze the time complexity of the following transaction state changes.

BEGIN TRANSACTION;
-- Perform several SQL operations
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
UPDATE accounts SET balance = balance + 100 WHERE id = 2;
COMMIT;

This snippet shows a simple transaction that updates two accounts and then commits the changes.

Identify Repeating Operations

Look for repeated steps or operations that affect time.

• Primary operation: Executing SQL update statements inside the transaction.
• How many times: Each update runs once, but the number of operations depends on how many rows are affected.

How Execution Grows With Input

The time taken depends on how many rows each update affects and how complex the operations are.

Input Size (rows affected)	Approx. Operations
10	About 10 updates per statement
100	About 100 updates per statement
1000	About 1000 updates per statement

Pattern observation: As the number of rows affected grows, the time grows roughly in direct proportion.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the transaction grows linearly with the number of rows affected by the operations inside it.

Common Mistake

[X] Wrong: "The transaction time is always constant regardless of data size."

[OK] Correct: The time depends on how many rows the transaction modifies; more rows mean more work and longer time.

Interview Connect

Understanding how transaction time grows helps you explain database performance and reliability in real projects.

Self-Check

"What if the transaction included a loop that updated rows one by one instead of a single update statement? How would the time complexity change?"

Practice

1. Which of the following is NOT a valid state of a database transaction?

easy

A. Running

B. Waiting

C. Committed

D. Failed

Solution

1. Step 1: List common transaction states

   Common transaction states include Running (active), Waiting (blocked), Committed (successfully completed), and Aborted (rolled back).

2. Step 2: Identify invalid state

   "Failed" is not a standard transaction state; instead, "Aborted" or "Rolled back" is used for unsuccessful transactions.

3. Final Answer:

   Failed -> Option D

4. Quick Check:

   Standard states exclude "Failed" [OK]

Hint: Remember standard states: Running, Waiting, Committed, Aborted [OK]

Common Mistakes:

• Confusing 'Failed' with 'Aborted'
• Thinking 'Waiting' is not a state
• Assuming 'Failed' is official terminology

2. Which SQL command is used to move a transaction from the 'Running' state to the 'Committed' state?

easy

A. ROLLBACK

B. COMMIT

C. SAVEPOINT

D. BEGIN

Solution

1. Step 1: Understand transaction commands

   ROLLBACK undoes changes, SAVEPOINT sets a restore point, BEGIN starts a transaction, and COMMIT finalizes changes.

2. Step 2: Identify command to commit

   COMMIT is the command that moves a transaction from Running (active) to Committed (completed) state.

3. Final Answer:

   COMMIT -> Option B

4. Quick Check:

   COMMIT finalizes transaction [OK]

Hint: COMMIT saves changes permanently, ROLLBACK cancels [OK]

Common Mistakes:

• Confusing ROLLBACK with COMMIT
• Using SAVEPOINT to commit
• Thinking BEGIN commits

3. Consider the following sequence of SQL commands in a transaction:

BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
UPDATE accounts SET balance = balance + 100 WHERE id = 2;
COMMIT;

What is the final state of this transaction after execution?

medium

A. Committed

B. Aborted

C. Running

D. Waiting

Solution

1. Step 1: Analyze the transaction commands

   The transaction starts with BEGIN, performs two updates, then ends with COMMIT.

2. Step 2: Determine transaction state after COMMIT

   COMMIT finalizes the transaction successfully, so the state becomes Committed.

3. Final Answer:

   Committed -> Option A

4. Quick Check:

   COMMIT means transaction is Committed [OK]

Hint: COMMIT means transaction completed successfully [OK]

Common Mistakes:

• Thinking transaction remains Running after COMMIT
• Confusing Aborted with Committed
• Assuming Waiting state after COMMIT

4. Identify the error in this transaction sequence:

BEGIN;
UPDATE inventory SET quantity = quantity - 5 WHERE product_id = 10;
ROLLBACK;
COMMIT;

medium

A. COMMIT after ROLLBACK is invalid

B. ROLLBACK should come after COMMIT

C. BEGIN is missing

D. No error, sequence is correct

Solution

1. Step 1: Understand ROLLBACK and COMMIT order

   ROLLBACK cancels the transaction, so no changes remain to commit afterwards.

2. Step 2: Identify invalid command sequence

   After ROLLBACK, issuing COMMIT is invalid because the transaction is already aborted.

3. Final Answer:

   COMMIT after ROLLBACK is invalid -> Option A

4. Quick Check:

   Cannot COMMIT after ROLLBACK [OK]

Hint: ROLLBACK cancels; no COMMIT allowed after rollback [OK]

Common Mistakes:

• Thinking COMMIT can follow ROLLBACK
• Assuming ROLLBACK should come after COMMIT
• Missing BEGIN statement

5. A transaction is in the 'Waiting' state because it is blocked by another transaction holding a lock. Which of the following actions will NOT help the waiting transaction to proceed?

hard

A. The blocking transaction commits

B. The blocking transaction rolls back

C. The waiting transaction issues a COMMIT

D. The blocking transaction releases the lock

Solution

1. Step 1: Understand 'Waiting' state cause

   Waiting occurs when a transaction is blocked due to locks held by another transaction.

2. Step 2: Analyze actions that unblock waiting

   If the blocking transaction commits, rolls back, or releases the lock, the waiting transaction can proceed.

3. Step 3: Identify action that does NOT help

   The waiting transaction issuing COMMIT while blocked cannot proceed because it must first acquire the lock.

4. Final Answer:

   The waiting transaction issues a COMMIT -> Option C

5. Quick Check:

   Waiting means blocked; only blocking transaction actions help [OK]

Hint: Only blocking transaction actions unblock waiting transaction [OK]

Common Mistakes:

• Thinking waiting transaction can commit while blocked
• Assuming waiting state ends without lock release
• Confusing roles of blocking and waiting transactions