+1 vote
550 views
I)All schedules that are allowed under 2PL are also allowed under Timestamp?? Is vice versa true??

II)Plz explain by giving example. I have read that there are schedules that are allowed under 2PL but not under Timestamp and vice versa, but need example. For schdeules allowed under timestamp but not under 2PL is understable bcoz of view serializable nature of timestamp, but how a 2PL schedule not allowed under testamp??

III) Are there conflict serializable schedules that are not allowed under 2PL?? are there any conflict serializable schedule that are not allowed in Timestamp???

IV) Are all view serializable allowed under Timestamp(Thomas write rule)???

Explanation along with example would be helpful.
retagged | 550 views

+1 vote

1. There  are some schedules which are possible under basic timestamp but not under 2PL and vice-versa.

2. Lets take an example tp prove the first statement.

Let, TS(T1) = 20   and TS(T2) = 30

Let, the schedule be:

 T1 T2 W(A) R(A)

Now, lets see if this possible under basic timestmp protocol.

W(A) of T2 updates the Write-TS(A) = 30 initially.

Then, T1 requests R(A).

Now, TS(T1) < Write-TS(A)   and hence, T1 read operation is rejected and T1 is rolled back.

But, this schedule is easily possible under 2PL.

Now, the schedule possible under basic timestamp but not under 2PL: TS(T1) = 20, TS(T2) = 30

 T1 T2 W(A) R(A) R(B)

3. One ssuch schedule which is conflict serializable but not possible with 2PL is:

 T1 T2 W(A) R(A) R(A)

4.

2PL scheules $\subseteq$ conflict serializable schedules $\subseteq$ view serializable schedules

Some timestamp schedules that use Thomas' write rule are view serializable but not conflict serializable.

REF: here

edited
0
Any standard reference for the last diagram ?
0
Yes, Korth.

Just they have this in words and not using diagram.
0

But, I can give an example which is allowed in the timestamp protocol but violates 2PL .

On the other hand, your diagram says that All TP are 2PL

+1

@kapil. My mistake.

From Korth:

There are schedules possible under 2PL but not under timestamp and vice-versa.

I will edit the same.

Btw, could you give the schedule possible under timestamp but not using 2PL for reference?

+2
Got the schedule possible under timestamp but not under 2PL. Posted the same.
0
@sushant lots of thanks. You solved so many doubts.☺
0
But I think sushant Thomas write rule allows some scedules that are not conflict serializable but are view serializable.
0
not conflict but view serializable isnt possible :)
0
In thomas write rule W-W conflict is not rollbacked bcoz of these some view serializable schedules are allowed even though they are not conflict serializable.
0
ANy example? I doubt this.

Thomas' write rule makes use of concept used in view serializability(no WAW dependenhcy) but I doubt if it says that it produces view serializable schedules.
+1

@Rahul.

You are right. It allows some view serializable schedules which arent conflict serializable

REF: here

Editing the last point :P This was new to me.

+1

http://www.edugrabs.com/thomas-write-rule/ It has a good venn diagram at end.

+1 vote
1
+1 vote
2