02-02-2012, 03:59 PM
CS411 Database Systems
[attachment=17098]
Timestamps
• Scheduler assigns each transaction T a timestamp
of its starting time TS(T)
• Each database element X is associated with
– RT(X): the highest timestamp of a transaction that has
read X
– WT(X): the highest timestamp of a transaction that
has written X
– c(X): the commit bit of X, which is true iff the most
recent transaction to write X has already committed
Scheduler’s response to a T’s request
1. Grant the request
2. Abort and restart (roll back) T with a new
timestamp
3. Delay T and later decide whether to abort T or
to grant the request
Multiversion Timestamping Scheduler
• When wT(X) occurs, if it’s legal, a new version of X,
Xt where t = TS(T), is created.
• When rT(X) occurs, find the version Xt of X s.t.
t <= TS(T), but no Xt’ with t < t’ <= TS(T)
• Write times are associated with versions of an element,
and they never change
• Read times are also associated with versions
• When Xt has a write time t s.t. no active transaction has a
timestamp less than t, we can delete any version of X
previous to Xt
Concurrency Control by Validation
• Another type of optimistic concurrency control
• Maintains a record of what active transactions are
doing
• Just before a transaction starts to write, it goes
through a “validation phase”
• If a there is a risk of physically unrealizable
behavior, the transaction is rolled back
[attachment=17098]
Timestamps
• Scheduler assigns each transaction T a timestamp
of its starting time TS(T)
• Each database element X is associated with
– RT(X): the highest timestamp of a transaction that has
read X
– WT(X): the highest timestamp of a transaction that
has written X
– c(X): the commit bit of X, which is true iff the most
recent transaction to write X has already committed
Scheduler’s response to a T’s request
1. Grant the request
2. Abort and restart (roll back) T with a new
timestamp
3. Delay T and later decide whether to abort T or
to grant the request
Multiversion Timestamping Scheduler
• When wT(X) occurs, if it’s legal, a new version of X,
Xt where t = TS(T), is created.
• When rT(X) occurs, find the version Xt of X s.t.
t <= TS(T), but no Xt’ with t < t’ <= TS(T)
• Write times are associated with versions of an element,
and they never change
• Read times are also associated with versions
• When Xt has a write time t s.t. no active transaction has a
timestamp less than t, we can delete any version of X
previous to Xt
Concurrency Control by Validation
• Another type of optimistic concurrency control
• Maintains a record of what active transactions are
doing
• Just before a transaction starts to write, it goes
through a “validation phase”
• If a there is a risk of physically unrealizable
behavior, the transaction is rolled back