Information Technology Reference
In-Depth Information
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
AI
1
Œx;
v
1
C
v
2
C
v
3
D
1
Œx;
v
C .
The original value
v
of the tuple with key x is thus restored.
t
Let r be the logical database (a relation) and oŒ
N
x an action, o
2
f
B; R; W; I; D; C; A
g
and
N
x a sequence of constant arguments. We define when
the action oŒ
N
x
can be run
on r and what is the database (relation) r
0
produced
by
the action—this is denoted .r; r
0
/
ˆ
oŒ
N
x.
1. .r; r/
ˆ
o,wheno
2f
B; C; A
g
.
2. .r; r/
ˆ
RŒx;
z
;
v
,if.x;
v
/
2
r and x is the least key in r that satisfies x
z
.
Here is the operator
or >.
3. .r; r/
ˆ
RŒ
1
;
z
;0,ifr contains no tuple with key x satisfying x
z
.
4. .r; r
0
/
ˆ
WŒx;
u
;
v
,ifr
0
D
.r
nf
.x;
u
/
g
/
[f
.x;
v
/
g
.
5. .r; r
0
/
ˆ
IŒx;
v
,ifthekeyx does not appear in r and r
0
D
r
[f
.x;
v
/
g
.
6. .r; r
0
/
ˆ
DŒx;
v
,if.x;
v
/
2
r and r
0
D
r
nf
.x;
v
/
g
.
7. .r; r
0
/
ˆ
W
1
Œx;
u
;
v
,if.r
0
;r/
ˆ
WŒx;
u
;
v
.
8. .r; r
0
/
ˆ
I
1
Œx;
v
,if.r
0
;r/
ˆ
IŒx;
v
.
9. .r; r
0
/
ˆ
D
1
Œx;
v
,if.r
0
;r/
ˆ
DŒx;
v
.
To simulate an
exact-match read action
, we may write RŒx;
x;
v
.By(2),
.r; r/
ˆ
RŒx;
x;
v
,if.x;
v
/
2
r .
The action sequence ˛
can be run
on database r and
produces
the database r
0
,
denoted .r; r
0
/
ˆ
˛, if either (1) ˛
D
and r
0
D
r or (2) ˛ is of the form LJo,where
the action sequence LJ can be run on r and produces a database r
00
and action o can
be run on r
00
and produces r
0
.
Example 1.8
The transaction of Example
1.7
can be run on every database that
contains the tuples .x
1
;
v
1
/, .x
2
;
v
2
/, .x
3
;
v
3
/,and.x;
v
/ with x
0
x
1
<x
2
<
x
3
but no other tuples with keys in the range Œx
0
;x
3
. The forward-rolling portion
of the transaction produces a database where the tuple .x;
v
/ has been changed to
.x;
v
1
C
v
2
C
v
3
/ and the entire rolled back transaction restores the original database.
t
Example 1.9
The transactions of Example
1.4
can be modeled in the key-range
model as follows:
T
1
D
BR
Œx
1
;>
1
;
v
1
RŒx
2
;>x
1
;
v
2
:::RŒx
n
;>x
n1
;
v
n
RŒ
1
;>x
n
;0C,
T
2
D
BI Œx;
u
I Œy;
v
C ,
where
f
.x
1
;
v
1
/;:::;.x
n
;
v
n
/
g
is the set of tuples in the relation r.X;V/ and x and
y are keys not found in r . The phantom phenomenon occurs if
x
i
<x<x
iC1
<y
D
x
j
for some i and j , and the actions are executed in the following order (from left to
right):
T
1
W
BR
Œx
1
;
v
1
:::RŒx
j1
;
v
j1
RŒx
j
;
v
j
:::RŒ
1
;0C
T
2
W
BI Œx;
u
I Œy;
v
C
