Serializability of transactions

Serializability of transactions

When multiple transactions are running concurrently then there is a possibility that the database may be left in an inconsistent state.
Serializability is a concept that helps us to check which schedules are serializable.
A serializable schedule is the one that always leaves the database inconsistent state.
What is a serializable schedule?

A serializable schedule always leaves the database inconsistent state.
A serial schedule is always a serializable schedule because, in serial schedule, a transaction only starts when the other transaction finished execution.
However, a non-serial schedule needs to be checked for Serializability.
A serial schedule doesn’t allow concurrency, only one transaction executes at a time and the other stars when the already running transaction finished.

Conflict Serializability is one of the types of Serializability, which can be used to check whether a non-serial schedule is conflict serializable or not.
A schedule is called conflict serializable if we can convert it into a serial schedule after swapping its non-conflicting operations.
Conflicting operations

Two operations are said to be in conflict if they satisfy all the following three conditions:

In this schedule, W1 (A) and R2 (A) are called as conflicting operations.
This is because all the above conditions (1) (2) (3) hold true for them.
Follow the following steps to check whether a given non-serial schedule is conflict serializable or not-

Step-01: Find and list all the conflicting operations.
Step-02: Start creating a precedence graph by drawing one node for each transaction.
Step-03: Draw an edge for each conflict pair such that if Xi (V) and Yj (V) forms a conflict pair then draw an edge from Ti to Tj.

If there is no cycle found, then the schedule is conflict serializable otherwise not.

If a given schedule is found to be view equivalent to some serial schedule, then it is called as a view serializable schedule.
View Equivalent Schedules-

Consider two schedules S1 and S2 each consisting of two transactions T1 and T2.
Schedules S1 and S2 are called view equivalent if the following three conditions hold true for them-

For each data item X, if transaction Ti reads X from the database initially in schedule S1, then in schedule S2 also, Ti must perform the initial read of X from the database.
In short, “Initial readers must be same for all the data items”.

If transaction Ti reads a data item that has been updated by the transaction Tj in schedule S1, then in schedule S2 also, transaction Ti must read the same data item that has been updated by the transaction Tj.
In short, “Write-read sequence must be the same.”.

For each data item X, if X has been updated at last by transaction Ti in schedule S1, then in schedule S2 also, X must be updated at last by transaction Ti.
In short, “Final writers must be the same for all the data items”.

Check whether the given schedule is conflict serializable or not.
If the given schedule is conflict serializable, then it is surely viewed as serializable. Stop and report your answer.
If the given schedule does not conflict serializable, then it may or may not be view serializable. Go and check using other methods.
Note: All conflict serializable schedules are view serializable.
All view serializable schedules may or may not be conflict serializable.

Check if there exists any blind write operation. (Writing without reading is called as a blind write).
If there does not exist any blind write, then the schedule is surely not viewed as serializable. Stop and report your answer.
If there exists any blind write, then the schedule may or may not be view serializable. Go and check using other methods.
Note: No blind write means not a view serializable schedule.

In this method, try finding a view equivalent serial schedule.
By using the above three conditions, write all the dependencies.
Then, draw a graph using those dependencies.
If there exists no cycle in the graph, then the schedule is view serializable otherwise not.