Information Technology Reference
In-Depth Information
2.
Read-next actions
of the form
RŒx; >
z
;
v
(1.9)
for reading the tuple .x;
v
/ with the key value x next to
z
.Thekey
z
,
1
z
<
1
, is an input parameter, and the key x and the value
v
are output parameters.
The action fetches the tuple .x;
v
/ whose key is the least key satisfying x>
z
and .x;
v
/
2
r . If no such tuple exists, .
1
;0/ is returned. Shorthand notations
for this action are RŒx; >
z
, RŒx;
v
,orRŒx.
3.
Insert actions
of the form
IŒx;
v
(1.10)
for inserting the tuple .x;
v
/ into r . Input parameters are the key x and the value
v
.
The action inserts the tuple .x;
v
/ into relation r .Ifr already contains a tuple with
key x, the action fails. A shorthand notation is IŒx.
4.
Delete actions
of the form
DŒx;
v
(1.11)
for deleting the tuple .x;
v
/ with key x from r .Thekeyx is an input parameter,
and the value
v
is an output parameter. The action deletes the tuple .x;
v
/ with
key x from relation r . If the tuple is not found, the action fails. A shorthand
notation is DŒx.
For an insert or delete action oŒx,wedefinethe
undo action
o
1
Œx or
undo-o
Œx
as follows:
5. The
undo-insert action
I
1
Œx;
v
D
undo-I
Œx;
v
(1.12)
undoes the action IŒx;
v
by deleting the tuple .x;
v
/ from r .
6. The
undo-delete action
D
1
Œx;
v
D
undo-D
Œx;
v
(1.13)
undoes the action DŒx;
v
by inserting the tuple .x;
v
/ into r .
Example 1.7
The forward-rolling transaction
BR
Œx
1
;
x
0
;
v
1
RŒx
2
;>x
1
;
v
2
RŒx
3
;>x
2
;
v
3
DŒx;
v
I Œx;
v
1
C
v
2
C
v
3
reads three tuples with consecutive keys and replaces the value in the tuple with
key x by the sum of the values in the three tuples. This transaction is rolled back
by first performing the abort action A and then undoing the two updates and finally
completing the rollback: