Calculating Number of conflict serializable schedules.
A schedule is said to be conflict-serializable when the schedule is conflict-equivalent to one or more serial schedules.
We can have to serial schedules $S_1 → S_2$ and $S_2 → S_1$
CASE 1. Number of conflict serializabe schedulle that is equivalent to $S_1 → S_2$
Here the colourful arrows represents conflicts, out of these conflicts we can remove the purple arrows since they can be inferred from the diagram.
Rearranging the nodes of the diagram , we get
As we can see the number of conflict serializable schedules possible= toplogical sort possible $= \frac{3!}{2!} = 3$
CASE 2. Number of conflict serializable schedule that is equivalent to $S_2 → S_1$
Here the colourful arrows represents conflicts, out of these conflicts we can remove the purple arrows since they can be inferred from the diagram.
Rearranging the nodes of the diagram , we get
As we can see the number of conflict serializable schedules possible= toplogical sort possible $= \frac{4!}{2!2!} = 6$
$\therefore$ The number of conflict serializable schedules $= 3+6 =9$
Calculating Number of view serializable schedules.
A schedule is view serializable if
- The Order of initial reads are same as some serial schedule
- The Order of W-R conflicts are same as in some serial schedule
- The Order of final writes are same as in some serial schedule
CASE 1. Number of view serializabe schedule that is equivalent to $S_1 → S_2$
Here the colourful arrows represents conflicts, out of these conflicts we can remove the purple arrows since they can be inferred from the diagram.
Rearranging the nodes of the diagram , we get
As we can see the number of view serializable schedules possible= toplogical sort possible $= \frac{3!}{2!} = 3$
CASE 2. Number of view serializable schedule that is equivalent to $S_2 → S_1$
Here the colorful arrows represents conflicts, out of these conflicts we can remove the purple and green arrows since they can be inferred from the diagram.
Rearranging the nodes of the diagram , we get
As we can see the number of view serializable schedules possible= toplogical sort possible $= \frac{4!}{2!2!} = 6$
$\therefore$ The number of view serializable schedules $= 3+6 =9$
$\text{Hence. the number of schedules that are view serializable but not conflict seriable = 9-9=0}$