Serializability in Database Management
Systems (DBMS)
1. Introduction
In a Database Management System (DBMS), multiple transactions often execute concurrently
to improve system performance, maximize resource utilization, and reduce user response time.
However, concurrent execution of transactions can lead to data inconsistency if not properly
controlled.
To ensure correctness of concurrent transaction execution, DBMS uses the concept of
serializability. Serializability is a fundamental theory that determines whether the concurrent
execution of transactions produces results that are equivalent to some serial execution of the
same transactions.
In simple terms, serializability ensures that concurrency does not affect the correctness of
the database.
2. Transactions and Schedules
2.1 Transaction
A transaction is a logical unit of work that consists of one or more database operations such as:
• Read (R)
• Write (W)
• Commit (C)
• Abort (A)
A transaction must satisfy the ACID properties:
• Atomicity
• Consistency
• Isolation
• Durability
2.2 Schedule
A schedule represents the order in which operations of multiple transactions are executed.
Types of schedules:
1. Serial Schedule
2. Non-Serial (Concurrent) Schedule
2.3 Serial Schedule
A serial schedule executes one transaction completely before starting another.
Example:
T1: R(A) W(A) C
T2: R(A) W(A) C
Serial order: T1 → T2 or T2 → T1
Serial schedules are always correct, but they are inefficient because they do not allow
concurrency.
2.4 Non-Serial Schedule
In a non-serial schedule, operations of transactions are interleaved.
Example:
T1: R(A)
T2: R(A)
T1: W(A)
T2: W(A)
Non-serial schedules improve performance but may cause problems like:
• Lost update
• Dirty read
• Unrepeatable read
3. Serializability Concept
A schedule is said to be serializable if its effect on the database is equivalent to a serial
schedule.
Goal of serializability:
To allow concurrency while maintaining database consistency.
Serializability focuses on logical correctness, not the exact execution order.
4. Types of Serializability
There are two main types of serializability:
1. Conflict Serializability
2. View Serializability
5. Conflict Serializability
5.1 Conflicting Operations
Two operations are said to conflict if:
1. They belong to different transactions
2. They access the same data item
3. At least one of them is a write operation
Types of conflicting pairs:
• Read–Write (RW)
• Write–Read (WR)
• Write–Write (WW)
Read–Read (RR) does not cause conflict.
5.2 Conflict Serializable Schedule
A schedule is conflict serializable if it can be transformed into a serial schedule by swapping
non-conflicting operations.
5.3 Precedence Graph (Serialization Graph)
A precedence graph is used to test conflict serializability.
Construction Rules:
• Each transaction is a node
• Draw a directed edge Ti → Tj if:
o Ti’s operation conflicts with Tj’s operation
o Ti’s operation occurs before Tj’s operation
5.4 Testing Conflict Serializability
• If the precedence graph has no cycle, the schedule is conflict serializable
• If the graph contains a cycle, the schedule is not conflict serializable
5.5 Example
Schedule:
T1: R(A) W(A)
T2: R(A) W(A)
Conflicts:
• T1 W(A) → T2 R(A)
• T2 W(A) → T1 R(A)
Graph:
T1 → T2
T2 → T1
Cycle exists → Not conflict serializable
6. View Serializability
6.1 Definition
A schedule is view serializable if it is view equivalent to a serial schedule.
View equivalence focuses on what values are read and written, rather than the order of
conflicting operations.
6.2 Conditions for View Equivalence
Two schedules are view equivalent if:
1. The initial read of a data item is the same in both schedules
2. Each read operation reads the same value written by the same transaction
3. The final write on each data item is done by the same transaction
6.3 View Serializable Schedule
A schedule is view serializable if it is view equivalent to some serial schedule.
6.4 Relationship Between Conflict and View Serializability
• All conflict serializable schedules are view serializable
• Not all view serializable schedules are conflict serializable
View serializability is more general but harder to test.
6.5 Blind Writes
Schedules containing blind writes (write without read) may be:
• View serializable
• Not conflict serializable
Example:
T1: W(A)
T2: W(A)
7. Comparison: Conflict vs View Serializability
Feature Conflict Serializability View Serializability
Based on Conflicting operations Read-write relationships
Testing Easy (graph-based) NP-complete
Practical use Widely used Rarely implemented
Strictness More restrictive Less restrictive
8. Problems Caused by Non-Serializable Schedules
8.1 Lost Update
Two transactions overwrite each other’s updates.
8.2 Dirty Read
A transaction reads uncommitted data from another transaction.
8.3 Unrepeatable Read
A transaction reads different values for the same data item.
9. Serializability and Concurrency Control
To ensure serializability, DBMS uses concurrency control protocols:
9.1 Lock-Based Protocols
• Two-Phase Locking (2PL)
• Strict 2PL
9.2 Timestamp-Based Protocols
• Timestamp Ordering
9.3 Validation-Based Protocols
• Optimistic Concurrency Control
These protocols ensure that only serializable schedules are produced.
10. Two-Phase Locking (2PL) and Serializability
2PL guarantees conflict serializability.
Phases:
1. Growing Phase – locks are acquired
2. Shrinking Phase – locks are released
Variants:
• Basic 2PL
• Strict 2PL
• Rigorous 2PL
11. Importance of Serializability
• Maintains database consistency
• Ensures correctness of concurrent transactions
• Prevents anomalies
• Forms the theoretical basis of concurrency control
12. Advantages and Limitations
Advantages
• Ensures correctness
• Allows concurrency with safety
• Prevents inconsistent database states
Limitations
• Can reduce concurrency
• Overhead of locks and graphs
• View serializability is difficult to test
13. Conclusion
Serializability is a cornerstone concept in DBMS that ensures safe concurrent execution of
transactions. By guaranteeing that concurrent schedules behave like serial ones, serializability
preserves database consistency while enabling efficient system performance. Conflict
serializability provides a practical and widely used approach, while view serializability offers a
more general theoretical framework. Together, these concepts form the foundation of modern
concurrency control mechanisms in database systems.