DBMS NotesPYQs

Chapter 7

Transaction Processing and Concurrency Control

5 hours8 marks22 past questionsBack to chaptersOpen filtered PYQsPrevious: Ch 6Next: Ch 8

Chapter Notes

Block-based notes with markdown, diagrams, code, and math.

Chapter 7 — Transaction Processing and Concurrency Control

7.1 Transaction States

7.2 ACID Properties

PropertyMeaningMechanism
AtomicityAll operations complete or none doLogging (undo)
ConsistencyDB moves from valid state to valid stateIntegrity constraints, application logic
IsolationConcurrent transactions appear serialConcurrency control (locks, MVCC)
DurabilityCommitted changes survive crashesLogging (redo), stable storage

Example: Bank transfer of $100 from Account A to B:

  • T1: READ(A), A ← A-100, WRITE(A), READ(B), B ← B+100, WRITE(B)
  • If crash after WRITE(A) but before WRITE(B): atomicity requires rollback of A.
  • After commit: even if crash occurs, the change persists (durability).

7.3 Concurrency Anomalies

AnomalyDescriptionExample
Lost updateT1 and T2 both read X; T1 writes X; T2 overwrites T1's changeTicket booking race
Dirty readT2 reads a value written by T1 which later abortsReading uncommitted data
Unrepeatable readT1 reads X; T2 updates X; T1 reads X again — different valueBalance check race
Phantom readT1 reads rows matching predicate; T2 inserts new matching rowCOUNT changes

7.4 Serializability

A schedule is an ordering of operations from multiple transactions.

A schedule is conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations.

Conflicting operations: on the same data item, from different transactions, with at least one write.

OperationsConflict?
Ti: Read(X), Tj: Read(X)No
Ti: Read(X), Tj: Write(X)Yes
Ti: Write(X), Tj: Read(X)Yes
Ti: Write(X), Tj: Write(X)Yes

Precedence (Serialization) Graph Test

Build a directed graph G = (V, E):
  V = one node per transaction
  E = edge Ti → Tj if any operation of Ti conflicts with and precedes an operation of Tj

If G has a CYCLE → schedule is NOT conflict serializable
If G is acyclic → schedule IS conflict serializable
  (topological order of G gives a serial schedule equivalent)

Example:
  T1: R(A) W(A) R(B) W(B)
  T2: R(A) W(A)

  Schedule S: R1(A) R2(A) W1(A) W2(A) R1(B) W1(B)

  Conflicts:
    R1(A) before W2(A) → T1 → T2
    W1(A) before R2(A)? No, R2(A) comes before W1(A)
    R2(A) before W1(A) → T2 → T1

  Graph: T1 → T2 AND T2 → T1 = CYCLE → NOT serializable

View Serializability

Broader than conflict serializability. A schedule S is view equivalent to serial schedule S' if:

  1. Same initial read: if Ti reads initial value of Q in S, so does in S'.
  2. Same dependent read: if Ti reads value written by Tj in S, same in S'.
  3. Same final write: if Ti performs final write of Q in S, so does in S'.

Every conflict-serializable schedule is view-serializable, but not vice versa.

7.5 Lock-Based Protocols

Lock Types & Compatibility Matrix

S (Shared)X (Exclusive)
SCompatible ✓Incompatible ✗
XIncompatible ✗Incompatible ✗

Two-Phase Locking (2PL)

PhaseAllowed operations
Growing phaseAcquire locks; no releases
Shrinking phaseRelease locks; no new acquisitions

Guarantee: 2PL ensures conflict-serializable schedules.

Strict 2PL: hold all write locks until commit/abort. Prevents cascading rollbacks.

Rigorous 2PL: hold ALL locks (read + write) until commit/abort.

7.6 Deadlock Handling

Deadlock: T1 waits for T2; T2 waits for T1 → circular wait.

Prevention Strategies

SchemeHowCharacteristic
Wait-DieOlder transaction waits; younger abortsNon-preemptive: older never killed
Wound-WaitOlder preempts younger; younger waitsPreemptive: younger may be killed

Both use timestamps assigned at transaction start.

Detection: Wait-For Graph

Build directed graph: Ti → Tj if Ti is waiting for a lock held by Tj. If cycle detected → deadlock. Choose a victim and rollback it.

7.7 Multiple Granularity Locking

Lock granularity levels: Database → Relation → Page → Tuple

Intention locks signal intent to lock at a finer level:

LockMeaning
IS (Intention Shared)Will acquire S locks on descendants
IX (Intention Exclusive)Will acquire X locks on descendants
S (Shared)Read entire subtree
SIX (S + IX)Read entire subtree + write some children
X (Exclusive)Write entire subtree

