Testing of Serializability
When working with database schedules, ensuring serializability is one of the most important aspects of concurrency control. A Serialization Graph, also known as a Precedence Graph, is commonly used to test whether a given schedule is serializable or not.
Machine Learning Tutorial:–Click Here
Data Science Tutorial:-Click Here
Complete Advance AI topics:- CLICK HERE
Deep Learning Tutorial:- Click Here
What is a Precedence Graph?
For a given schedule S, we construct a graph G = (V, E):
- V (Vertices): Represents the set of transactions involved in the schedule.
- E (Edges): Represents dependencies between transactions.
An edge Ti → Tj is added if one of the following holds:
- Write–Read Conflict: Ti writes(Q) before Tj reads(Q).
- Read–Write Conflict: Ti reads(Q) before Tj writes(Q).
- Write–Write Conflict: Ti writes(Q) before Tj writes(Q).
Testing Serializability in DBMS
- If a precedence graph has a single edge Ti → Tj, it means all operations of Ti complete before Tj begins.
- If the graph contains a cycle, the schedule is non-serializable.
- If the graph is acyclic, the schedule is serializable.
Example 1: Schedule S1
Step-by-step conflict analysis:
- Read(A): In T1, no later writes → no edge
- Read(B): In T2, no later writes → no edge
- Read(C): In T3, no later writes → no edge
- Write(B): Later read by T3 → add edge T2 → T3
- Write(C): Later read by T1 → add edge T3 → T1
- Write(A): Later read by T2 → add edge T1 → T2
- Remaining writes: No new dependencies
Precedence Graph (S1): Contains a cycle.
➡ Conclusion: Schedule S1 is non-serializable.
Example 2: Schedule S2
Step-by-step conflict analysis:
- Read(A): In T4, no later writes → no edge
- Read(C): In T4, no later writes → no edge
- Write(A): Later read by T5 → add edge T4 → T5
- Read(B): In T5, no later writes → no edge
- Write(C): Later read by T6 → add edge T4 → T6
- Write(B): Later read by T6 → add edge T5 → T6
- Remaining writes: No new dependencies
Precedence Graph (S2): Contains no cycle.
➡ Conclusion: Schedule S2 is serializable.
Final Thoughts
Testing serializability ensures that concurrent transactions maintain the same correctness as if executed serially. Using precedence graphs, database systems can efficiently check conflicts and determine whether a schedule is safe for execution.
At UpdateGadh, we emphasize practical understanding—remember:
- Cycle → Non-Serializable
- No Cycle → Serializable
Complete Python Course with Advance topics:-Click Here
SQL Tutorial :-Click Here
Download New Real Time Projects :–Click here
testing of serializability in dbms
testing of serializability pdf
testing of serializability in dbms pdf
testing of serializability example
testing of serializability in dbms example
serializability in dbms
view serializability in dbms
conflict serializability in dbms
