C H A P T E R
18
Conurreny Control
Solutions for the Pratie Exerises of Chapter 18
Pratie Exerises
18.1
Answer :
Suppose two-phase loking does not ensure serializabilit y. Then there exists a
set of transations
T
0
,
T
1
:::
T
n
*
1
whih obey 2PL and whih produe a nonseri-
alizable shedule. A nonser ializable shedule implies a yle in the preedene
graph, and we shall show that 2PL annot produe suh yles. Without loss
of generality, assume the following yle exists in t he preedene g raph:
T
0
T
1
T
2
...
T
n
*
1
T
0
. Let
i
be the time at whih
T
i
obtains its last
lok (i.e.
T
i
's lok point). Then for all transations suh t hat
T
i
T
j
,
i
<
j
.
Then for the yle we have
0
<
1
<
2
< ::: <
n
*
1
<
0
Sine
0
<
0
is a ontradition, no suh yle an exist. Hene 2PL annot
produe nonser ializable shedules. Beause of the propert y that for all trans-
ations suh t hat
T
i
T
j
,
i
<
j
, the lok point ordering of the transations
is also a topologial sor t ordering of the preedene g raph. Thus transations
an be ser ialized aording to their lok points.
113
评论0