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.
Serializable Schedules-
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.
Characteristics-
Serializable schedules behave exactly same as serial schedules.
Thus, serializable schedules are always-
- Consistent
- Recoverable
- Casacadeless
- Strict
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.
Conflict 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.
Conflicting Operations-
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
Example-
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-
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.
- This ensures that Ti gets executed before Tj.
Step-04:
- Check if there is any cycle formed in the graph.
- If there is no cycle found, then the schedule is conflict serializable otherwise not.
NOTE-
- 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.
