Conflict Serializability

Imagine a busy banking system processing thousands of transactions simultaneously. At any given moment, multiple customers are transferring funds, checking balances, and making payments—all operating on shared account data. The database management system must orchestrate these concurrent operations in a way that preserves data integrity while maximizing throughput.

But how do we reason about whether a particular interleaving of operations is correct? How can we determine if concurrent execution produces the same results as running transactions one after another? The answer lies in the formal concept of a schedule—the fundamental abstraction for analyzing concurrent transaction execution.

A schedule is essentially a transcript of what happened: a precise, ordered record of every database operation executed by every transaction. Understanding schedules is the first step toward understanding serializability, the gold standard for concurrent transaction correctness.

A schedule (also called a history) is a sequence of operations from one or more transactions that represents a particular execution order. Formally, a schedule S over a set of transactions T = {T₁, T₂, ..., Tₙ} is a partially ordered list of operations where:

1. All operations are present: Every operation from every transaction in T appears exactly once in S
2. Transaction order is preserved: For any transaction Tᵢ, if operation O₁ precedes O₂ in Tᵢ, then O₁ must precede O₂ in S
3. Conflict operations are ordered: Any two conflicting operations must have a defined order in S

The schedule captures not just what operations occurred, but the precise order in which they executed across all participating transactions.

The Building Blocks: Transaction Operations

Schedules are composed of operations—the atomic units of database access. For serializability analysis, we focus on the following fundamental operations:

The subscript i identifies which transaction performs the operation. For example, r₁(A) means "Transaction T₁ reads data item A," while w₂(B) means "Transaction T₂ writes data item B."

Important: For conflict serializability analysis, we typically focus on read and write operations since conflicts arise from how transactions access shared data items. Commit and abort operations become critical when analyzing recoverability.

Understanding Data Items

A data item is the unit of data that transactions read and write. The granularity of data items varies depending on the system and analysis context:

• Attribute-level: Single column values (e.g., Account.balance)
• Tuple-level: Entire rows (most common in practice)
• Page-level: Disk pages containing multiple tuples
• Table-level: Entire relations
• Database-level: The entire database

For serializability theory, we abstract data items as simple named entities (A, B, X, Y, etc.) without specifying their physical representation. The key insight is that conflicts arise when two operations access the same data item.

Read vs. Write Operations

The behavior of operations determines whether conflicts can occur:

Read Operations (R(X)):

• Retrieves the current value of data item X
• Does not modify the database state
• Multiple reads of the same item do NOT conflict with each other
• Safe to execute concurrently with other reads

Write Operations (W(X)):

• Modifies the value of data item X
• Changes the database state
• Conflicts with any other operation (read or write) on the same item
• The order of writes determines the final database state

The Critical Insight: Reads are inherently compatible with each other, but writes introduce ordering dependencies. This asymmetry is the foundation of conflict analysis.

Schedules can be represented in several ways, each useful for different purposes. Mastering these representations is essential for analyzing serializability.

Linear (Sequence) Notation

The simplest representation lists operations in their execution order as a linear sequence:

S = r₁(A) r₂(A) w₁(A) w₂(A) r₁(B) w₁(B) c₁ c₂

This notation is compact and easy to write, making it ideal for exam questions and quick analysis. However, it can become unwieldy for schedules with many transactions.

Tabular Notation

A table format shows the temporal progression with each transaction in its own column:

This format makes it easy to visualize the interleaving and identify which transaction performs each operation.

Timeline Diagram

A visual timeline shows transactions as horizontal bars with operations marked along them:

T₁: ──r(A)────w(A)────r(B)────w(B)────c──────────────
         │         │
         ▼         ▼
T₂: ─────────r(A)────────w(A)────────────────────c───

Timeline diagrams excel at showing the temporal relationship between operations across transactions.

Formal Set Notation

For rigorous mathematical analysis, schedules can be defined as ordered sets:

S = (O, <S)

where:
- O is the set of all operations from all transactions
- <S is a partial order on O defining execution order

This formal notation is used in academic papers and advanced theoretical discussions.

Complete Schedules

A complete schedule satisfies two important properties:

1. All operations present: Every operation of every participating transaction appears in the schedule
2. All transactions terminated: Every transaction either commits or aborts (no pending transactions)

Complete schedules represent finished executions where all transactions have reached a final state. When analyzing serializability, we typically work with complete schedules because they represent the full picture of what happened.

Complete Schedule Example:
S = r₁(A) w₁(A) r₂(A) w₂(A) c₁ c₂

Both T₁ and T₂ have all their operations included and both have committed.

Incomplete Schedules

An incomplete schedule (also called a partial schedule or prefix) represents an execution in progress:

• Some transaction operations may not yet have executed
• Some transactions may not yet have committed or aborted
• Represents a snapshot of ongoing execution

Incomplete Schedule Example:
S' = r₁(A) r₂(A) w₁(A)

