Database Reference
In-Depth Information
Deadlock
Locking can introduce problems of its own, principally the problem of
deadlock. Deadlock is a situation in which two or more transactions are in simulta-
neous wait state, each one waiting for one of the others to release a lock before it
can proceed. It is a responsibility of the universal machine program to detect it and
break it. Breaking the deadlock involves choosing one of the deadlock transactions
as the victim
ID
T
and rolling it back: invoking CALL of ROLLBACK of this
ID
T
toward the RDB machine
M
R
, thereby releasing (in
M
R
) its locks and so allowing
some other transaction to proceed. Now we are in a position to see how locking
is implemented in our categorial setting. Let us define a specialization of the uni-
versal (specified in Definition
39
) and categorial RDB machines for the concurrent
multiple-user/programs systems:
Definition 43
A concurrent multiple-user universal machine
M
UC
is a universal
general purpose programming language machine
M
U
with the following specific
features, where
ID
T
is the transaction identifier of the current transaction:
1. The extended input function
In
∗
EU
satisfies the following properties:
f
:
S
U
→
S
U
if
z
=
(n,m, ID
T
,R)
∈
INP
;
λIn
∗
EU
(z)
=
id
:
S
U
→
S
U
(
identity function
)
otherwise
,
where
f
is a mapping such that for a state
st
∈
S
U
,
f(st)
∈
S
U
is obtained from
st
by the following setting:
x
1
=
n,x
2
=
m
, and the relation
R
is loaded into
the subset of registers of
S
U
used as a dynamic data memory ('System/data/IO
memory' of
M
UC
in Fig.
6.2
).
2. The output function
Out
U
satisfies the following properties:
∅
(
empty set
)
if
t
1
(st)
=
1
;
=
Out
U
(st)
(n,
0
, ID
T
,L)
otherwise
,
where
L
is a list of values in
I/O
memory of
M
UC
(used for 'INSERT...' and
'UPDATE...'SQLstatementsinthesourceprogram
P
) and
n
is the value of
x
1
.
The output of this function is then transmitted to the concurrent RDB machine
M
RC
.
3. The initial input value for the initial input function
In
E
contains also all programs
(written for a database with a given schema) to be executed concurrently before
a turn-off of the machine. They are loaded together with a Main program for
time-shared Supervisor into its program memory.
A concurrent categorial RDB machine
M
RC
is a more complex version of the
categorial RDB machine
M
R
(specified in Definition
40
), with the new additional
features:
Its Buffer Manager dedicates, for each existing transaction identifier
ID
T
=
N
a
generated during the execution of some source program
P(i)
in the concurrent uni-
versal machine
M
UC
, a dynamic data memory where all
RA
arrows (obtained after
variable bindings for the Application Plans
P
n
,
n
≥
3, obtained by compilation from
