Thomas write rule

Thomas write rule modify or improves the Basic Timestamp Ordering Algorithm (BTSO Algorithm).

According to Basic Timestamp Ordering Algorithm (BTSO Algorithm) :
  1. When Transaction Ti issues READ Operation :
    1. If TS(Ti) < WTS(Q), then
      • ROLLBACK Ti.
      • RESTART Ti
    2. Otherwise,
      • allowed to execute READ operation by transaction Ti and
      • Set RTS(Q) = max(RTS(Q), TS(Ti))
  2. When Transaction Ti issues WRITE Operation :
    1. If TS(Ti) < RTS(Q), then
      • ROLLBACK Ti.
      • RESTART Ti.
    2. If TS(Ti) < WTS(Q), then
      • ROLLBACK Ti.
      • RESTART Ti.
    3. Otherwise,
      • Allowed to execute the WRITE operation by transaction Ti and
      • Set WTS(Q) = TS(Ti)

Criteria For Modification :

Before improving the BTSO protocol, it must follow some criteria :

  • The First Criteria used to maintain the consistency of the system.
  • After maintaining the consistency of the system, the next criteria is to trying to see whether we can enhance the concurrency of the mechanism.

Modification in BTSO Protocol

Let us discuss the cases one by one :

  1. When Ti issues a READ (R(Q)) :
    1. Case (a) : If TS(Ti) < WTS(Q) ?
      Thomas write rule 2

      • Transaction Ti must have rolled back as transaction Ti is trying to read a data item Q which is written by transaction Tj which started after Ti.
      • If we allow this, then we have thousands of examples, in which this case will lead to problem ( As we are not analyzing what the code exactly is. The code may or may not have the problem.)
      • So no modification can be done in this case.
    2.  Case (b) : If TS(Ti) >= WTS(Q) ?
      • The read is allowed in the otherwise case.
      • So no need of modification.
  2. When Ti issues a WRITE (W(Q)) :
    1. Case (a) : If TS(Ti) < RTS(Q) ?
      Thomas write rule 3

      • In this case also transaction Ti must have rolled back as transaction Ti is trying to write data item Q which is already read by a transaction Tj.
      • If we allow this, then the schedule will not be conflict serializable at all.
    2. Case (B) : TS(Ti) < WTS(Q)
      • This case can be improved as :
        Thomas write rule 4
      • In this case Tj writes a data item Q which is again updated by Ti and Tj starts after Ti.
      • We cannot allow the WRITE (W1(Q)) statement because it will never be conflict serializable.
      • But the question is do we have to rollback Ti?
      • In BTSO protocol we do not allow to execute the write statement and rolled back Ti.
      • The modification is done as : We do not allow to execute the write statement by Ti but we do not rollback Ti. We just continue to execute with Ti.
      • This is because any updates made by transaction Tj ( timestamp greater than Ti) has already written the value of Q and any updates made by Tj will be lost.
      • Therefore we must ignore the write operation of Ti because it is already outdated and obsolete.
      • This way, it prevents a rollback in this situation as late as possible and therefore tries to reduce the amount of rollback.
      • Thomas write rule 5
    3. Case (c) : The otherwise case
      {TS(Ti) > RTS(Q) and TS(Ti) > WTS(Q)}

      • The write is allowed in the otherwise case. So no need of modification.

Thomas’s Write Rule Timestamp Ordering (TWRTSO)

Modification in case (B) when transaction Ti issues a write operation is called Thomas write rule. It rejects fewer write operations, by modifying the checks for write operation.

Thomas’s Write Rule Timestamp Ordering Protocol (TWRTSO Protocol)

  1. When Transaction Ti issues READ Operation :
    1. If TS(Ti) < WTS(Q), then
      • ROLLBACK Ti.
        Thomas write rule 6.1
    2. Otherwise,
      • allowed to execute READ operation by transaction Ti and
      • Set RTS(Q) = max(RTS(Q), TS(Ti))
  2. When Transaction Ti issues WRITE Operation :
    1. If TS(Ti) < RTS(Q), then
      • ROLLBACK Ti.
        Thomas write rule 6.2
    2. If TS(Ti) < WTS(Q), then
      • Ignore WRITE operation by Ti and
      • Continue the execution of Ti.
        Thomas write rule 6.3
    3. Otherwise,
      • Allowed to execute the WRITE operation by transaction Ti and
      • Set WTS(Q) = TS(Ti)
Thomas Write Rule Timestamp Ordering  is :
  • Deadlock Free
  • Ensures Serializability (equivalent serial schedule based of the order of TS value)
Problems in Thomas Write Rule Timestamp Ordering
  • Starvation may be possible.
  • Irrecoverability Possible.
    Thomas write rule 7

Strict TSO Protocol : To Avoid Irrecoverability

Concurrent schedule should be equivalent to serial schedule based on TS ordering and
If transaction Ti updates data item Q, other transaction Tj is not allowed to read or write on data item Q (R(Q)/W(Q)) until commit(C) or rollback(R) of Ti.

Thomas write rule 8

Strict Timestamp Ordering Schedule is :
  • Strict Recoverable
  • Deadlock Free
  • Starvation still Possible

Combining :

Basic Timestamp Ordering + Strict TSO Protocol
or
Thomas Write Rule Timestamp Ordering + Strict TSO Protocol

Thomas write rule 9

View/Conflict Serializability and Timestamp Ordering :

Consider the following Scenario :

Thomas write rule 10

If schedule is view serializable schedule and view equivalent serial schedule is based on timestamp value, then Thomas Write Rule Timestamp Ordering Protocol allow to execute the schedule.

Thomas write rule 11

Relation between Thomas Write Rule Timestamp Ordering, Basic Timestamp Ordering, and Strict TSO Protocol :

Thomas write rule 12


Previous Home Next
Questions on Timestamp Ordering Deadlock in Transaction

     

Incoming search terms:

  • thomas write rule
  • thomas write rule in dbms
  • thomas rule in dbms
  • thomas write rule in rdbms
  • dbms thomas write
  • does thomas write rule eliminate cascade rollback??
  • state and explain thomas write rule

Leave a Reply