PadhaikoAll subjects

Transaction Processing and Concurrency Control

Database Management System (ENCT 301)

Open in the Padhaiko app

7.1 Transaction and transaction model - State diagram

A transaction is a logical unit of database work (one or more read(X), write(X), or SQL statements) that accesses and possibly updates various data items, executing either completely or not at all.

Definition

Five States of a Transaction

  1. Active: The initial state; the transaction stays in this state while it is executing its read/write instructions.
  2. Partially Committed: Reached immediately after the final statement of the transaction has executed, before its log records and modifications are safely flushed to non-volatile disk storage.
  3. Committed: Reached once all changes are guaranteed permanent (durable) in stable storage; the transaction has completed successfully and cannot be aborted.
  4. Failed: Reached from Active or Partially Committed if normal execution can no longer proceed (e.g., constraint violation, deadlock abort, hardware crash, or explicit ROLLBACK).
  5. Aborted: Reached after the transaction has been rolled back and the database is restored to its exact state prior to the start of the transaction. From Aborted, the system either restarts the transaction (if caused by hardware/concurrency error) or kills it (if caused by internal logic error).
Transaction State Transition DiagramText
                       +-------------------+
                       | Partially         |----(Durable Flush)---> [ Committed ]
                       | Committed         |
                       +-------------------+
                          ^               \
         (Last Statement) |                \ (Disk/Write Failure)
                          |                 v
  (Start) ----------> [ Active ] -------> [ Failed ]
                      (Executing)    (Error/Abort) |
                                                   | (Rollback Complete)
                                                   v
                                              [ Aborted ] ---> (Restart / Kill)

7.2 Acid properties

To preserve database integrity despite concurrent users and system crashes, every transaction must satisfy four ACID properties:

The Four ACID Properties and DBMS Responsibility
PropertyFormal MeaningEnforced By
A — Atomicity"All or nothing": either all operations of the transaction reflect properly in the database, or none do.Recovery Manager (Undo logging / rollback)
C — ConsistencyExecution of a transaction in isolation (from a consistent state) preserves all database consistency invariants (e.g., total sum of accounts remains unchanged).Application Programmer + DBMS Integrity Constraints
I — IsolationEven when multiple transactions execute concurrently, each transaction is unaware of others; intermediate dirty updates are hidden until commit, producing an effect equivalent to serial execution.Concurrency Control Manager (Locking / Timestamps / MVCC)
D — DurabilityOnce a transaction commits, its updates persist permanently even if a power loss or system crash occurs immediately afterward.Recovery Manager (Redo logging / WAL flush to stable disk)

7.3 Concurrent execution of transactions

Executing transactions concurrently (interleaving their CPU and disk operations) improves system throughput (more transactions per second) and reduces average response time (short transactions do not wait behind long disk-bound ones). However, uncontrolled interleaving causes severe concurrency anomalies:

Classic Concurrency Anomalies
AnomalyDescription
Lost Update (W–W) and both read , modify it, and write back; the second write overwrites and erases the first update.
Dirty Read (W–R) updates , reads the uncommitted , and then aborts—leaving holding phantom invalid data.
Unrepeatable Read (R–W–R) reads ; modifies and commits ; re-reads and gets a different value within the same transaction.
Phantom Read executes a range query (WHERE Dept='CS'), inserts a new 'CS' row and commits, and 's repeat query sees a "phantom" row.

Schedules and Recoverability

A schedule is an ordering of the instructions of a set of concurrent transactions that preserves the relative order of instructions within each individual transaction. For transactions with operations, there are serial schedules (no interleaving) and total valid schedules.


7.4 Serializability (Conflict and view serializability)

A concurrent schedule is serializable if its net effect on the database is identical to some serial schedule of the same transactions.

Definition

Conflict Serializability vs. View Serializability

  1. Conflicting Instructions: Two consecutive instructions (from ) and (from , ) conflict if they access the same data item and at least one of them is a write(Q):
    • and : Do NOT conflict (order can be swapped).
    • and , and , and : CONFLICT (order matters).
  2. Conflict Equivalence & Conflict Serializability: Schedule is conflict equivalent to if can be transformed into by swapping adjacent non-conflicting instructions. Schedule is conflict serializable if it is conflict equivalent to some serial schedule.
  3. View Equivalence & View Serializability: Schedules and are view equivalent if for every data item :
    • (Initial Read) Whichever transaction reads the initial value of in also does so in .
    • (Reads-From) If reads a value of written by in , it does so in .
    • (Final Write) Whichever transaction performs the final write(Q) in also performs the final write(Q) in . Schedule is view serializable if it is view equivalent to a serial schedule.

Precedence Graph Test for Conflict Serializability

Construct a directed precedence (serialization) graph where vertices are the transactions , and add a directed edge whenever an operation of precedes and conflicts with an operation of on the same data item (, , or ).


7.5 Lock based protocols

A lock controls concurrent access to a data item using two standard lock modes:

Basic Lock Compatibility Matrix
Requested \ HeldShared (S)Exclusive (X)
Shared (S)True (Compatible)False (Wait)
Exclusive (X)False (Wait)False (Wait)

Two-Phase Locking (2PL) Protocols

Simply locking and unlocking immediately around individual reads/writes does not guarantee serializability. Two-Phase Locking (2PL) guarantees conflict serializability by dividing each transaction into two distinct phases:

  1. Growing Phase: A transaction may acquire locks (and upgrade S X), but may not release any lock.
  2. Shrinking Phase: A transaction may release locks (and downgrade X S), but may not acquire any new locks. (The point where the transaction holds its maximum locks and releases its first lock is the lock point, which defines the equivalent serial order!)
AspectBasic 2PLStrict 2PL & Rigorous 2PL
Basic 2PLAny lock may be released as soon as the shrinking phase starts.Guarantees conflict serializability, but vulnerable to cascading aborts and deadlocks.
Strict 2PLAll exclusive (X) locks are held until the transaction commits or aborts; S locks may release earlier.Guarantees conflict serializability, strictness, and cascadeless (ACA) recovery. (Industry standard!)
Rigorous 2PLAll locks (S and X) are held until commit or abort.Same as Strict 2PL, plus commit order directly matches the serialization order.

7.6 Deadlock handling and prevention

A system is in deadlock when a cycle of two or more transactions exists where every transaction is waiting for a lock held by the next transaction in the cycle (e.g., holds X(A) and waits for X(B) while holds X(B) and waits for X(A)).

1. Deadlock Prevention (Timestamp-Based Schemes)

Assign each transaction a unique startup timestamp (smaller timestamp = older transaction). When requests a lock held by :

AspectWait-Die Scheme (Non-Preemptive)Wound-Wait Scheme (Preemptive)
is OLDER () is allowed to WAIT for . WOUNDS (preempts/aborts) , forcing to roll back and release the lock.
is YOUNGER () DIES (aborts itself and restarts with the same original timestamp). is allowed to WAIT for .
Key CharacteristicOlder transactions wait for younger ones; prevents cycles without preemption, though younger ones may abort repeatedly.Older transactions never wait for younger ones; fewer aborts overall. Retaining the original timestamp on restart prevents starvation in both schemes!

(Timeout-based prevention simply aborts any transaction that waits longer than a threshold; simple to implement but risks unnecessary rollbacks under heavy load.)

2. Deadlock Detection and Recovery


7.7 Multiple granularity

Real databases contain data items of vastly different sizes. Locking only tuples incurs huge lock-manager overhead on full-table scans, whereas locking only entire tables destroys concurrency for single-row updates. Multiple granularity locking organizes items into a tree hierarchy:

To allow locking at any level safely without scanning the whole subtree for conflicting lower-level locks, intention locks are placed on ancestor nodes first:

Definition

Intention Lock Modes

Multiple Granularity 5x5 Lock Compatibility Matrix
Requested \ HeldISIXSSIXX
ISTrueTrueTrueTrueFalse
IXTrueTrueFalseFalseFalse
STrueFalseTrueFalseFalse
SIXTrueFalseFalseFalseFalse
XFalseFalseFalseFalseFalse

Worked Out Examples

Example 7.1

