Conflict Serializable Schedule
- A schedule is called conflict serializability if after swapping of non-conflicting operations, it can transform into a serial schedule.
- The schedule will be a conflict serializable if it is conflict equivalent to a serial schedule.
Conflicting Operations
The two operations become conflicting if all conditions satisfy:
- Both belong to separate transactions.
- They have the same data item.
- They contain at least one write operation.
Example:
Swapping is possible only if S1 and S2 are logically equal.
Here, S1 = S2. That means it is non-conflict.
Here, S1 ≠ S2. That means it is conflict.
Conflict Equivalent
In the conflict equivalent, one can be transformed into another by swapping non-conflicting operations. In the given example, S2 is conflict equivalent to S1 (S1 can be converted to S2 by swapping non-conflicting operations).
Two schedules are said to be conflict equivalent if and only if:
- They contain the same set of the transaction.
- If each pair of conflict operations are ordered in the same way.
Example:
Schedule S2 is a serial schedule because, in this, all operations of T1 are performed before starting any operation of T2. Schedule S1 can be transformed into a serial schedule by swapping non-conflicting operations of S1.
After swapping of non-conflict operations, the schedule S1 becomes:
T1 | T2 |
---|---|
Read(A) Write(A) Read(B) Write(B) | Read(A) Write(A) Read(B) Write(B) |
Since, S1 is conflict serializable.
0 comments:
Post a Comment
Thanks