Compatibility: coarser locks (S, X) are incompatible with each other as before; IS/IX add compatibility.

Protocol: to lock node N at level L, must first acquire IS or IX on all ancestors of N.

Exam Quick-Reference

  • Transaction states: Active → Partially Committed → Committed (happy path); → Failed → Aborted (sad path).
  • ACID: Atomicity=undo log, Consistency=constraints, Isolation=locks, Durability=redo log.
  • Precedence graph cycle → NOT conflict serializable.
  • 2PL phases: grow (acquire) then shrink (release). Lock point = peak.
  • Wait-Die: old waits, young dies. Wound-Wait: old wounds young.

Full Syllabus Outline

Every topic from the syllabus data is preserved here.

Solved PYQs

A few past questions with short answers.

Chapter 74 marksasked 1xModel Q

Define the concept of Conflict Serializability. Provide an example involving two transactions (T1 and T2) that is NOT serializable and explain why it is not Conflict Serializable.

Solution

Conflict in Concurrent Transaction Schedules

Two operations from different transactions conflict if:

  1. They belong to different transactions.
  2. They access the same data item.
  3. At least one of them is a WRITE operation.

Conflict Pairs Table

Operation 1 (Ti)Operation 2 (Tj)Same Item?Conflict?Reason
Read(X)Read(X)YesNoTwo reads never conflict — reading doesn't change the value
Read(X)Write(X)YesYesTj writes X; Ti reads a different value depending on order
Write(X)Read(X)YesYesTi writes X; Tj reads a different value depending on order
Write(X)Write(X)YesYesThe final value of X depends on which write comes last
AnyAnyNoNoDifferent data items — no interference
Chapter 73 marksasked 1xModel Q

Briefly describe the four primary states in a database transaction. Illustrate these states using a simple state diagram.

Solution

Transaction and Transaction States:

A transaction is a logical unit of database work that consists of a sequence of operations (reads and writes) that must be executed atomically and in isolation from other transactions.

Why Transactions? Without transactions, a system crash mid-operation (e.g., debit account A, crash before crediting account B) leaves the database in an inconsistent state. Transactions ensure all-or-nothing execution.

Five Transaction States:

  1. Active: The transaction is executing normally — reading and writing.
  2. Partially Committed: The last statement has executed. The transaction's output is still in main memory (volatile storage) and has not yet been written to stable storage (disk).
  3. Committed: The transaction's changes have been durably written to stable storage. The transaction is complete and its effects are permanent.
  4. Failed: Normal execution cannot continue — either a logical error (divide by zero, constraint violation), system error (deadlock), or explicit ROLLBACK.
  5. Aborted: The rollback process has completed. The database has been restored to its state before the transaction began. The transaction can optionally be restarted.
Chapter 74 marksasked 1x2081 Chaitra R

Let schedule S be R1(X) W1(X); W2(X); R3(Y) W3(Y) W3(X); R1(Y). Conclude whether the given schedule is conflict serializable or not.

Solution

ACID Properties:

ACID is the set of properties that guarantee correctness of database transactions, especially in the presence of concurrent execution and system failures.

A — Atomicity: A transaction is an indivisible unit — either all its operations complete successfully (commit) or none of them take effect (abort/rollback). Partial execution is never visible. Implemented by: Write-Ahead Logging (WAL) — the undo log allows rolling back incomplete transactions after a crash. Example: Transfer $500 from A to B: debit A AND credit B must both happen or neither happens.

C — Consistency: A transaction transforms the database from one consistent state to another consistent state. It must respect all integrity constraints (PK, FK, CHECK, domain constraints). Implemented by: Application logic + integrity constraints. The DBMS enforces structural constraints; the application must ensure business rule consistency. Example: After a transfer, the total balance in the system must remain the same.

I — Isolation: Concurrently executing transactions must appear to execute serially — as if no other transaction is running. Intermediate states of a transaction are invisible to other transactions. Implemented by: Two-Phase Locking (2PL) or MVCC (Multi-Version Concurrency Control). Example: If T1 is transferring funds, T2 should see either the pre-transfer or post-transfer balances — not the intermediate state where A is debited but B is not yet credited.

D — Durability: Once a transaction commits, its changes are permanent — even if the system crashes immediately afterward. Implemented by: Redo log + stable storage. Committed data is written to non-volatile storage (disk) before the commit is acknowledged. Example: After a successful bank transfer commit, the new balances survive even a power failure.

More PYQs

Additional practice from this chapter.