Conflict Equivalence

In the previous page, we introduced conflict equivalence as the practical choice for schedule equivalence. Now we dive deep into this concept—understanding not just what it is, but why it works and how to apply it rigorously.

Conflict equivalence is the heart of practical serializability theory. It provides:

1. A precise definition of when schedules are "effectively the same"
2. An efficient polynomial-time algorithm for testing serializability
3. The theoretical foundation for concurrency control protocols like Two-Phase Locking

This page exhaustively explores conflict operations, the conflict equivalence rules, systematic conflict identification, and the theoretical properties that make this approach so powerful.

Understanding conflict equivalence deeply prepares you to construct precedence graphs (next page) and to understand how real database systems ensure transactional correctness.

Two operations from a set of concurrent transactions are said to conflict if the outcome of executing them depends on their order. Formally:

Definition: Conflicting Operations

Operations Oᵢ and Oⱼ (from transactions Tᵢ and Tⱼ respectively, where i ≠ j) conflict if and only if ALL of the following conditions hold:

1. Different Transactions: The operations belong to different transactions (i ≠ j)
2. Same Data Item: Both operations access the same data item X
3. At Least One Write: At least one of the operations is a write operation

Conflict(Oᵢ, Oⱼ) ⟺ (Tᵢ ≠ Tⱼ) ∧ (item(Oᵢ) = item(Oⱼ)) ∧ (isWrite(Oᵢ) ∨ isWrite(Oⱼ))

Why These Conditions?

Condition 1 (Different Transactions): Operations within the same transaction are ordered by the transaction's program logic. Only operations from different transactions can be reordered by the scheduler.

Condition 2 (Same Data Item): Operations on different data items are completely independent. r₁(A) and w₂(B) can be executed in either order with identical results.

Condition 3 (At Least One Write): Two read operations on the same item don't conflict because both merely observe the value—neither changes it. The order of reads doesn't affect what either sees.

The Conflict Matrix

For two operations from different transactions on the same data item, the conflict matrix is:

• RR (Read-Read): Both observe; no interaction → No conflict
• RW (Read-Write): Reader may see value before or after write → Conflict
• WR (Write-Read): Reader may see old or new value → Conflict
• WW (Write-Write): Final value depends on order → Conflict

Each conflict type has distinct implications for correctness and represents a different kind of dependency between transactions. Understanding these deeply is essential for analyzing concurrent behavior.

Read-Write (RW) Conflict

Pattern: rᵢ(X) ... wⱼ(X) or wⱼ(X) ... rᵢ(X)

A read-write conflict exists when one transaction reads a data item that another transaction writes.

Implications:

• The read may see the value before or after the write
• Creates a read-dependency: Tᵢ depends on whether it reads before or after Tⱼ's write
• If rᵢ(X) comes first: Tᵢ sees the old value; Tⱼ's write comes later
• If wⱼ(X) comes first: Tᵢ sees Tⱼ's new value

Example:

Initial: Balance = 1000

T₁: r₁(Balance) → sees 1000 (decides to withdraw 800)
T₂: w₂(Balance) = 500 (another withdrawal already processed)

If r₁ before w₂: T₁ thinks Balance is 1000 (incorrect assumption)
If w₂ before r₁: T₁ sees Balance is 500 (correct current state)

Write-Read (WR) Conflict

Pattern: wᵢ(X) ... rⱼ(X) or rⱼ(X) ... wᵢ(X)

Note: WR and RW conflicts are logically the same—just named from different perspectives.

A write-read conflict determines whether a read sees the written value.

Implications:

• Creates a write-dependency: What Tⱼ reads depends on Tᵢ's write
• If wᵢ(X) comes first: Tⱼ reads the new value (written by Tᵢ)
• If rⱼ(X) comes first: Tⱼ reads the old value (not yet modified)

This is the conflict behind 'dirty reads' and 'non-repeatable reads':

• Dirty read: Tⱼ reads Tᵢ's uncommitted write, then Tᵢ aborts
• Non-repeatable read: Tⱼ reads X, Tᵢ writes X, Tⱼ reads X again → different values

Write-Write (WW) Conflict

