Schedules in DBMS-
Before you go through this article, make sure that you have gone through the previous article on Schedules in DBMS.
We have discussed-
- A schedule is the order in which the operations of multiple transactions appear for execution.
- Serial schedules are always consistent.
- Non-serial schedules are not always consistent.
In DBMS, schedules may be classified as-
In this article, we will discuss about Serializability in DBMS.
Serializability in DBMS-
- Some non-serial schedules may lead to inconsistency of the database.
- Serializability is a concept that helps to identify which non-serial schedules are correct and will maintain the consistency of the database.
If a given non-serial schedule of ‘n’ transactions is equivalent to some serial schedule of ‘n’ transactions, then it is called as a serializable schedule.
Serializable schedules behave exactly same as serial schedules.
Thus, serializable schedules are always-
Serial Schedules Vs Serializable Schedules-
|Serial Schedules||Serializable Schedules|
|No concurrency is allowed.|
Thus, all the transactions necessarily execute serially one after the other.
|Concurrency is allowed.|
Thus, multiple transactions can execute concurrently.
|Serial schedules lead to less resource utilization and CPU throughput.||Serializable schedules improve both resource utilization and CPU throughput.|
|Serial Schedules are less efficient as compared to serializable schedules.|
(due to above reason)
|Serializable Schedules are always better than serial schedules.|
(due to above reason)
Types of Serializability-
Serializability is mainly of two types-
- Conflict Serializability
- View Serializability
In this article, we will discuss about Conflict Serializability.
Learn about View Serializability.
If a given non-serial schedule can be converted into a serial schedule by swapping its non-conflicting operations, then it is called as a conflict serializable schedule.
Two operations are called as conflicting operations if all the following conditions hold true for them-
- Both the operations belong to different transactions
- Both the operations are on the same data item
- At least one of the two operations is a write operation
Consider the following schedule-
In this schedule,
- W1 (A) and R2 (A) are called as conflicting operations.
- This is because all the above conditions hold true for them.
Checking Whether a Schedule is Conflict Serializable Or Not-
Follow the following steps to check whether a given non-serial schedule is conflict serializable or not-
Find and list all the conflicting operations.
Start creating a precedence graph by drawing one node for each transaction.
- 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.
- This ensures that Ti gets executed before Tj.
- Check if there is any cycle formed in the graph.
- If there is no cycle found, then the schedule is conflict serializable otherwise not.
- By performing the Topological Sort of the Directed Acyclic Graph so obtained, the corresponding serial schedule(s) can be found.
- Such schedules can be more than 1.
Next Article-Practice Problems On Conflict Serializability
Get more notes and other study material of Database Management System (DBMS).
Watch video lectures by visiting our YouTube channel LearnVidFun.