Introduction
A database can interleave operations from multiple transactions to handle concurrent work. However, an interleaved execution should not produce unexpected effects simply because transactions overlap. Serializability provides a way to reason about this correctness.
Conflict serializability and view serializability compare an interleaved schedule with a serial schedule using different rules. Understanding these rules helps explain which operation orders are safe, how dependency graphs work, and why matching final values alone is insufficient.
What Is Serializability?
A schedule specifies the order in which transaction operations execute while preserving the operation order inside each transaction.
A serial schedule executes one transaction completely before another begins. A serializable schedule may interleave transactions, but it is equivalent to some serial execution under the equivalence rule being considered.
For example, an interleaved execution might be equivalent to T1 followed by T2. It does not need to be equivalent to every possible serial order.
Serializability assumes that each transaction performs valid work when executed alone. It controls interactions between transactions; it does not correct faulty business logic.
Example Table and Schedule Notation
The examples use an Account table containing an account identifier, holder name, and balance.
Account: initial data
AccountID | HolderName | Balance |
|---|---|---|
1 | Asha | 1000.00 |
2 | Ravi | 500.00 |
AccountID is the primary key. In the schedules below, A means Asha’s balance and B means Ravi’s balance.
The notation is:
R1(A): Transaction T1 reads A.W1(A): Transaction T1 writes A.C1: Transaction T1 commits.
The number identifies the transaction. For example, R2(B) means that T2 reads Ravi’s balance.
These symbols describe a schedule. They are not SQL commands. Each conceptual example begins with the initial table above.
Which Operations Conflict?
Two operations conflict when all three conditions hold:
They belong to different transactions.
They access the same data item.
At least one operation is a write.
Operation pair | Conflict? | Reason |
|---|---|---|
| No | Both only read A. |
| Yes | Changing their order can change what T1 reads. |
| Yes | Changing their order can change what T2 reads. |
| Yes | Changing their order can change the final writer. |
| No | They access different data items. |
A conflict is an ordering dependency, not automatically an error. A correct schedule can contain many conflicts, provided their ordering is consistent with a serial execution.
Conflict Serializability
Two schedules are conflict equivalent when they contain the same operations of the same transactions and preserve the relative order of every conflicting pair.
A schedule is conflict serializable if it is conflict equivalent to a serial schedule.
Another way to understand this is through swaps: adjacent, non-conflicting operations from different transactions can be exchanged without changing their relevant effects. If such swaps can transform a schedule into a serial schedule, it is conflict serializable.
Testing with a Precedence Graph
A precedence graph, also called a conflict graph, represents the ordering requirements between transactions.
To construct it:
Create one node for each transaction.
Find conflicting operations from different transactions.
Add an edge from the transaction with the earlier operation to the transaction with the later operation.
For example, T1 → T2 means T1 must precede T2 in a conflict-equivalent serial order.
The result is determined by cycles:
No directed cycle: The schedule is conflict serializable.
A directed cycle exists: The schedule is not conflict serializable.
An ordering of the nodes that respects every edge is called a topological order. It gives an equivalent serial transaction order. More than one order may be possible.
Example: A Conflict-Serializable Schedule
Objective: T1 adds 100 to Asha’s balance. T2 adds 50 to Ravi’s balance and then adds 200 to Asha’s balance.
Step | T1 | T2 |
|---|---|---|
1 |
| |
2 |
| |
3 |
| |
4 |
| |
5 |
| |
6 |
| |
7 |
| |
8 |
|
The transactions overlap because T2 reads B before T1 finishes.
The conflicting pairs on A all require the same direction:
Earlier operation | Later operation | Required edge |
|---|---|---|
|
| T1 → T2 |
|
| T1 → T2 |
|
| T1 → T2 |
T1 never accesses B, so T2’s operations on B introduce no additional edges.
The graph contains only T1 → T2, with no cycle. Therefore, the schedule is conflict serializable, equivalent to T1 followed by T2.
Expected final table:
AccountID | HolderName | Balance |
|---|---|---|
1 | Asha | 1300.00 |
2 | Ravi | 550.00 |
Building a Precedence Graph
Example: A Cycle in the Graph
Consider the following operation order on Asha’s balance:
R1(A), R2(A), W1(A), W2(A)R1(A) occurs before W2(A), producing T1 → T2. However, R2(A) occurs before W1(A), producing T2 → T1.
These edges form a cycle, so the schedule is not conflict serializable.
The graph test establishes this conclusion without needing the exact numeric values written. A cycle does not, by itself, settle whether a schedule is view serializable.
When conflicts form a cycle
View Serializability
View equivalence compares where reads obtain their values and which transaction performs the final write.
Two schedules containing the same transaction operations are view equivalent when all three conditions hold:
Condition | What must remain the same? |
|---|---|
Initial reads | A read that obtains the initial value of a data item must still obtain its initial value. |
Reads-from relationships | A read that obtains a value from a particular write must obtain its value from that same write. |
Final writers | The transaction performing the final write on each data item must remain the same. |
A schedule is view serializable if it is view equivalent to a serial schedule.
In the earlier conflict-serializable example, T2 reads A from T1’s write. The equivalent serial order, T1 followed by T2, preserves this relationship.
Preserving only the numeric result is insufficient. Two different writes might happen to store the same number, but reading from different writes does not satisfy the reads-from condition.
Blind Writes: View Serializable but Not Conflict Serializable
A blind write writes a data item without first reading that item in the same transaction. For example, setting a balance to a fixed value can be represented as a blind write in a theoretical schedule.
Consider these transactions:
T1: Writes A as 1100.00, then writes A as 1300.00.
T2: Writes A as 1200.00.
Neither transaction reads A.
Interleaved schedule:
Step | Operation | Value of A after the operation |
|---|---|---|
1 | T1 writes A as 1100.00 | 1100.00 |
2 | T2 writes A as 1200.00 | 1200.00 |
3 | T1 writes A as 1300.00 | 1300.00 |
For conflict serializability:
T1’s first write precedes T2’s write, giving T1 → T2.
T2’s write precedes T1’s second write, giving T2 → T1.
The graph contains a cycle, so the schedule is not conflict serializable.
For view serializability, compare it with the serial order T2 followed by T1:
T2 writes 1200T1 writes 1100T1 writes 1300There are no reads, so there are no initial-read or reads-from relationships to preserve. T1 is the final writer of A in both schedules.
Therefore, the interleaved schedule is view serializable.
Final table in both schedules:
AccountID | HolderName | Balance |
|---|---|---|
1 | Asha | 1300.00 |
2 | Ravi | 500.00 |
This is a theoretical read/write schedule. It is not a claim that MySQL or PostgreSQL will allow these overlapping writes to the same row in this order. Their concurrency controls can block or reject conflicting work.
A blind write does not automatically make a schedule view serializable. It explains how some schedules can be view serializable without being conflict serializable.
Blind writes and view serializability
Conflict vs. View Serializability
Aspect | Conflict serializability | View serializability |
|---|---|---|
Main requirement | Preserve the order of conflicting operations. | Preserve initial reads, reads-from relationships, and final writers. |
Typical check | Construct a precedence graph and test for cycles. | Check whether a serial order satisfies all view-equivalence conditions. |
Scope | More restrictive. | More general. |
Blind writes | Can create cycles that cause the test to fail. | Can allow some schedules rejected by the conflict test. |
Testing difficulty | Efficient graph-based test. | More difficult to test in general. |
Every conflict-serializable schedule is view serializable, but the reverse is not always true.
In the standard read/write model, a view-serializable schedule that is not conflict serializable must contain blind writes. Their presence is necessary for this difference, but does not prove view serializability.
Serializability also differs from recoverability. A serializability test does not replace checks about reading uncommitted data, commit order, or safe rollback.
A Compact SQL Example
Objective: Implement the transactions from the conflict-serializable example and show their equivalent serial result.
The starting data is:
AccountID | HolderName | Balance |
|---|---|---|
1 | Asha | 1000.00 |
2 | Ravi | 500.00 |
T1 adds 100 to Asha’s balance. T2 adds 50 to Ravi’s balance and then adds 200 to Asha’s balance.
Consider the following queries to create the table and execute T1 followed by T2 at the SERIALIZABLE isolation level.
CREATE TABLE Account ( AccountID INT PRIMARY KEY, HolderName VARCHAR(50) NOT NULL, Balance DECIMAL(10, 2) NOT NULL);START TRANSACTION;INSERT INTO Account (AccountID, HolderName, Balance)VALUES (1, 'Asha', 1000.00), (2, 'Ravi', 500.00);COMMIT;-- T1: Add 100 to Asha's balance.SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;START TRANSACTION;UPDATE AccountSET Balance = Balance + 100WHERE AccountID = 1;COMMIT;-- T2: Add 50 to Ravi, then 200 to Asha.SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;START TRANSACTION;UPDATE AccountSET Balance = Balance + 50WHERE AccountID = 2;UPDATE AccountSET Balance = Balance + 200WHERE AccountID = 1;COMMIT;SELECT AccountID, HolderName, BalanceFROM AccountORDER BY AccountID;BEGIN ISOLATION LEVEL SERIALIZABLE starts a transaction with serializable isolation. The expression Balance = Balance + 100 increases the stored balance by 100.
Expected result for both versions:
AccountID | HolderName | Balance |
|---|---|---|
1 | Asha | 1300.00 |
2 | Ravi | 550.00 |
The scripts execute an actual serial order because T1 commits before T2 starts. They demonstrate the reference result to which the earlier interleaved schedule is conflict equivalent.
SERIALIZABLE does not require every transaction in the database to run one at a time. When transactions overlap through separate connections, the database coordinates their execution to provide a serializable outcome. Conflicts can cause waiting, deadlocks, or serialization failures; an aborted transaction may need to be retried in full.
The SQL isolation level does not provide a command for selecting “conflict serializability” or “view serializability.” Those are theoretical ways of analyzing schedules, while the database implements isolation through its own concurrency-control mechanisms.
Summary
Conflict serializability preserves the order of conflicting operations. Its precedence graph must be acyclic, and an ordering that respects the graph’s edges gives an equivalent serial execution. Conflicts are dependencies, not automatic evidence of an incorrect schedule.
View serializability preserves initial reads, reads-from relationships, and final writers. It includes all conflict-serializable schedules and some additional schedules involving blind writes. Correct analysis requires these relationships, not just a matching final table.
Be the first to add a comment.