7.1

Test the following two schedules for conflict serializability using precedence graphs; if conflict serializable, give an equivalent serial schedule:

Analyzing Schedule : Check all conflicting operation pairs (same item, different transactions, at least one Write):

  • On item :
    • .
    • and are both in (no edge); and do not conflict.
  • On item :
    • (same tx); .
  • On item : only appears (no conflict).
  • Edges of : . No cycle exists!
  • Result for : Conflict serializable; unique topological order is .

Analyzing Schedule : Check conflicts in :

  • On item :
    • .
    • .
    • .
  • On item :
    • .
  • Now look at the edges: and form a -cycle (, as well as )!
  • Result for : Not conflict serializable.
Answer:
  1. is conflict serializable (acyclic precedence graph ; equivalent serial schedule: ).
  2. is not conflict serializable (contains cycle ).
Example 7.2

7.2

Examine the schedule with a blind write:

Show that is not conflict serializable, yet is view serializable (and find the equivalent serial schedule).

Conflict Serializability Test (Precedence Graph): Every pair of operations accesses with at least one write:

  • .
  • .
  • .

Because forms a cycle, is not conflict serializable.

View Serializability Test (Three View-Equivalence Conditions on ):

Check the three view conditions in :

  1. Initial Read: reads the initial database value of .
  2. Reads-From: No transaction reads any value written by another transaction in .
  3. Final Write: performs the final write(Q).

Now test the serial schedule ():

  • Initial Read: reads initial (matches ).
  • Reads-From: None (matches ).
  • Final Write: performs the final write(Q) (matches ).

All three conditions hold!

Answer:

is not conflict serializable (precedence graph has cycle ), but is view serializable and view-equivalent to the serial schedule .

Example 7.3

7.3

  1. Three transactions arrive with timestamps , , . Suppose holds an X lock on item . Determine what happens under (a) Wait-Die and (b) Wound-Wait when:
    • Case 1: requests X(A)
    • Case 2: requests X(A)
  2. If two transactions and each have operations (), how many total valid schedules and how many non-serial (interleaved) schedules exist? Also how many serial schedules exist for transactions?

Wait-Die vs. Wound-Wait Outcomes: Remember: smaller timestamp = older transaction ( is older than , and is younger than ).

  • Case 1 ( older requests item held by younger):
    • Wait-Die: Older WAITS for .
    • Wound-Wait: Older WOUNDS (aborts) younger and takes the lock.
  • Case 2 ( younger requests item held by older):
    • Wait-Die: Younger DIES (aborts and restarts) with original timestamp .
    • Wound-Wait: Younger WAITS for older .

Counting Serial and Interleaved Schedules:

  • For transactions, number of serial schedules .
  • For () and (), total schedules preserving intra-transaction order:
  • Subtracting the serial schedules ( and ) leaves interleaved (non-serial) schedules.
Answer:
  1. Case 1 (): Wait-Die: waits; Wound-Wait: is wounded (aborted). Case 2 (): Wait-Die: dies (aborts); Wound-Wait: waits.
  2. transactions have serial schedules; two -operation transactions have total schedules ( interleaved, serial).

Exercises

Practice Exercises — Transactions & Concurrency

Question 1

Draw the transaction state diagram and explain each of the five states (Active, Partially Committed, Committed, Failed, Aborted). Explain the ACID properties of a transaction with a banking transfer example.

Transaction States: A transaction begins in Active, moves to Partially Committed after its final operation, and enters Committed once log records/writes are flushed durably to disk. If any error or abort occurs during Active or Partially Committed, it moves to Failed, rolls back all partial changes, and reaches Aborted (where it is killed or restarted).

ACID Properties (Transferring from Account to ):

  • Atomicity: Either both debit() and credit() happen, or neither happens.
  • Consistency: Total money before and after the transfer remains identical.
  • Isolation: Another concurrent balance-check query cannot observe debited before is credited.
  • Durability: Once committed, the updated balances survive a crash immediately afterward.
Answer:

The five states are Active Partially Committed Committed, or Failed Aborted. ACID stands for Atomicity (all-or-nothing), Consistency (invariant preservation), Isolation (concurrent invisibility), and Durability (post-commit persistence).

