11
Chapter 25 Distributed DBMSs – Advanced Concepts
Review Questions
25.1 In a distributed environment, locking-based algorithms can be classified as centralized, primary copy,
25.2 One of the most well-known methods for distributed deadlock detection was developed by Obermarck.
25.3 Outline two alternative two-phase commit topologies to the centralized topology.
25.4 Explain the term nonblocking protocol and explain why two-phase commit protocol is not a non-
blocking protocol.
A nonblocking protocol should cater for both site and communication failures to ensure that the failure
25.5 Discuss how the three-phase commit protocol is a non-blocking protocol in the absence of complete
site failure.
25.6 Specify the layers of distributed query optimization and detail the function of each layer.
12
25.7 Discuss the costs that need to be considered in distributed query optimization and discuss two
different cost models.
.
25.8 Discuss the distributed query optimization algorithms used by R* and SDD-1.
.
25.9 Briefly describe the distributed functionality of Oracle11g.
.
Exercises
25.10 You have been asked by the Managing Director of DreamHome to investigate the data distribution
requirements of the organization and to prepare a report on the potential use of a distributed
DBMS. The report should compare the technology of the centralized DBMS with that of the
distributed DBMS, and should address the advantages and disadvantages of implementing a
DDBMS within the organization, and any perceived problem areas. The report should also
address the possibility of using a replication server to address the distribution requirements.
Finally, the report should contain a fully justified set of recommendations proposing an
appropriate solution.
25.11 Give full details of the centralized two-phase commit protocol in a distributed environment. Outline
the algorithms for both coordinator and participants.
Algorithm (a) 2PC coordinator algorithm
begin
STEP C1 VOTE INSTRUCTION
write
send
STEP C2a GLOBAL COMMIT
13
STEP C2b GLOBAL ABORT
at least one participant has voted abort or coordinator has timed out
STEP C3 TERMINATION
do until acknowledgement received from all participants
Algorithm (b) 2PC participants algorithm
begin
STEP P0 WAIT FOR VOTE INSTRUCTION
STEP P1 VOTE
if
STEP P2a COMMIT
STEP P2b ABORT
14
STEP P3 TERMINATION
Algorithm Cooperative termination protocol for 2PC
STEP 1 HELP REQUESTED FROM Pi
P0 sends a message to Pi asking for help to un-block
if Pi knows the decision (Pi received global commit/abort or Pi unilaterally aborted)
STEP 2 HAS Pi VOTED?
if Pi has not voted
Algorithm 2PC participant restart following failure
begin
do while Pr is blocked
STEP 1 ASCERTAIN STATUS OF Pr IMMEDIATELY PRIOR TO FAILURE if Pr voted
15
end
end-if
STEP 2 IS GLOBAL DECISION KNOWN?
if Pr knows global decision
then begin
STEP 3 Pr CANNOT RECOVER INDEPENDENTLY AND ASKS FOR HELP
25.12 Give full details of the three-phase commit protocol in a distributed environment. Outline the
algorithms for both coordinator and participants.
Algorithm (a) 3PC coordinator algorithm
begin
STEP C1 VOTE INSTRUCTION
write
end-do
STEP C2a PRE-COMMIT
if
STEP C2b GLOBAL ABORT
at least one participant has voted abort or coordinator has timed out
16
end
end-if
STEP C3 GLOBAL COMMIT
do until all (pre–commit) acknowledgements received
STEP C4 TERMINATION
do until acknowledgement received from all participants
Algorithm (b) 3PC participants algorithm
begin
STEP P0 WAIT FOR VOTE INSTRUCTION
do until
wait
end-do
STEP P1 VOTE
STEP P2a PRE-COMMIT
STEP P2b ABORT
17
STEP P3 COMMIT
25.13 Analyze the DBMSs that you are currently using and determine the support each provides for the
X/Open DTP model and for data replication.
25.14 Consider six transactions T1, T2, T3, T4, and T5 with:
T1 initiated at site S1 and spawning an agent at site S2,
The locking information for these transactions is shown in following table.
18
(a) Produce the local wait-for-graphs (WFGs) for each of the sites. What can you conclude from the local
WFGs?
(b)
detection works. What can you conclude from the global WFG?
Cycle at site 1, so move WFG from Site 1 to site 3. The resulting WFG shows a cycle:
T
1
T
2
T
1
T
4
T
2
T
3
Site 1 Site 2 Site 3