Information Technology Reference
In-Depth Information
released and x is unconditionally S-locked, and the search for the correct key is
restarted when the lock is granted.
6. Neither .x; T
00
;
v
00
/ nor .x; T
0
;
v
0
/ exists. If T holds a lock on the key
1
, then the
tuple .
1
;0/is returned. Otherwise, all latches are released,
1
is unconditionally
S-locked, and the search for the correct key is restarted when the lock is granted.
If the current version of the tuple with key x is deleted (cases 3 and 5), we unlatch
the pages in P and move to the key next to x, that is, to the versioned tuples with the
least key greater than x, and repeat the checking for that key, and so on. The move
to the key next to x is performed by the procedure call
find-pages-for-read
.P; > x/.
If no key x is found with a non-deleted tuple, then by our convention, the key
1
is
S-locked and the tuple .
1
;0/is returned (case 6).
In case 5 it is necessary to lock the key x of the currently deleted tuple, because
otherwise some transaction that commits before T can insert a tuple with key x.
This is possible because the pages in P are unlatched before moving to the key next
to x. It is necessary to unlatch the pages before the call
find-pages-for-read
.P; > x/,
because we must never latch an ancestor of a latched page.
In executing a delete action DŒx;
v
in an update transaction T ,wefirst
unconditionally X-lock key x for commit duration and then use the procedure call
find-pages-for-delete
.P;x;T/ to access and write-latch the set P of leaf pages
that contain the versioned tuples with key x. The call also ensures, by appropriate
structure modifications, that the leaf page that covers the key .x; T / has room for the
versioned tuple .x; T;
?
/. The commit-time table is read-latched, the set of records
for the transactions that created the versioned tuples with key x is retrieved from
the commit-time table, and the table is unlatched. Among the committed versioned
tuples with key x, if such tuples exist, let .x; T
0
;
v
0
/ be the one with the greatest
commit time, and let .x; T;
v
00
/ be the one created by T itself, if one exists. Note
that because of commit-duration X-locking, there cannot exist any tuple .x; T
00
;
v
00
/
where T
00
6D
T is an active transaction.
We have the following cases:
1. .x; T;
v
00
/ with
v
00
6D?
exists. Then the last update on key x is an insert or a
write action by T itself. The tuple .x; T;
v
00
/ is replaced by the tuple .x; T;
?
/,
the replacement is redo-undo logged, and the tuple .x;
v
00
/ is returned.
2. .x; T;
v
00
/ with
v
00
D?
exists. Then T is logically inconsistent and must be
aborted.
3. .x; T;
v
00
/ does not exist but .x; T
0
;
v
0
/ with
v
0
6D?
exists. Then the last update
on key x is an insert or a write action by committed transaction T
0
. The tuple
.x; T;
?
/ is inserted, the insertion is redo-undo logged, and the tuple .x;
v
0
/ is
returned.
4. .x; T;
v
00
/ does not exist but .x; T
0
;
v
0
/ with
v
0
D?
exists. Then the delete action
is illegal in this context and T must be aborted.
5. Neither .x; T;
v
00
/ nor .x; T
0
;
v
0
/ exists. Then the delete action is illegal in this
context and T must be aborted.