This is incomplete because:
- T₁ hasn't committed yet
- T₂ still has operations to perform
- Neither transaction has terminated

Why do incomplete schedules matter?

In real systems, the scheduler must make decisions before transactions complete. Concurrency control protocols must ensure that any incomplete schedule can be extended to a serializable complete schedule—or detect when this becomes impossible and abort transactions.

Interleaving is the mixing of operations from multiple concurrent transactions during execution. The DBMS interleaves transaction operations to maximize resource utilization and system throughput.

Why Interleave?

Consider a transaction that reads data, performs computation, and writes results:

T₁: READ (disk I/O) → COMPUTE (CPU) → WRITE (disk I/O)

During disk I/O, the CPU sits idle. During computation, the disk sits idle. If we run transactions one at a time (serially), resources are underutilized:

Serial execution (wasted resources):

CPU:  [idle][T₁ compute][idle][idle][T₂ compute][idle]
Disk: [T₁ read][idle][T₁ write][T₂ read][idle][T₂ write]

With interleaving, we can overlap I/O from one transaction with computation from another:

Interleaved execution (better utilization):

CPU:  [idle][T₁ compute][T₂ compute][idle]
Disk: [T₁ read][T₂ read][T₁ write][T₂ write]

The Combinatorial Explosion Problem

For n transactions, each with m operations, the number of possible interleavings is astronomically large. This is calculated as:

Number of interleavings = (n × m)! / (m!)ⁿ

Example: Just 3 transactions with 3 operations each:

• Total operations: 9
• Possible interleavings: 9! / (3!)³ = 362,880 / 216 = 1,680

Example: 5 transactions with 5 operations each:

• Total operations: 25
• Possible interleavings: 25! / (5!)⁵ ≈ 6.2 × 10¹⁴

This exponential growth makes exhaustive checking impractical. We need efficient algorithms—like precedence graphs—to determine serializability without examining every possible interleaving.

The Challenge: Among all possible interleavings, some produce correct results (equivalent to some serial execution), while others produce anomalies. The scheduler must either:

1. Only allow interleavings guaranteed to be correct (preventive approach)
2. Check each schedule for serializability (detective approach)

Schedules are classified into two fundamental categories based on the degree of interleaving:

Serial Schedules

A serial schedule executes transactions one at a time, with no interleaving. Each transaction runs to completion before the next one begins:

Serial Schedule (T₁ before T₂):
S₁ = r₁(A) w₁(A) r₁(B) w₁(B) c₁ r₂(A) w₂(A) c₂
        |____________T₁______________|  |____T₂____|              

Properties of Serial Schedules:

• Always correct: Since transactions don't overlap, there's no interference
• Order determines result: Different serial orders may produce different (but all valid) results
• Poor performance: Resources are underutilized
• Simple to reason about: No concurrency anomalies possible

For n transactions, there are exactly n! possible serial schedules (one for each ordering).

Concurrent (Non-Serial) Schedules

A concurrent schedule (also called interleaved schedule) has operations from different transactions mixed together:

Concurrent Schedule:
S₂ = r₁(A) r₂(A) w₁(A) r₁(B) w₂(A) w₁(B) c₁ c₂

Here, T₂'s operations are interspersed with T₁'s operations.

Properties of Concurrent Schedules:

• May or may not be correct: Depends on the specific interleaving
• Better performance: Improved resource utilization
• Complex analysis required: Must verify correctness
• Many more possibilities: Far more concurrent than serial schedules

Before we move to analyzing schedules for serializability, let's consolidate the essential properties that characterize schedules:

Structural Properties

Behavioral Properties

Performance Properties

Understanding schedules is not merely academic—it's the foundation for all database concurrency control. Here's why this matters:

1. Correctness Verification

Schedules give us a formal language to ask and answer: "Is this execution correct?" Without the schedule abstraction, we would have no systematic way to compare different executions or prove correctness properties.

2. Protocol Design

Every concurrency control protocol—two-phase locking, timestamp ordering, optimistic concurrency control, multi-version approaches—is designed to produce schedules with specific properties. Understanding schedules is essential to understanding why these protocols work.

3. Debugging Concurrency Issues

When concurrent transactions produce unexpected results, analyzing the execution as a schedule helps identify:

• Which operations conflicted
• Where the interleaving went wrong
• What properties were violated

4. Performance Tuning

Schedule analysis helps optimize transaction design:

• Minimizing lock duration
• Reducing conflict probability
• Choosing appropriate isolation levels

5. System Design Decisions

Architectural choices depend on schedule properties:

• What isolation level to default to
• Whether to use pessimistic vs. optimistic protocols
• How to balance consistency vs. availability

What's Next:

Now that we understand what schedules are and how to represent them, we need to explore serial schedules in depth. Serial schedules serve as our reference point—the "gold standard" of correctness that concurrent schedules must match. The next page examines serial schedules, their properties, and why they define what we mean by a "correct" execution.