I was going through the concept of order preservation in Conflict Serializable class and I came across Order preserving conflict serializable (OCSR in short). The following is the definition of OCSR that I found:

History h is order preserving conflict serializable if h is conflict equivalent to a serial history hs where t,t'∈h:if t occurs completely before t' in h then the same holds in hs.

Following is one example of a schedule that is in OCSR:

w3(y) c3 w1(x)r2(x) c2 w1(y) c1

But I could not get why this schedule is in OCSR. Because as per my understanding this is the conflict graph t3 --- > t1 ---- > t2

which is showing a serial schedule where t1 comes before t2. But in the original interleaved schedule t2 completely comes before t1. Then how is the given example said to be in OCSR? Can anyone please help me understand this better?

  • Seems like nobody likes to answer that question and all the slide over the internet and even books ignore the fact to explain!! – MD. Jahidul Islam Nov 18 '19 at 11:36

In the schedule, T3 occurs completely before T1 and T2, but T2 and T1 are interleaved (so there is no "one occurs completely before the other" relationship between them). So, it can be in OCSR as long as there exists a serial history that T3 occurs completely before T1 and T2.

Actually there is a serial history T3->T1->T2 that meets the above condition. Then, it is in OCSR.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.