Database Reference
In-Depth Information
•
By convention, each turn-on/turn-off of the
M
UC
determines a corresponding
turn-on/turn-off of the RDB machine
M
RC
.
Let us now introduce the operator of concurrent (“parallel”, that is, time-shared)
composition of application programs
P
P(
2
)
∗
(where
P(
2
)
∗
is obtained from
P(
2
)
by incrementing each address in its instructions
by the integer
N
+
=
P(
1
)
|
P(
2
)
such that
P
=
P(
1
)
∪
1, where
N
is the biggest address in
P(
1
)
), in the time-shared
mode of the concurrent multiple-user universal machine
M
UC
, by the following
definition:
Definition 45
A
concurrent execution of a program P
=
P(
1
)
|···|
P(n)
on a ma-
chine
M
UC
is a computation system
CS
=
(TrS, In
S
, Out
S
, Stop
S
)
, where
TrS
=
(S
PU
,
→
P
)
is a deterministic transition system with:
1. The set of configurations (obtained during the concurrent execution of programs):
S
PU
={
(i, st, ID
T
)
|
i
is the address of some instruction of the program
P(m)
=
Pr(ID
T
),
1
≤
m
≤
n,
executed during the transaction
ID
T
≥
1
, st
∈
S
U
is the
state of
M
UC
before the execution of this
i
th instruction
}
.
→
P
is a function defined for any time-shared window during the execu-
tion of a program
P(m)
in the state
st
2. The
∈
S
U
such that there is a transaction
ID
T
with
Pr(ID
T
)
=
P(m)
(if
P(m) /
∈{
Pr(i)
|
1
≤
i
≤
K
}
,for
K
=
min
{
k
≥
1
|∀
j
≥
k, Pr(j)
, then in this time-window the execution of this program
P(m)
just begins and we set
Pr(K)
=
P
∅
}
=
P(m)
and
ID
T
=
K
), as follows:
2.1.
((i, st, ID
T
),(j,λIn
∗
EU
(z)(st), ID
T
))
∈→
P
if
(i, In
∗
EU
,j)
∈
Pr(ID
T
)
is ex-
ecuted in this time-window, where
z
∈
INP
is the input value taken by
M
UC
in this current state
st
∈
S
U
and
λ
is the abstraction operator (currying) of
λ
-calculus such that
λIn
∗
EU
(z)(st)
I
EU
(z, st)
.
=
∈→
P
,if
(i,f,j)
∈
2.2.
((i, st, ID
T
),(j,f (st), ID
T
))
Pr(ID
T
)
is executed in
this time-window and
f/
.
If there is no instruction with the address
j
(we reached the end of
this program) then
((j,f (st), ID
T
),(j,f (st), ID
T
))
∈{
COMMIT
,
ROLLBACK
}
∈→
P
, and this time-
window is closed by imposing
Pr(ID
T
)
=
P
.
∅
2.3.
(i, st, ID
T
),
j,f(st), ID
T
∈→
P
j,f(st),ID
T
,
k,Out
U
f(st)
,ID
T
∈→
P
,
∈
if
(i,f,j),(j, Out
U
,k)
Pr(ID
T
)
are executed in this time-window and
f
∈{
COMMIT
,
ROLLBACK
}
. Set
Pr(K)
=
Pr(ID
T
)
with
K
=
min
{
k
≥
1
|∀
j
≥
k, Pr(j)
=
P
∅
}
, and after that set
Pr(ID
T
)
=
P
∅
and
ID
T
=
K
.
2.4.
((i, st, ID
T
),(j, st, ID
T
))
∈→
P
,if
(i,t,j,k)
∈
Pr(ID
T
)
is executed in this
time-window and
t(sk)
=
1,
2.5.
((i, st, ID
T
),(k, st, ID
T
))
∈→
P
,if
(i,t,j,k)
∈
Pr(ID
T
)
is executed in this
time-window and
t(sk)
=
0.
3.
In
S
(x)
=
(
0
, In
U
(x),
1
)
.
4.
Out
S
(i, st, ID
T
)
=
Out
U
(st)
.