Equivalent Schedules

We've established that serial schedules are our benchmark for correctness. We've also seen that concurrent schedules provide the performance modern systems need. The critical question now becomes:

How do we determine if a concurrent schedule is "equivalent" to a serial schedule?

The answer isn't as simple as it might seem. "Equivalent" could mean many things:

• Do they produce the same final database state?
• Do they perform the same reads and writes?
• Do they follow the same logical dependencies?

Each interpretation leads to a different formal definition of equivalence, with different properties and different computational complexity for testing. Understanding these distinctions is essential for appreciating why conflict equivalence became the practical standard in database systems.

This page explores the various notions of schedule equivalence, their formal definitions, their relationships, and their practical implications for database concurrency control.

Why Equivalence Matters

Serializability is defined in terms of equivalence:

A schedule S is serializable if and only if
S is EQUIVALENT to some serial schedule

But what does "equivalent" mean? The definition of equivalence directly determines:

1. Which concurrent schedules are considered correct
2. How difficult it is to test serializability
3. What guarantees the database provides to applications

The Spectrum of Equivalence

Imagine two schedules, S₁ and S₂, both operating on the same transactions. They could be related in various ways:

• Identical: Same operations in the exact same order (trivially equivalent)
• Operationally equivalent: Different order but same reads observe same writes
• Result equivalent: Different operations observed but same final state
• Unrelated: Different outcomes with no meaningful relationship

Database theory formalizes specific points on this spectrum as precise definitions of equivalence.

The Three Main Definitions

The database literature defines three primary notions of schedule equivalence:

Each is a different formalization of "the same behavior." We'll explore all three, but focus on conflict equivalence as it's the foundation for practical serializability testing.

The simplest notion of equivalence focuses solely on the outcome:

Definition: Two schedules S₁ and S₂ are result equivalent if they produce the same final database state when starting from the same initial state.

S₁ ≡ᵣ S₂  ⟺  FinalState(S₁, InitialDB) = FinalState(S₂, InitialDB)

Intuition

Result equivalence captures the idea: "If the database ends up the same, who cares how we got there?" This seems reasonable at first—applications typically care about final results, not intermediate steps.

Example

Consider two schedules on a variable X initially set to 10:

S₁: r₁(X) w₁(X)  // T₁ reads X=10, writes X=15 (X = X + 5)
    r₂(X) w₂(X)  // T₂ reads X=15, writes X=30 (X = X * 2)
    Final: X = 30

S₂: r₂(X) w₂(X)  // T₂ reads X=10, writes X=20 (X = X * 2)  
    r₁(X) w₁(X)  // T₁ reads X=20, writes X=25 (X = X + 5)
    Final: X = 25

These schedules are NOT result equivalent (30 ≠ 25), even though both are serial and therefore both correct.

The Problem with Result Equivalence

Result equivalence suffers from a critical flaw: coincidental equivalence.

Consider:

Initial: X = 10

S₁ (Serial T₁→T₂):
  T₁: X = 0 (constant assignment)
  T₂: X = 0 (constant assignment)
  Final: X = 0

S₂ (Interleaved, with lost update):
  r₁(X) = 10
  r₂(X) = 10
  w₁(X) = 0  // T₁ writes
  w₂(X) = 0  // T₂ overwrites (lost update!)
  Final: X = 0

