Wednesday, January 9, 2008

Concurrency Control Based On Timestamp Ordering

Time Stamps

A time is a unique identifier created by the DBMS to identify a transaction. Typically,timestamp values are assigned in the order in which the trasactions are submitted to the system, so a timestamp can be thought of as the trasaction start time. We will refer to the time stamp of tranaction T as TSCT.

Time Stamp Ordering Algorithm

The idea for this scheme is to order the tranactions based on their timestamps.A schedule in which tranaction participate in the serial table, and the equivalent serial schedule has the transaction of their timestamp values.This is called timestamp ordering(TO) . In timestamp ordering equivalent To the particular serial order corresponding to the order of the transactionthe schedule is on time stamps. The Algorithm must ensure that for each item accessed by competing operations in the schedule, the order in which theitem isaccessed does not violate the serializability order. To do this, the algorithm associates with each dataBase item X two timestamp (TS) VALUES:

1. Read –TS (X) : The read timestamp of item X; this is the largest time stamp among all the timestamps of transactions that have successfully read item – X i.e. Read – TS (X) = TS (T). Where T is the youngest transaction tht has read X successfylly.

2. Write – TS (X) : The write timestamp of item X; this is the largest of all the timestamps of transactions that have successfylly written item X – i.e., write –TS (X) = TS(T), where T is the youngest transaction that has written X successfully.

Basic Time Stamp Ordering

Wherever some transaction T tries to issue a read- item (X) or write-item (X) operation, the basic TO (Time Ordering) compares the timestamp of T with read – TS (X) and write – TS (X) to ensure that the timestamp order of transactionis not violate.If this order is violated,then transactionT is aborted resubitted to the system as a new transaction with a new timestamp.If T is aborted and rolled back , any transaction T1 that may have used a value written by T must also be rolled back similarly, any transactionT2that may have used a value written by T1 must also be rolled back, and so on. This effect is known as cascading rollback and is one of the problems associated with basic TO, since the schedules produced are not recoverable, codeless or stick. We visit desirable the basic to algotithm here. The concurrency control algorithm must check whether convicting operations violate the time stamp ordering in the following two cases.

1. Transaction T issues a write –item (X) operation

(a) If read –TS (X) > TS (T) or if write – TS (X) > TS (T), then abort and roll back T and reject the

Operation. This shoud be done because some younger transaction with a time stamp greater than TS (T) – and hence after T in the timestamp ordering –has alredy read or written the value of item X before T had a chance to write X, thus violating the timestamp ordering.

(b) If the condition in (a) does not occure then execute the write-item (X) operation on T and set write –

Item (X) operation on T and set write- TS(X) to TS (T).

2. Transaction T issues a read- item (X) operation

(a) If write- TS (X) >TS (T), then abort and roll back Tand reject the operation. This shoud be done

Because some younger transaction have timestamp greater than TS (T) – and hence after T in the

Timestamp ordering-has already written the value of item X before T had a chance to read X.

(b) If write TS (X) < = TS (T), then execute the read item (X) operation of T and set read TS (X) to the

Larger to TS (T) and the current read –TS (X).

Hence, whenever the basic to algorithm detects two conflicting operations that occur in the incorrect rejects the latter of the two operations by aborting the transaction that issued it.

Strict Time Stamp Ordering

A varation of basic TO called Strict TO ensures that the schedules are both strict and serial tables. In this variation, a transaction T that issues a read-item (X) or wrote-item (X) such that TS (T) = write TS (X) has its read or write operation delayed until the transaction T1 that wrote the value of X

(hence TS (T1) =write-TS (X) has committed or aborted. T o implement this algorithm, it is necessary to simulate the locking of an item X that has been written by transaction T1 until T1 is either committed or aborted. This algorithm does not cause deadlock, since T waits for T1 only if TS (T) > TS (T1).

No comments: