I am learning about serializability and I am not sure that if view serializability bidirectional or unidirectional. What I am meaning that, if S is view equivalent to S’, is it always true that S’ is also view equivalent to S? I think I have a counter example to that but I am not sure if I am missing something.
Suppose we have two transactions T1, T2 and T3 where R(x) denotes a read and W(x) denotes a write operation on x:
- S: T3:R(x), T3:R(y), T2:W(x), T2:W(y), T1:R(x), T1:R(y)
- S’: T3:R(x), T3:R(y), T1:R(x), T2:W(x), T2:W(y), T1:R(y)
View equivalence has three conditions:
- If a data item is read by a transaction first, then it must be read by the same transaction first for all other schedules
- For each Write -> Read conflict on the same item, order must be preserved
- If a data item written by transaction last, then it must be written by the same transaction last for all other schedules.
Now if we check if S’ is view equivalent to S:
- T3 reads first for both the x and y in S’. Also in S.
- T2 writes last for both the x and y in S’. Also in S.
- R(y) operation in T1 appears after W(y) on T2 in S’. By rule 2 it must be preserved in S. It is in fact preserved in S.
- Since there is no other Write to Read conflict, then S is view equivalent to S’.
Now if we check the other direction, if S is view equivalent to S’:
- For conditions 1 and 3 are the same, they are satisfied.
- Write to read conflict in the previous case also present here. But also there is another write to read conflict on x because in S T2 operates before T1. But in S’ read on x appears before T2. So the order is different between S and S’. Therefore S is not view equivalent to S’.
If what I am doing is correct, then view equivalence is not bidirectional. But I am not sure if I did no mistakes. Does my example correctly shows that property?