Introduction to Serializability in DBMS
Transactions in a database correspond to the set of instructions that are executed to achieve a target. All the transactions that take place in a database by theory should satisfy the ACID property. ACID is the acronym used to define transaction properties such as Atomicity, Consistency, Isolation, and Durability. A single transaction may contain one or more sets of independent instructions for accessing (read) or modifying (write) the huge data stored in a database. A collection of transactions becomes a schedule. Scheduling multiple transactions is necessary to maintain the execution order and to avoid the overlap of data operations.
Scheduling in DBMS is majorly classified into Serial and Non-Serial Schedules. As a part of transaction management, it is important to verify if a non-serial schedule is serializable especially when the transactions have concurrent execution. A given non-serial schedule of ‘n’ Transactions is said to be serializable if there exists some kind of equivalent serial schedule to the same ‘n’ transactions.
What is Serializability in DBMS?
Serial schedule both by definition and execution means that the transactions bestowed upon it will take place serially, that is, one after the other. This leaves no place for inconsistency within the database. But, when a set of transactions are scheduled non-serially, they are interleaved leading to the problem of concurrency within the database. Non-serial schedules do not wait for one transaction to complete for the other one to begin. Serializability in DBMS decides if an interleaved non-serial schedule is serializable or not.
Example of Serializability
Consider 2 schedules, Schedule1 and Schedule2:
- Schedule1 is a serial schedule consisting of Transaction1 and Transaction2 wherein the operations on data item A (A1 and A2) are performed first and later the operations on data item B (B1 and B2) are carried out serially.
- Schedule2 is a non-serial schedule consisting of Transaction1 and Transaction2 wherein the operations are interleaved.
Explanation: In the given scenario, schedule2 is serializable if the output obtained from both Schedule2 and Schedule1 are equivalent to one another In a nutshell, a transaction within a given non-serial schedule is serializable if its outcome is equivalent to the outcome of the same transaction when executed serially.
Types of Serializability
A schedule can be checked for serializability in one of the 3 methods mentioned below:
1. Result Equivalent Schedule
- Two schedules, S1 and S2 are said to result equivalent if they produce the same output obtained when the schedules are serially executed.
- Often, this kind of schedule is given the least significance since the result derived are mainly focussed on the output which in some cases may vary for the same set of inputs or might produce the same output for a different set of inputs.
2. Conflict Equivalent Schedule
When either of a conflict operation such as Read-Write or Write-Read or Write-Write is implemented on the same data item at the same time within different transactions then the schedule holding such transactions is said to be a conflict schedule. The prerequisites for such conflict schedule are:
- The conflict operations are to be implemented on the same data item.
- The conflict operations (RW, WR, WW) must take place within different transactions.
- At least one of the conflict operations must be the write operation.
- Two Read operations will not create any conflict.
Two schedules (one being serial schedule and another being non-serial) are said to be conflict serializable if the conflict operations in both the schedules are executed in the same order.
Example:
Consider 2 schedules, Schedule1 and Schedule2,
Schedule2 (a non-serial schedule) is considered to be conflict serializable when its conflict operations are the same as that of Shedule1 (a serial schedule).
3. View Equivalent Schedule
Two schedules (one being serial schedule and another being non-serial) are said to be view serializable if they satisfy the rules for being view equivalent to one another.
The rules to be upheld are:
- Initial values of the data items involved within a schedule must be the same.
- Final values of the data items involved within a schedule must be the same.
- The number of WR operations performed must be equivalent for the schedules involved.
Example:
Consider 2 schedules, Schedule1 and Schedule2:
The (non-serial) Schedule2 is considered as a view equivalent of the (serial) Schedule1, when the 3 rules of view serializability are satisfied. For the example shown above,
- The Initial transaction of read operation on the data items A and B both begin at T1
- The Final transaction of write operations on the data items A and B both end at T2
- The number of updates from write-read operations are 2 in both the cases
Hence satisfying all the rules required, Schedule2 becomes view serializable w.r.t Schedule1.
Benefits of Serializability in DBMS
Let’s first understand the difference between a serial and non-serial schedule for a better understanding of the benefits that serializability provides. In the case of a serial schedule, the multiple transactions involved are executed one after the other sequentially with no overlap. This helps maintain the consistency in the database but limits the scope of concurrency and often a smaller transaction might end up waiting for a long time due to an execution of a previous longer transaction. Serial schedule also consumes a lot of CPU resources which gets wasted due to the serial execution.
In the case with a non-serial schedule, the multiple transactions executed are interleaved leading to inconsistency in the database but at the same time helps overcome the disadvantages of a serial schedule such as concurrent execution and wastage of CPU resources.
It’s established that the execution of multiple transactions in a non-serial schedule takes place concurrently. And because of the multiple combinations involved, the output obtained may be incorrect at times which cannot be afforded. This is where serializability comes into the picture and help us determine if the output obtained from a parallelly executed schedule is correct or not.
In other words, Serializability serves as a measure of correctness for the transactions executed concurrently. It serves a major role in concurrency control that is crucial for the database and is considered to provide maximum isolation between the multiple transactions involved. The process of Serializability can also help in achieving the database consistency which otherwise is not possible for a non-serial schedule.
Conclusion
- Serializable means obtaining an equivalent output as of a serial schedule for the same ‘n’ number of transactions.
- Serializability helps preserve the consistency and concurrency of a database.
- There are 2 methods widely used to check serializability i.e. Conflict equivalent and View equivalent.
- As a rule of thumb, it can be stated that all conflict serializable schedules can be view serializable, but all view serializable schedules may or may not be conflict serializable.
Recommended Articles
This is a guide to Serializability in DBMS. Here we discuss what is Serializability in DBMS along with examples, types and benefits. You can also go through our other related articles to learn more –