Question 2

Differentiate between recoverable, cascadeless (ACA), and strict schedules. Give a concrete two-transaction example of a non-recoverable schedule and explain why strict schedules are preferred in practice.

Schedule Hierarchy:

  • Recoverable: If reads an item written by , must commit before commits.
  • Cascadeless (ACA): may only read items written by after has committed (prevents cascading rollbacks).
  • Strict: may neither read nor write any item written by until commits or aborts. (Inclusion: .)

Non-Recoverable Example and Why Strict Is Preferred: Consider . Here commits after reading 's uncommitted write, then aborts— cannot be undone, violating durability/atomicity! Strict schedules are preferred because they completely prevent cascading aborts and allow simple physical before-image undo without overwriting another uncommitted write.

Answer:

Recoverable commits writers before dependent readers; cascadeless delays reads until the writer commits; strict delays both reads and writes until the writer commits/aborts. Strict schedules are preferred because they eliminate cascading rollbacks and simplify undo recovery.

Question 3

State the Two-Phase Locking (2PL) protocol and contrast Basic 2PL, Strict 2PL, and Rigorous 2PL. Does Basic 2PL prevent deadlocks? Explain.

Two-Phase Locking Variants: Under 2PL, every transaction has a Growing Phase (acquires locks, never releases) followed by a Shrinking Phase (releases locks, never acquires).

  • Basic 2PL: Releases any lock once the shrinking phase begins; guarantees conflict serializability, but allows dirty reads / cascading aborts if X locks are released early.
  • Strict 2PL: Holds all X locks until COMMIT/ABORT; guarantees conflict serializability and strict/cascadeless schedules.
  • Rigorous 2PL: Holds all S and X locks until COMMIT/ABORT; commit order matches serialization order.

2PL and Deadlocks: No—Basic (and Strict/Rigorous) 2PL does NOT prevent deadlocks. For example, acquires S(A), acquires S(B), then requests X(B) (waits for ) and requests X(A) (waits for ). Both are still in their growing phases, yet they are deadlocked!

Answer:

2PL enforces a Growing Phase (acquire only) followed by a Shrinking Phase (release only). Strict 2PL holds X locks until commit/abort (cascadeless recovery) and Rigorous 2PL holds all locks until commit/abort. None of them prevents deadlocks, which must be handled via detection or timestamp prevention.

Question 4

Explain Multiple Granularity Locking using intention locks (IS, IX, SIX). Suppose transaction wants to read a single tuple in table Student while wants to update every tuple in Student. Which lock modes must and acquire from Database down to Tuple, and can they run concurrently?

Lock Acquisition Paths:

  • (reads one tuple in Student):
    1. IS on Database
    2. IS on Student (table)
    3. IS on Page containing
    4. S on tuple
  • (updates the entire Student table):
    1. IX on Database
    2. X on Student (table—no need to lock individual pages or tuples!)

Concurrency Check Using Compatibility Matrix:

  • At Database: requests IS and holds IX Compatible.
  • At Student: requests IS while holds X Incompatible! (IS conflicts with X).

Therefore, must wait until releases X(Student), preventing from reading partially updated rows.

Answer:

acquires IS(Database) IS(Student) IS(Page) S(t); acquires IX(Database) X(Student). They cannot run concurrently because IS and X are incompatible on Student.

Question 5
  1. Test the schedule for conflict serializability using a precedence graph.
  2. How many serial schedules exist for transactions? For transactions each having operations, how many non-serial (interleaved) schedules exist?

Precedence Graph for : Inspect conflicts on each data item:

  • On : .
  • On : .
  • On : .

The graph contains the directed -cycle , so is not conflict serializable.

Schedule Counting:

  • Serial schedules for transactions: .
  • Total schedules for two -operation transactions:
  • Subtracting the serial schedules gives interleaved (non-serial) schedules.
Answer:
  1. is not conflict serializable (cycle ).
  2. transactions have serial schedules; two -operation transactions have non-serial schedules ( total minus serial).
← File Structure and HashingCrash Recovery →