Information Technology Reference
In-Depth Information
of committed transactions to commit timestamps. Such a table would not be needed
if the versioned tuples created by a transaction were stamped with the start time of
the transaction. But then we have to force the transactions to commit in their start-
time order. Explain why. Also explain how such a commit order can be enforced.
12.4
Design an efficient method for maintaining the write sets needed in enforcing
the disjoint-write property of transactions. Observe that unlike locks, which only
exist while the owner transaction is active, write sets need be stored for committed
transactions. When can the write set of a committed transaction be purged?
12.5
Give an algorithm for the procedure
find-pages-for-read
.P;
z
/ discussed in
Sect.
12.7
.
12.6
Give an algorithm for the procedure
find-pages-for-insert
.P;x;T;
v
;y/ dis-
cussed in Sect.
12.8
.
12.7
The logic of the procedures
find-pages-for-read
.P;
z
/,
find-pages-for-
insert
.P;x;T;
v
;y/,and
find-pages-for-delete
.P;x;T/can obviously be simplified,
and the number of page latchings reduced, by linking the leaf pages of the
versioned B-tree from left to right, so that each leaf page p contains the record
.
high-key
.p/; p
0
/,wherep
0
is the page-id of the leaf page next to page p (if p is
not the last leaf page) or the null page-id (otherwise). Work out this simplification.
12.8
Analyze the complexity of insert, delete, and write actions IŒx;
v
, DŒx;
v
,
and WŒx;
u
;
v
on a versioned B-tree.
12.9
Explain how the actions in the history
T
1
:
BI
Œ2;
w
1
RŒ2; > 1;
w
1
RŒ3; > 2;
w
2
C
T
2
:
BI
Œ3;
w
2
C
of Example
12.3
are executed on a versioned B-tree using the algorithms outlined
in Sect.
12.8
. What locks are acquired?
12.10
Explain how a write action WŒx;
u
;
v
is executed in a transaction running at
transaction-level read consistency on a versioned B-tree. Explain how the actions in
the history
T
1
:
BR
Œx;
x;
u
0
RŒy;
y;
v
0
RŒy;
y;
v
0
C
T
2
:
BW
Œx;
u
0
;
u
2
W Œy;
v
0
;
v
2
C
of Example
12.3
are executed. What locks are acquired?
12.11
The commit-time table may become a bottleneck because in order to access
the correct versioned tuple in read and update actions, the commit-time table must
be consulted for the mapping from transaction identifiers to the commit timestamps
of the transactions. Also, the insertion of the commit-time tuple into the table
within the transaction, when the transaction is committing, means an overhead.
Performance can be enhanced (1) by allowing a transaction to commit without
updating the commit-time table, by just logging the commit timestamp and updating
the commit-time table later, and (2) by substituting the commit timestamps for the
