ACID Invariants, Precedence Graphs & Conflict Serializability

When thousands of users execute bank transfers simultaneously, executing them sequentially one-by-one destroys throughput. But interleaving their operations blindly causes Lost Updates, Dirty Reads, and Inconsistent Summaries.

A Transaction is a logical unit of database processing that includes one or more database access operations. To maintain database consistency amidst failures and concurrency, the DBMS must guarantee the famous ACID Properties:

• Atomicity: All-or-nothing execution. Managed by the recovery log (Undo mechanism).

• Consistency: Database transitions from one valid state satisfying all integrity constraints to another valid state.

• Isolation: Concurrently executing transactions are shielded from each other's uncommitted intermediate states. Managed by the Concurrency Control Manager.

• Durability: Once a transaction commits, its updates persist permanently even if the power fails 1 millisecond later. Managed by Write-Ahead Logging (Redo mechanism).

A schedule is Conflict Serializable if it is conflict-equivalent to some serial execution of the same transactions.

What Constitutes a Conflicting Operation?

Two operations I_i and I_j belonging to different transactions are in conflict if and only if:

1. They belong to different transactions (T_i ≠ T_j),

2. They access the exact same data item X,

3. At least one of them is a WRITE (W(X)).

The Three Conflicting Pairs:

• R_i(X) and W_j(X) (Read-Write conflict / Anti-dependency)

• W_i(X) and R_j(X) (Write-Read conflict / Dirty Read hazard)

• W_i(X) and W_j(X) (Write-Write conflict / Blind Write hazard)

The Precedence Graph (Serialization Graph) Test:

1. Create a node for each participating transaction T_i.

2. Draw a directed edge T_i → T_j if T_i executes a conflicting operation on item X before T_j executes its conflicting operation on X.

3. Theorem: A schedule is Conflict Serializable IF AND ONLY IF its precedence graph contains NO DIRECTED CYCLES (is a DAG).

4. If acyclic, the Topological Sort of the graph yields the exact equivalent serial schedule!

Serializability guarantees correctness, but recoverability guarantees that an unexpected crash will not leave the database in an unrecoverable corrupted state.

1. Recoverable Schedule: If transaction T_j reads a value written by T_i, then T_i must commit BEFORE T_j commits.

Why: If T_j commits first and T_i aborts, T_j committed invalid dirty data that cannot be rolled back!

2. Cascadeless Schedule (Avoids Cascading Aborts): If T_j reads a value written by T_i, then T_i must commit BEFORE T_j even performs its READ.

Why: Prevents domino-effect aborts where aborting T_1 forces 50 downstream transactions to be cancelled.

3. Strict Schedule: If T_j wants to Read OR Write an item written by T_i, T_i must commit or abort first.

The Universal Schedule Subset Hierarchy: All Schedules ⊃ Recoverable ⊃ Cascadeless ⊃ Strict.