[go: up one dir, main page]
Scribd
Upload
5 views11 pages

Dbms 2

Uploaded by

Akul Natekar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
5 views11 pages

Dbms 2

Uploaded by

Akul Natekar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 11

CONCURRENCY CONTROL BASED

ON TIMESTAMP ORDERING
TIMESTAMP

• Timestamp is a unique identifier created by the DBMS to identify a


transaction.
• Timestamp values are assigned in the order in which the transactions
are submitted to the system.
• Concurrency control techniques based on timestamp ordering do not
use locks, hence, deadlocks cannot occur.
• A timestamp can be thought of as the transaction start time. We will
refer to the timestamp of transaction T as TS(T).
TIMESTAMP-BASED CONCURRENCY CONTROL

• Timestamp-based concurrency control is a method used in


database systems to ensure that transactions are executed safely
and consistently without conflicts, even when multiple transactions
are being processed simultaneously.
• This approach relies on timestamps to manage and coordinate the
execution order of transactions.
The Timestamp Ordering Algorithm for Concurrency Control

• The idea for this scheme is to enforce the equivalent serial order on
the transactions based on their timestamps.
• A schedule in which the transactions participate is then serializable,
and the only equivalent serial schedule permitted has the
transactions in order of their timestamp values.
This is called timestamp ordering (TO).
• The timestamp ordering algorithm works by assigning a unique
timestamp to each transaction when it arrives in the system. The
timestamp reflects the transaction's start time, and it is used to order
the transactions for execution.
The algorithm associates with each database item X two timestamp
(TS) values:

1. read_TS(X). The read timestamp of item X is the largest timestamp


among all the timestamps of transactions that have successfully read
item X—that is, read_TS(X) = TS(T), where T is the youngest transaction
that has read X successfully.

2. write_TS(X). The write timestamp of item X is the largest of all the


time stamps of transactions that have successfully written item X—
that is, write_TS(X) = TS(T), where T is the youngest transaction that
has written X successfully. Based on the algorithm, T will also be the
last transaction to write item X.
a) Basic Timestamp Ordering (TO)

Whenever some transaction T tries to issue a read_item(X) or a


write_item(X) operation, the basic TO algorithm compares the
timestamp of T with read_TS(X) and write_TS(X) to ensure that the
timestamp order of transaction execution is not violated. If this order is
violated, then transaction T is aborted and resubmitted to the system
as a new transaction with a new time stamp.
• Whenever a transaction T issues a write_item(X) operation, the
following check is performed:

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 should be done because some
younger transaction with a timestamp greater than TS(T)—and
hence after T in the timestamp ordering—has already 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 part (a) does not occur, then execute the write_item(X)
operation of T and set write_TS(X) to TS(T).
• Whenever a transaction T issues a read_item(X) operation, the
following check is performed:

a. If write_TS(X) > TS(T), then abort and roll back T and reject the
operation. T his should be done because some younger transaction
with 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 of TS(T) and the current read_TS(X).
• Strict Timestamp Ordering (TO).

A variation of basic TO called strict TO ensures that the schedules are


both strict (for easy recoverability) and (conflict) serializable. In this
variation, a transaction T issues a read_item(X) or write_item(X) such
that TS(T) > write_TS(X) has its read or write operation delayed until
the transaction T′ that wrote the value of X (hence TS(T′) = write_TS(X))
has committed or aborted.
Thomas’s Write Rule

A modification of the basic TO algorithm, known as Thomas’s write


rule, does not enforce conflict serializability, but it rejects fewer write
operations by modifying the checks for the write_item(X) operation as
follows:

 If read_TS(X) > TS(T), then abort and roll back T and reject
the operation.
 If write_TS(X) > TS(T), then do not execute the write
operation but continue processing.
 If neither the condition in part (1) nor the condition in part (2) occurs,
then execute the write_item(X) operation of T and set write_TS(X) to
TS(T).
THANK YOU

You might also like