Serial Schedule

Before databases supported concurrent execution, transactions ran one at a time. Transaction T₁ would complete entirely—every read, every write, every decision—before Transaction T₂ could begin. This sequential execution model, known as serial execution, represents the simplest guarantee of correctness.

When transactions execute serially, they cannot interfere with each other. There are no race conditions, no lost updates, no dirty reads. Each transaction observes a consistent database state, makes its changes, and leaves a consistent state for the next transaction. It's clean, simple, and provably correct.

The concept of a serial schedule formalizes this serial execution. Understanding serial schedules is essential because they serve as the definition of correctness for concurrent schedules. A concurrent schedule is considered correct if and only if it produces results equivalent to some serial schedule.

In database theory, serial schedules are not just a type of schedule—they are the benchmark by which all other schedules are judged.

A serial schedule is a schedule in which transactions execute sequentially without any interleaving of operations from different transactions.

Formal Definition:

Given a set of transactions T = {T₁, T₂, ..., Tₙ}, a schedule S is serial if and only if:

For every pair of transactions Tᵢ and Tⱼ (where i ≠ j), either:

• All operations of Tᵢ appear before all operations of Tⱼ in S, OR
• All operations of Tⱼ appear before all operations of Tᵢ in S

In other words, transactions appear as contiguous, non-overlapping blocks in the schedule.

Equivalent Definition:

A schedule S is serial if there exists an ordering (permutation) π of transactions such that S = Tπ(1) · Tπ(2) · ... · Tπ(n), where · denotes concatenation and each Tπ(k) is the complete sequence of operations for transaction Tπ(k).

The correctness of serial schedules stems from a fundamental property: complete isolation. When transactions execute serially, each transaction:

1. Observes a complete, consistent state: The database contains only the results of fully committed transactions
2. Operates without interference: No concurrent transaction can read or modify data during execution
3. Leaves a complete, consistent state: All changes are visible to subsequent transactions

The Isolation Guarantee

In a serial schedule, when transaction Tᵢ executes:

• All transactions before Tᵢ have already committed—their changes are final
• All transactions after Tᵢ haven't started—they can't see Tᵢ's uncommitted changes
• Tᵢ has exclusive access to the database for its entire duration

This provides perfect isolation—the 'I' in ACID at its strongest level.

Consistency Preservation

If we assume:

1. The database starts in a consistent state
2. Each individual transaction, if run alone on a consistent database, leaves it consistent

Then serial execution preserves consistency through induction:

Base case: Database starts consistent (given)

Inductive step: Transaction Tᵢ runs on consistent database
               → Tᵢ transforms it to another consistent state (by assumption 2)
               → Database still consistent for Tᵢ₊₁

Conclusion: Database remains consistent after all transactions

This is the theoretical foundation for database correctness: transactions are units of consistency preservation, and running them serially chains these preservations together.

For a given set of transactions, there are multiple possible serial schedules. The number of serial schedules equals the number of ways to order the transactions—a factorial relationship.

Counting Serial Schedules

For n transactions, the number of possible serial schedules is:

Number of serial schedules = n!

Examples:

• 2 transactions: 2! = 2 serial schedules
• 3 transactions: 3! = 6 serial schedules
• 4 transactions: 4! = 24 serial schedules
• 5 transactions: 5! = 120 serial schedules
• 10 transactions: 10! = 3,628,800 serial schedules

All Serial Schedules May Produce Different Results

Importantly, different serial schedules may leave the database in different final states. This is not a problem—all serial schedules are considered correct, even if they produce different outcomes.

If serial schedules are always correct, why don't databases just execute transactions serially? The answer is performance. Serial execution suffers from severe limitations that make it impractical for real-world systems.

Resource Underutilization

Modern databases operate on systems with multiple resources:

• CPU cores (often 16, 32, 64, or more)
• Disk channels and SSDs
• Network connections
• Memory bandwidth

Serial execution uses only one resource at a time per transaction:

Serial execution timeline:

Transaction: [Read from disk]→[CPU compute]→[Write to disk]→[Wait for commit]
CPU:         [----idle----][processing][---------idle----------]
Disk:        [--reading---][---idle---][---writing---][--idle--]

With serial execution, while one transaction waits for disk I/O, the CPU sits idle. While computing, the disk sits idle. This leads to utilization rates often below 20%.

Throughput Limitations

Consider a transaction that takes 100ms on average:

• Serial execution: 10 transactions/second maximum
• With interleaving: Could achieve 100+ transactions/second

For high-volume OLTP systems processing thousands of transactions per second, serial execution is simply not viable.

Latency Impact

Serial execution forces transactions to wait in line:

Scenario: 100 pending transactions, each taking 50ms

Serial execution:
- Transaction 1: Waits 0ms, completes at 50ms
- Transaction 50: Waits 2450ms, completes at 2500ms
- Transaction 100: Waits 4950ms, completes at 5000ms
- Average wait: ~2500ms

Concurrent execution (with 10 parallel streams, ideally):
- Transaction 100: Waits ~450ms, completes at ~500ms
- Average wait: ~250ms (10x improvement)

Given that serial schedules are correct but impractical, the database community developed a crucial insight:

A concurrent schedule is correct if it produces the same result as some serial schedule.

This principle, called serializability, defines correctness in terms of equivalence to serial execution. It allows databases to:

1. Execute transactions concurrently for performance
2. Still guarantee correct results by ensuring equivalence to serial execution

The Serializability Principle

┌─────────────────────────────────────────────────────────────┐
│                    SERIALIZABILITY PRINCIPLE                 │
│                                                             │
│  A concurrent schedule S is CORRECT if and only if          │
│  S is EQUIVALENT to some serial schedule Ss                 │
│                                                             │
│  S ≡ Ss  →  S is correct                                   │
│  S ≢ any Ss  →  S may be incorrect                         │
└─────────────────────────────────────────────────────────────┘

Notice we don't require equivalence to a specific serial schedule—just some serial schedule. This flexibility is important because different serial orders produce different (but all valid) results.

Types of Equivalence

The concept of "equivalence" can be defined in multiple ways, each leading to a different notion of serializability:

Conflict serializability (our focus) is the most practical:

• Efficiently testable using precedence graphs
• Sufficient for most real-world needs
• Forms the basis for protocols like Two-Phase Locking

View serializability is more permissive:

• Some additional schedules are view-serializable but not conflict-serializable
• Testing is NP-complete (computationally expensive)
• Rarely used in practice

Serial schedules possess several important properties beyond mere correctness. Understanding these properties helps clarify what we're trying to achieve with concurrent schedules.

Structural Properties

1. Transaction Contiguity

All operations of each transaction appear consecutively, with no interleaving:

Serial: [----T₁----][----T₂----][----T₃----]
Not:    [--T₁--][--T₂--][--T₁--][--T₃--]...

2. Total Ordering

Every pair of transactions has a defined before/after relationship:

• For any Tᵢ and Tⱼ, either Tᵢ < Tⱼ or Tⱼ < Tᵢ
• No circular or ambiguous orderings

3. Deterministic Conflict Resolution

For any two conflicting operations, the order is determined by the transaction order:

• If Tᵢ < Tⱼ, then all conflicts between Tᵢ and Tⱼ favor Tᵢ going first

Correctness Properties

4. Always Serializable (by definition)

Every serial schedule is trivially serializable—it's equivalent to itself:

• S_serial ≡ S_serial (conflict-equivalent)
• Conflict serializability is vacuously satisfied

5. Recoverable and Strict

Serial schedules are inherently recoverable and strict:

• No transaction reads uncommitted data (previous transactions already committed)
• No cascading aborts possible (nothing depends on uncommitted state)
• Recovery is straightforward (undo the single failed transaction)

6. Deadlock-Free

Deadlocks cannot occur in serial execution:

• No circular waits possible when only one transaction is active
• Resource allocation is never contested

Understanding the relationship between serial and concurrent schedules is fundamental to serializability theory.

The Schedule Space

All possible schedules for a set of transactions can be visualized as a containment hierarchy:

┌─────────────────────────────────────────────────┐
│            ALL POSSIBLE SCHEDULES                │
│                                                  │
│   ┌────────────────────────────────────────┐    │
│   │       SERIALIZABLE SCHEDULES           │    │
│   │                                        │    │
│   │   ┌─────────────────────────────┐     │    │
│   │   │    SERIAL SCHEDULES (n!)    │     │    │
│   │   │                             │     │    │
│   │   │ (Correct by definition)     │     │    │
│   │   └─────────────────────────────┘     │    │
│   │                                        │    │
│   │   (Correct concurrent schedules)       │    │
│   └────────────────────────────────────────┘    │
│                                                  │
│   (Incorrectly interleaved schedules)           │
└─────────────────────────────────────────────────┘

• Serial schedules are a tiny subset of all schedules (exactly n! of them)
• Serializable schedules include serial schedules plus equivalent concurrent schedules
• Non-serializable schedules are everything else—potentially incorrect

The Numbers Tell the Story

The disparity between serial and total schedules grows explosively:

Serial schedules become an infinitesimally small fraction of the total schedule space. This is why testing every schedule for equivalence to every serial schedule is impractical—we need smarter algorithms.