1
$\begingroup$

Yesterday our Professor told in the class that Thomas Write rule ensures view serializability, but while surfing on this topic today on internet I am not able to find any information about that claim. So is it always $TRUE?$

What he told was this-->

Timestamp ordering ensures conflict serializability

Thomas write rule ensures view serializability

$\endgroup$
4
  • $\begingroup$ Did you just try asking your professor? $\endgroup$
    – Juho
    Jan 4 '20 at 8:32
  • $\begingroup$ What to ask when he has already mentioned that in class... But i am not able to find a single line about it on the web $\endgroup$
    – Turing101
    Jan 4 '20 at 13:32
  • $\begingroup$ For instance, couldn't you say "You said that X. Is it really always true? Why?". Anyway, I hope your question attracts attention here. $\endgroup$
    – Juho
    Jan 4 '20 at 13:58
  • $\begingroup$ Will do when college resumes on monday..Thanks anyway.. :) $\endgroup$
    – Turing101
    Jan 4 '20 at 14:07
1
$\begingroup$

Timestamp ordering ensures conflict serializability

proof :

Assume that in precedence graph of schedule, we have edge $T_i \rightarrow T_j$.

Now, When $T_j$ puts it's request for this conflicting operation it will be continue only if $\text{timestamp}(T_i) < \text{timestamp}(T_j)$.

Now, for schedule to be non conflict serializable there must exist a cycle in precedence graph of that schedule and let say that cycle is $T_i, T_{i+1}, ...., T_i$.

Now, note that that cycle can't exist because existence of cycle implies $\text{timestamp}(T_i) < \text{timestamp}(T_i)$. (As timestamp are unique.)

So, we conclude that there can't be any such cycle which in turn implies that timestamp ordering protocol allows only conflict serializable schedules.

$\endgroup$
5
  • $\begingroup$ Ya..this I know brother but i want to confirm the claim about view serailizibility $\endgroup$
    – Turing101
    Jan 5 '20 at 13:47
  • $\begingroup$ Yes, working on that will post if succeed. :) $\endgroup$ Jan 5 '20 at 13:49
  • $\begingroup$ Thanks a lot.. :) $\endgroup$
    – Turing101
    Jan 5 '20 at 13:57
  • $\begingroup$ @Turing101, here is a proof of second one $\endgroup$ Jan 5 '20 at 14:34
  • $\begingroup$ Thanks a ton mate.. :) $\endgroup$
    – Turing101
    Jan 5 '20 at 18:00

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.