Types of Serializability and Tests for Serializability

Definition

Serializability is a correctness criterion for concurrent transactions in a database management system. A schedule is considered "serializable" if its outcome (the final state of the database and the values read by transactions) is equivalent to the outcome of some serial execution of the same set of transactions, where transactions are executed one after another without any overlap.

Main Content

1. Conflict Serializability

• A schedule is conflict-serializable if it can be transformed into a serial schedule by swapping non-conflicting adjacent operations.
• Two operations conflict if they belong to different transactions, access the same data item, and at least one of them is a write operation (e.g., Read-Write, Write-Read, or Write-Write).

2. View Serializability

• A schedule is view-serializable if its "view" is equal to the view of some serial schedule.
• Two schedules are view-equivalent if the initial reads, subsequent reads, and final writes for every data item remain the same in both schedules.

3. Recoverable and Cascadeless Schedules

• A schedule is recoverable if, for every pair of transactions T1 and T2 such that T2 reads a data item previously written by T1, the commit operation of T1 appears before the commit operation of T2.
• Cascadeless schedules prevent "cascading rollbacks" by ensuring that a transaction only reads data from transactions that have already committed.

Working / Process

1. Constructing a Precedence Graph (Conflict Test)

• Create a directed graph where nodes represent the transactions in the schedule.
• Draw an edge from Ti to Tj if an operation in Ti conflicts with an operation in Tj and Ti's operation appears earlier in the schedule.
• If the graph contains no cycles, the schedule is conflict-serializable.

Precedence Graph Example:
T1 ---> T2
^       |
|       v
+------ T3
(Cycle T1 -> T2 -> T3 -> T1 indicates non-serializable)

2. Testing for View Serializability

• Check if the schedule is conflict-serializable (if it is, it is also view-serializable).
• If it is not conflict-serializable, verify if it satisfies the conditions of view-equivalence:
  • Initial Read: Each data item must be read from the same transaction in both schedules.
  • Intermediate Read: If Ti reads a value written by Tj, it must do so in both schedules.
  • Final Write: The final write for each data item must be performed by the same transaction in both schedules.

3. Analyzing Cycles

• The presence of a cycle in the Precedence Graph confirms that the execution order creates a circular dependency.
• If a cycle exists, the system cannot guarantee that the concurrent execution will produce the same result as any serial execution.

Advantages / Applications

• Ensures Database Consistency: Prevents data corruption by guaranteeing that concurrent transactions do not result in inconsistent states.
• Increases Concurrency: Allows multiple transactions to run simultaneously while maintaining the illusion of serial execution, maximizing throughput.
• Deadlock Detection: Precedence graphs are used in practical database engines to identify and resolve circular dependencies between transactions.

Summary

Serializability ensures that concurrent database transactions produce the same results as if they were run one by one. It uses methods like Precedence Graphs to detect conflicts, ensuring data integrity and consistency. Key terms to remember: Conflict Equivalence, View Equivalence, Precedence Graph, and Cycles.