S₂ contains a lost update (T₁'s write was overwritten), but produces the same result as S₁ due to the specific values involved.

The Deeper Problem: Result equivalence depends on the initial state and specific data values. A schedule that's result-equivalent for one initial state might not be for another. We need a notion of equivalence that's state-independent.

To address the shortcomings of result equivalence, we introduce a stronger notion that considers not just the final state, but what each transaction "sees" during execution.

Definition: Two schedules S₁ and S₂ are view equivalent if they satisfy the following three conditions:

Condition 1: Initial Reads

For every data item X, if transaction Tᵢ reads the initial value of X in S₁, then Tᵢ must also read the initial value of X in S₂.

If rᵢ(X) reads initial value in S₁ → rᵢ(X) reads initial value in S₂

Condition 2: Read-Write Relationship

For every read operation rᵢ(X) that reads a value written by wⱼ(X) in S₁, the same relationship must hold in S₂.

If rᵢ(X) reads from wⱼ(X) in S₁ → rᵢ(X) reads from wⱼ(X) in S₂

Condition 3: Final Writes

For every data item X, the transaction that performs the final write to X must be the same in both schedules.

If Tᵢ performs final write to X in S₁ → Tᵢ performs final write to X in S₂

Properties of View Equivalence

Stronger than Result Equivalence: View-equivalent schedules are always result-equivalent, but not vice versa. View equivalence ensures the same computational process, not just the same final result.

State-Independent: View equivalence depends only on the schedule structure, not the actual data values. Two schedules are either view-equivalent or not, regardless of initial database state.

Ideal for Correctness: View equivalence captures exactly what we mean by "the same execution from the transactions' perspective."

The Problem: Computational Complexity

Testing view serializability (checking if a schedule is view-equivalent to any serial schedule) is NP-complete. This means:

• No known polynomial-time algorithm exists
• Testing becomes exponentially expensive as transactions grow
• Impractical for real-time scheduling decisions

This is why view equivalence, despite its theoretical elegance, is not used in practice.

Conflict equivalence provides a practical, efficiently testable notion of equivalence that captures the essential correctness properties we need.

What Is a Conflict?

Two operations conflict if:

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

Types of Conflicts:

Non-Conflicts:

• Read-Read: rᵢ(X), rⱼ(X) — no conflict (both just observe)
• Different items: wᵢ(X), wⱼ(Y) — no conflict (independent data)

The Definition

Definition: Two schedules S₁ and S₂ are conflict equivalent if:

1. They involve the same set of transactions with the same operations
2. Every pair of conflicting operations is ordered the same way in both schedules

Formally:

S₁ ≡c S₂  ⟺  For all conflicting pairs (oᵢ, oⱼ):
              oᵢ < oⱼ in S₁  ⟺  oᵢ < oⱼ in S₂

Intuition

Conflict equivalence states: "Schedules are equivalent if all the 'important' orderings are the same." The "important" orderings are those that affect the outcome—which means orderings between conflicting operations.

Non-conflicting operations can be reordered freely without changing the result. Only conflicting operations must maintain their relative order.

The three equivalence types form a hierarchy, with each level being more restrictive than the next:

┌─────────────────────────────────────────────────────────────┐
│               RESULT EQUIVALENT SCHEDULES                    │
│                     (Largest set)                            │
│                                                              │
│   ┌────────────────────────────────────────────────────┐    │
│   │           VIEW EQUIVALENT SCHEDULES                │    │
│   │                                                    │    │
│   │   ┌───────────────────────────────────────────┐   │    │
│   │   │      CONFLICT EQUIVALENT SCHEDULES        │   │    │
│   │   │           (Smallest set)                  │   │    │
│   │   │                                           │   │    │
│   │   │   Efficiently testable (polynomial)       │   │    │
│   │   └───────────────────────────────────────────┘   │    │
│   │                                                    │    │
│   │   + Additional view-equivalent schedules           │    │
│   │   Testing is NP-complete                           │    │
│   └────────────────────────────────────────────────────┘    │
│                                                              │
│   + Coincidentally result-equivalent schedules              │
│   Not suitable for guaranteeing correctness                 │
└─────────────────────────────────────────────────────────────┘

The Implications

Conflict Equivalent ⟹ View Equivalent ⟹ Result Equivalent

But NOT the reverse:

• View equivalent ⟹̸ Conflict equivalent (some view-equivalent schedules are not conflict-equivalent)
• Result equivalent ⟹̸ View equivalent (coincidental results exist)

The Gap: View-Serializable but Not Conflict-Serializable

What schedules fall in the gap between conflict and view serializability? These involve blind writes—writes that don't depend on any prior reads.

Example:

T₁: w₁(X)       // Writes X without reading
T₂: w₂(X)       // Writes X without reading  
T₃: r₃(X)       // Reads X

Schedule S: w₁(X) w₂(X) r₃(X)

This schedule is:

• View-serializable: Equivalent to serial T₁→T₂→T₃

  • No initial reads to match (none exist)
  • T₃ reads from T₂'s write in both
  • T₂ has final write in both

• NOT conflict-serializable:

  • w₁(X) before w₂(X) implies T₁ < T₂
  • But we'd need to prove equivalence to a serial schedule
  • The precedence graph has edge T₁→T₂, but T₁'s write is "useless"

Such schedules with "blind writes" that get overwritten are view-serializable but not conflict-serializable.

Given two schedules, we can test conflict equivalence through a systematic process:

Algorithm: Testing Conflict Equivalence

Input: Two schedules S₁ and S₂ over the same transactions
Output: True if S₁ ≡c S₂, False otherwise

1. Verify both schedules have the same transactions and operations
   - If not, return False

2. Find all conflicting pairs of operations:
   - For each pair of transactions (Tᵢ, Tⱼ) where i ≠ j
   - For each data item X accessed by both
   - Check if at least one access is a write
   - If so, add (opᵢ, opⱼ) to conflict set

3. For each conflicting pair:
   - Determine the order in S₁
   - Determine the order in S₂
   - If orders differ, return False

4. Return True

Complexity Analysis

• Step 2: O(n² × m²) where n = transactions, m = operations per transaction
• Step 3: O(|conflicts| × m) to find positions
• Overall: O(n² × m²)—polynomial in input size

This polynomial complexity makes conflict equivalence testing practical for real systems.

With equivalence defined, we can formally define serializability:

Conflict Serializability

Definition: A schedule S is conflict serializable if it is conflict equivalent to some serial schedule.

S is conflict serializable  ⟺  ∃ serial schedule Ss : S ≡c Ss

View Serializability

Definition: A schedule S is view serializable if it is view equivalent to some serial schedule.

S is view serializable  ⟺  ∃ serial schedule Ss : S ≡v Ss

The Hierarchy

Conflict Serializable ⊂ View Serializable ⊂ All Schedules

- All conflict-serializable schedules are view-serializable
- Not all view-serializable schedules are conflict-serializable
- Many schedules are neither

Testing Conflict Serializability

To test if S is conflict serializable, we could:

Naive approach:

1. Generate all n! serial schedules
2. Test conflict equivalence with each
3. If any match, S is serializable

This is O(n! × test_cost)—impractical!

Better approach: Precedence Graph

Instead of comparing with all serial schedules, we construct a precedence graph (also called a serializability graph) and check for cycles:

• Nodes: One node per transaction
• Edges: Tᵢ → Tⱼ if Tᵢ has a conflicting operation before Tⱼ's conflicting operation
• Test: S is conflict-serializable if and only if the precedence graph is acyclic

This reduces testing to O(V + E) graph traversal—polynomial time!

The next page covers precedence graphs in complete detail.