Pattern: wᵢ(X) ... wⱼ(X)

A write-write conflict exists when two transactions both write to the same data item.

Implications:

• The final value of X depends on which write occurs last
• Creates an output-dependency: The database's final state depends on write order
• The first write is "overwritten" by the second

This is the conflict behind 'lost updates':

Initial: Counter = 0

T₁: w₁(Counter) = 1
T₂: w₂(Counter) = 2

If w₁ then w₂: Final Counter = 2 (T₁'s update "lost")
If w₂ then w₁: Final Counter = 1 (T₂'s update "lost")

Both orderings are valid in isolation—the problem arises when neither transaction realizes the other exists, leading to semantically incorrect behavior (like both incrementing from the same base value).

To analyze any schedule, we need a systematic approach to find all conflicts. Here's a rigorous methodology:

Algorithm: Finding All Conflicts

Input: Schedule S with transactions T₁, T₂, ..., Tₙ
Output: Set of all conflicting pairs with their types and order

1. Create empty conflict set C

2. For each unique data item X accessed in S:
   a. Collect all operations on X: Ops_X = {o | o accesses X}
   
   b. For each pair (oᵢ, oⱼ) where oᵢ ∈ Tᵢ, oⱼ ∈ Tⱼ, and i < j:
      - If both are reads: skip (no conflict)
      - Otherwise:
        * Determine conflict type (RW, WR, or WW)
        * Determine order in S (which comes first)
        * Add (oᵢ, oⱼ, type, order) to C

3. Return C

Organizing the Analysis

It helps to organize the analysis by data item:

Data Item: A
  Operations: r₁(A) at position 1, w₂(A) at position 3, r₃(A) at position 5
  Pairs to check:
    - r₁(A), w₂(A): RW conflict, T₁ before T₂
    - r₁(A), r₃(A): No conflict (both reads)
    - w₂(A), r₃(A): WR conflict, T₂ before T₃

Data Item: B
  Operations: w₁(B) at position 2, w₃(B) at position 4
  Pairs to check:
    - w₁(B), w₃(B): WW conflict, T₁ before T₃

A powerful way to understand conflict equivalence is through the swap theorem, which provides an operational definition of equivalence.

Statement: The Swap Theorem

Theorem: Two schedules S₁ and S₂ are conflict equivalent if and only if S₁ can be transformed into S₂ by a sequence of swaps of adjacent non-conflicting operations.

S₁ ≡c S₂  ⟺  S₁ can be transformed to S₂ by swapping
              adjacent non-conflicting operations

Why This Works

Non-conflicting operations are order-independent. If operations Oᵢ and Oⱼ don't conflict, then:

• They access different data items, OR
• They're both reads on the same item, OR
• They're from the same transaction

In any of these cases, executing Oᵢ before Oⱼ produces exactly the same result as executing Oⱼ before Oᵢ. The operations are truly independent.

Conflicting operations are order-dependent. The result changes based on which executes first. These operations cannot be swapped.

Visualizing Swaps

Original: r₁(A) r₂(B) w₁(A) w₂(B)

Can we reach: r₂(B) r₁(A) w₁(A) w₂(B)?

Step 1: Check if r₁(A) and r₂(B) conflict
        - Different items (A vs B) → No conflict → Can swap!

After swap: r₂(B) r₁(A) w₁(A) w₂(B) ✓

These schedules are conflict equivalent.

What Swaps Are Allowed?

Now we connect conflict equivalence to serializability through a fundamental theorem.

Theorem: Conflict Serializability Test

Statement: A schedule S is conflict serializable if and only if S is conflict equivalent to some serial schedule.

Corollary: A schedule S is conflict serializable if and only if there exists an ordering of transactions such that for every conflict, the transaction with the earlier operation comes first in that ordering.

The Key Insight

Conflicts create ordering constraints between transactions. If operations from Tᵢ and Tⱼ conflict, and Tᵢ's operation comes first in the schedule, then Tᵢ must come before Tⱼ in any equivalent serial schedule.

Schedule S has: oᵢ <S oⱼ  (conflicting operations)
                  ↓
Equivalent serial: Tᵢ before Tⱼ  (transaction order)

If these constraints are consistent (no cycles), we can find a serial order. If they're inconsistent (cycles exist), no serial order satisfies all constraints.

Proving Schedule Serializability

To prove a schedule S is conflict serializable:

Method 1: Find an Equivalent Serial Schedule

1. Identify a candidate serial order by examining conflicts
2. Verify that all conflicts are consistent with this order
3. Optionally, show the transformation via swaps

Method 2: Precedence Graph (Preferred)

1. Build a graph with transactions as nodes
2. Add edge Tᵢ → Tⱼ for each conflict where Tᵢ's operation precedes Tⱼ's
3. If the graph is acyclic → serializable
4. Any topological sort gives an equivalent serial order

We'll cover precedence graphs in complete detail on the next page.

Proving Non-Serializability

To prove a schedule is NOT conflict serializable:

1. Show a cycle of conflicts:

   • Tᵢ must be before Tⱼ (due to conflict 1)
   • Tⱼ must be before Tₖ (due to conflict 2)
   • Tₖ must be before Tᵢ (due to conflict 3)
   • Contradiction! No linear order satisfies all constraints.

2. Or show that the precedence graph has a cycle.

Conflict serializability has several important theoretical properties that make it suitable as the practical standard.

Inclusion Property

Every conflict-serializable schedule is view-serializable.

Proof sketch: If two schedules are conflict equivalent, they must be view equivalent. Conflict equivalence preserves read-from relationships because all read-write orderings are identical.

Conflict Serializable ⊂ View Serializable

The converse is NOT true—some view-serializable schedules are not conflict-serializable (involving blind writes).

Closure Property

The set of conflict-serializable schedules is closed under equivalence.

If S₁ is conflict serializable and S₂ ≡c S₁, then S₂ is also conflict serializable.

Proof: S₁ ≡c Ss (some serial). S₂ ≡c S₁. By transitivity, S₂ ≡c Ss. Therefore S₂ is conflict serializable.

Prefix Property

If S is conflict serializable, any prefix of S (with completed transactions) is also conflict serializable.

This is crucial for concurrency control: we can make scheduling decisions incrementally, knowing that what we've accepted so far remains serializable.

Composability

Conflict serializability is composable under certain conditions.

If S₁ over {T₁, T₂} is serializable with order T₁→T₂, and S₂ over {T₂, T₃} is serializable with order T₂→T₃, then a combined schedule respecting both is serializable with order T₁→T₂→T₃.

Computational Efficiency

Testing conflict serializability is in P (polynomial time).

• Build precedence graph: O(conflicts) = O(n² × m²)
• Test for cycles: O(V + E) = O(n + conflicts)
• Total: Polynomial in the schedule size

This is in stark contrast to view serializability testing, which is NP-complete.

Before diving into precedence graphs (next page), let's build intuition for why graph-based testing works.

Conflicts as Orderings

Each conflict in a schedule imposes an ordering:

r₁(A) ... w₂(A)  →  T₁ must precede T₂ in any equivalent serial schedule
                    (because T₁ read A before T₂ changed it)

We can represent this as a directed edge: T₁ → T₂

Meaning: "T₁ comes before T₂"

Multiple Conflicts = Multiple Constraints

Conflict 1: r₁(A) before w₂(A)  →  T₁ → T₂
Conflict 2: w₂(B) before r₃(B)  →  T₂ → T₃
Conflict 3: w₃(C) before w₁(C)  →  T₃ → T₁

These constraints form a graph:

T₁ → T₂ → T₃ → T₁  (cycle!)

What Cycles Mean

A cycle T₁ → T₂ → T₃ → T₁ means:

• T₁ must be before T₂
• T₂ must be before T₃
• T₃ must be before T₁

But if T₁ < T₂ < T₃ < T₁, then T₁ < T₁. Contradiction!

No serial ordering can satisfy a cycle of constraints.

What Acyclicity Means

If there are no cycles, the constraints are consistent. We can find a topological sort of the graph—an ordering where every edge goes from earlier to later.

If graph is: T₁ → T₂, T₁ → T₃, T₂ → T₃

Topological sort: T₁, T₂, T₃

This is an equivalent serial schedule!