95 views

I was reading multiversion timestamp ordering protocol from the book Database Systems Concepts by Korth. It can be explained in simpler words as follows:

Each data item version $Q$ has two timestamps associated with it:

• W-timestamp: the timestamp of the transaction that created version
• R-timestamp: the largest timestamp of any transaction that successfully read version

Let $Q_k$ denote the version of $Q$ whose write timestamp is the largest write timestamp less than or equal to $TS(Ti)$.

1. If transaction $T_i$ issues a $read(Q)$, then the value returned is the content of version $Q_k$, thus reading the most recent version that comes before $T_i$.
2. If transaction $T_i$ issues $write(Q)$, and
• if $TS(T_i) < R-timestamp(Q_k)$, then the system rolls back transaction $T_i$.
• if $TS(T_i) = W-timestamp(Q_k)$, the system overwrites the contents of $Q_k$;
• if $TS(T_i) > R-timestamp(Q_k)$, it creates a new version of $Q$.

My doubts

1. What happens when TS(Ti) < W-timestamp(Qk) and when TS(Ti) > W-timestamp(Qk)?
2. The set of schedules possible under multiversion timestamp ordering protocol forms superset of set of schedules possible under Thomas write rule. I know that Thomas write rule allows non conflict serializable schedules. So same must be true for multiversion protocol. Right?
3. Also I know that Thomas write rule allows view serializable schedules. Does the schedules produced by multiversion protocol are also view serializable?

Though above  questions seems valid and important to me, I had following doubts: is it worth to give so much importance to this topic fo GATE perspective? Also it seems that Elmasri Navathe's book gives somewhat different definition for the multiversion timestamp ordering protocol. Also it seems that this topic was never being asked in previous year GATE papers. (Or I am wrong and it was indeed asked in previous year GATE paper?) Can we safely skip it?

0

Doubt 1 part 1 : What happens when TS(Ti) < W-timestamp(Qk)

Let Qk denote the version of Q whose write timestamp is the largest write timestamp less than or equal to TS(Ti).

So according to this condition, the situation "TS(Ti) < W-timestamp(Qk) " can't occur ever because it is already said that the W-timestamp(Qk)<=TS(Ti).

At the very beginning we maintain a version Q0 of dB and initialize the read and write TS with 0.

So any transaction Ti will have a version of Q whose W-timestamp(Qk) is lesser than TS(Ti) i.e. W-timestamp(Q0) < TS(Ti)  =>   0<TS(Ti)

Doubt 1 part 2: What happens when TS(Ti) > W-timestamp(Qk)

Let Qk denote the version of Q whose write timestamp is the largest write timestamp less than or equal to TS(Ti) i.e. W-timestamp(Qk)<=TS(Ti)

The primary condition is this only. Whenever we confront any operation this is the condition that we always check.

Doubt 2 : Multiversion protocol allows schedules which may not be conflict or even view serializable. So Yes you are right that this protocol allows some non conflict serializable schedules too.

Doubt 3: Multiversion allows more than view serializable schedules.

I had following doubts: is it worth to give so much importance to this topic fo GATE perspective? Can we safely skip it?

I am a student as well so i shouldn't comment on this :P But yes my teacher told that this is very less important for GATE.