The meaning of Order preserving Conflict Serializable schedules

serialization

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?

Best Answer

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.

Related Solutions

Timestamp Protocol – Does Thomas’s Write Rule Allow Non-View-Serializable Schedules?

The given schedule S is:

T1    T2
----  -----
R(X)
      W(X)
W(X)

To be view serializable W2(X) must move before R1(X) or after W1(X). However, the first would violate the "initial read" rule and the second would violate the "last write" rule.

T2 starts after T1 so has a higher timestamp. When T1 comes to write X it sees that T2's timestamp on it. By Thomas' write rule the write by T1 is void and can be removed. The given schedule then becomes

T1    T2
----  -----
R(X)
      W(X)

Now all of T2's actions occur after all of T1's - the schedule is serialized.

(You have this the other way around in your question, removing W2(X). I think that is an error.)

To show that a schedule is serializable it is only necessary to show that there is at least one equivalent schedule that is serial. It is not necessary to show that every possible serial schedule is achievable. I agree that T2,T1 is not view serializable on the original schedule because of the read/ write dependency. However, T1,T2 is serializable under the Thomas write rule.

Postgresql – SELECT FOR UPDATE (NOWAIT) on auxilliary table for serializing updates

You could use transaction level advisory locks to serialize your operations:

BEGIN;
-- take an advisory lock for the duration of the session
SELECT pg_advisory_xact_lock(4711);
SELECT * FROM inventory_use;
INSERT INTO inventory_use (ref) VALUES ('T1 insert');
COMMIT;

The number 4711 is an arbitrary constant.

Then the second transaction using the same code will block until the first one has committed.