Database Systems A Practical Approach To Design Implementation And Management, Global Edition, 6Th Ed By Thomas Connolly -Test Bank

Database Systems A Practical Approach To Design Implementation And Management, Global Edition, 6Th Ed By Thomas Connolly -Test Bank

SOLUTIONS TO REVIEW QUESTIONS

AND EXERCISES

FOR PART 6 – DISTRIBUTED DBMSS and REPLICATION (CHAPTERS 24 – 26)

Solutions to Review Questions and Exercises

Chapter 24 Distributed DBMSs – Concepts and Design 3
Chapter 25 Distributed DBMSs – Advanced Concepts 11
Chapter 26 Replication and Mobile Databases 19

Chapter 24 Distributed DBMSs – Concepts and Design

Review Questions

24.1 Explain what is meant by a DDBMS and discuss the motivation in providing such a system.

See Section 24.1.1; motivation given at start of Section 24.1.

24.2 Compare and contrast a DDBMS with distributed processing. Under what circumstances would you choose a DDBMS over distributed processing?

Distributed processing defined at end of Section 24.1.1. Would choose a DDBMS, for example, if each site needed control over its own data, sites had their own existing DBMSs, communication costs would be significantly reduced, and so on.

24.3 Discuss why processes used to design a centralized relational database are not the same as those for a distributed relational database.

It is true that while designing a distributed relational database there are some additional factors to be considered. These factors add some additional steps to those used to design centralized relational databases. See section 24.4

24.4 Discuss the advantages and disadvantages of a DDBMS.

See Section 24.1.2.

24.5 What is the difference between a homogeneous and heterogeneous DDBMS? Under what circumstances would such systems generally arise?

See Section 24.1.3. Heterogeneous DDBMSs may arise as the result of integration of disparate systems. Homogeneous DDBMSs are more likely to be the result of a strategic decision to move to a DDBMS and implement the system in a top-down fashion.

24.6 What are network protocols and why are they important?

Network protocols are a set of rules that determine how messages between computers are sent, interpreted, and processed. Protocols are frameworks that are observed by manufacturers of all networking equipments, software and services. See section 24.2 on network protocols for detailed description of the protocols used today.

24.7 What functionality do you expect in a DDBMS?

Expect the same functionality of a centralized DBMS plus:
• extended communications services to provide access to remote sites and allow transfer of queries and data among the sites using a network;
• extended system catalog to store data distribution details;
• distributed query processing, including query optimization and remote data access;
• extended security control to maintain appropriate authorization/access privileges to the distributed data;
• extended concurrency control to maintain consistency of replicated data;
• extended recovery services to take account of failures of individual sites and the failures of communication links.

See Section 24.3.1.

24.8 What is a multidatabase system? Describe a reference architecture for such a system.

An MDBS is a distributed DBMS in which each site maintains complete autonomy (see end of Section 24.1.3). Reference architecture provided in Figure 24.5.

24.9 One problem area with DDBMSs is that of distributed database design. Discuss the issues that have to be addressed with distributed database design. Discuss how these issues apply to the global system catalog.

The question that is being addressed is how the database and the applications that run against it should be placed across the sites. Two basic alternatives: partitioned or replicated. In partitioned scheme database is divided into a number of disjoint partitions each of which is placed at a different site. Replicated designs can be fully or partially replicated.

Two fundamental design issues are fragmentation and distribution. Mostly involves mathematical programming to minimize combined cost of storing the database, processing transactions against it, and communication. Problem is NP-hard; therefore proposed solutions are based on heuristics.

The global system catalog (GSC) is only relevant if we talk about a distributed DBMS or multi-DBMS that uses a global conceptual schema. Problems are similar to above. Briefly, a GSC may be either global to entire database or local; it may be maintained centrally at one site, or in a distributed fashion over a number of sites; finally, replication – there may be a single copy of the directory or multiple copies. These three dimensions are orthogonal to one another.

24.10 What are the differences between horizontal and vertical fragmentation schemes?

The significant differences are the definitions on the two found in section 24.4.2. Practically, sometimes the database relation that contains a large number of tuples is subdivided for a number of reasons. The same is possible for relations divided based on attributes. Tuple divisions are regarded as horizontal fragments while attributes divisions are regarded as vertical fragments. Based on the available rules, they can be reconstructed to the original relation as described in the same section.

24.11 Describe alternative schemes for fragmenting a global relation. State how you would check for correctness to ensure that the database does not undergo semantic change during fragmentation.

Alternative schemes are: primary horizontal, vertical, mixed, and derived horizontal fragmentation (see Section 24.4).

Correctness rules are: completeness, reconstruction, and disjointness (see Section 24.4 again).

24.12 What are the differences between query optimization processes under centralized and distributed DBMSs? Why is the latter thought to be complex?

See Section 24.5.3

24.13 A DDBMS must ensure that no two sites create a database object with the same name. One solution to this problem is to create a central name server. What are the disadvantages with this approach? Propose an alternative approach that overcomes these disadvantages.

See Section 24.5.1 – Naming Transparency.

Problems with the central name server, which has the responsibility for ensuring uniqueness of all names in the system, are:

• loss of some local autonomy
• performance problems, if the central site becomes a bottleneck
• low availability, if the central site fails, the remaining sites cannot create any new database objects.

An alternative solution is to prefix an object with the identifier of the site that created it. For example, a relation BRANCH created at site S1 might be named S1.BRANCH. Similarly, we would need to be able to identify each fragment and each of its copies. Thus, copy 2 of fragment 3 of the branch relation created at site S1 might be referred to as S1.BRANCH.F3.C2. However, this results in loss of distribution transparency.

An approach that resolves the problems with both these solutions uses aliases for each database object. Thus, S1.BRANCH.F3.C2 might be known as local_branch by the user at site S1. The DDBMS has the task of mapping aliases to the appropriate database object.

24.14 What are parallel database management systems? Describe their architecture and the way they are applied in organizations.

See Section 24.1.1 and Figure 24.3. (a,b,c,d)
Exercises

A multinational engineering company has decided to distribute its project management information at the regional level in mainland Britain. The current centralized relational schema is as follows:-

Employee (NIN, fName, lName, address, DOB, sex, salary, taxCode, deptNo)
Department (deptNo, deptName, managerNIN, businessAreaNo, regionNo)
Project (projNo, projName, contractPrice, projectManagerNIN, deptNo)
WorksOn (NIN, projNo, hoursWorked)
Business (businessAreaNo, businessAreaName)
Region (regionNo, regionName)

where Employee contains employee details and the national insurance number NIN is the key.
Department contains department details and deptNo is the key. managerNIN identifies the employee who is the manager of the department. There is only one manager for each department.
Project contains details of the projects in the company and the key is projNo. The project manager is identified by the projectManagerNIN, and the department responsible for the project by deptNo.
WorksOn contains details of the hours worked by employees on each project and (NIN, projNo) forms the key.
Business contains names of the business areas and the key is businessAreaNo.
and Region contains names of the regions and the key is regionNo.

Departments are grouped regionally as follows:

Region 1: Scotland; Region 2: Wales; Region 3: England

Information is required by business area which covers: Software Engineering, Mechanical Engineering and Electrical Engineering. There is no Software Engineering in Wales and all Electrical Engineering departments are in England. Projects are staffed by local department offices.

As well as distributing the data regionally, there is an additional requirement to access the employee data either by personal information (by Personnel) or by work related information (by Payroll).

24.15 Draw an Entity-Relationship (ER) diagram to represent this system.

Crow’s foot notation used for expediency:

 

 

 

 

 

24.16 Using the ER diagram from Exercise 24.15, produce a distributed database design for this system, and include:

(a) a suitable fragmentation schema for the system;
(b) in the case of primary horizontal fragmentation, a minimal set of predicates;
(c) the reconstruction of global relations from fragments.

State any assumptions necessary to support your design.

Possible solution as follows:

Don’t fragment Business/Region – replicate relations at all sites – only contain a small number of records.

Department
Use primary horizontal fragmentation for Department with minterm predicates :
D1 Region = ‘Scotland’ and businessArea = ‘SE’
D2 Region = ‘Scotland’ and businessArea = ‘ME’
D3 Region = ‘Wales’ and businessArea = ‘ME’
D4 Region = ‘England’ and businessArea = ‘SE’
D5 Region = ‘England’ and businessArea = ‘ME’
D6 Region = ‘England’ and businessArea = ‘EL’

Reconstruction: D1  D2  D3  D4  D5  D6

Employee
Use vertical fragmentation for Employee:

E1: NIN, fName, lName, address, DOB, sex, deptNo(Employee)
E2: NIN, salary, taxCode(Employee)

Then used derived fragmentation on fragment E1:

Eii: E1 deptNo Di 1  i  6

Reconstruction: (E11  E12  E13  E14  E15  E16 ) NIN E2

Projects
Use derived fragmentation for Projects:

Pi: Projects deptNo Di 1  i  6

Reconstruction: (P1  P2  P3  P4  P5  P6 )

WorksOn
Use derived fragmentation for WorksOn:

Wi: WorksOn NIN E1i 1  i  6

24.17 Repeat Exercise 24.16 for the DreamHome case study documented in Appendix A.

Possible solution as follows:

Don’t fragment Branch – replicate relations at all sites – only contain a small number of records.

PropertyForRent
Use primary horizontal fragmentation for PropertyForRent with minterm predicates (for example):
P1j price  39999 AND branchNo = j
P2j 40000  price  69999 AND branchNo = j
P3j price  70000 AND branchNo = j 1  j  maximum number of branches

Reconstruction:  (P1i  P2i  P3i)
i=1

Staff
Assume salaries paid by head office (branch 1 say), so use vertical fragmentation first:

S1: staffNo, fName, lName, branchNo (Staff)
S2: staffNo, position, sex, DOB, salary(Staff)

Then use horizontal fragmentation on fragment S1:

S1i: branchNo= i S1 1  i  j

Reconstruction: (S11  S12  S13 …  S1j ) staffNo S2

Client
Use horizontal fragmentation:

Ci: branchNo= i (Client) 1  i  j

Reconstruction: (C1  C2  C3 …  Cj )

Viewing, Owner
Use derived fragmentation for Viewing and Owner:
Vik: Viewing Pik 1  i  3, 1  k  j
Oik: Owner Pik 1  i  3, 1  k  j

Reconstruction: as for PropertyForRent

24.18 Repeat Exercise 24.16 for the EasyDrive School of Motoring case study documented in Appendix B.2.

24.19 Prepare an action plan for the process of distributing the Wellmeadows case study database documented in Appendix B.3

The answer to the question requires a student to identify list of activities that are necessary in identifying the need for distributed system. Also it will details other processes required in order to achieve the intended objectives. Students must not only know how to distribute the systems, but also be able to plan the process.

24.20 In Section 24.5.1 when discussing naming transparency, we proposed the use of aliases to uniquely identify each replica of each fragment. Provide an outline design for the implementation of this approach to naming transparency.

FUNCTION map(name)
{
IF name appears in the replica table
THEN
result = name of replica of name;
IF name appears in the fragment table
THEN {
result = expression to construct fragment;
FOR each iname IN result {
replace iname in result with map(iname);
}
}
RETURN result;
}

IF name appears in the alias table
THEN
expression = map(name);
ELSE
expression = name;

24.21 Compare a distributed DBMS that you have access to against Date’s 12 rules for a DDBMS. For each rule for which the system is not compliant, give your reasons why you think there is no conformance to this rule.

This is a small student project, the result of which is dependent on the system analyzed.

Chapter 25 Distributed DBMSs – Advanced Concepts

Review Questions

25.1 There can be many types of failures in a distributed environment. Discuss how failure due to network partition is handled by the distributed DBMS.

See Section 25.4.5 under network partitioning.

25.2 One of the most well-known methods for distributed deadlock detection was developed by Obermarck. Explain how Obermarck’s method works and how deadlock is detected and resolved.

See Section 25.3 under Distributed Deadlock Detection.

25.3 Outline two alternative two-phase commit topologies to the centralized topology.

Alternative topologies: linear and distributed 2PC. See end of Section 25.4.3.

25.4 Describe the term “non-blocking” and explain how it is related to two-phase and three-phase commit protocols.

A non-blocking protocol should cater for both site and communication failures to ensure that the failure of one site will not affect processing at another site. In other words, operational sites should not be left blocked.

In the event that a participant has voted COMMIT but has not received global decision and is unable to communicate with any other site that knows the decision, that site is blocked. Although 2PC has a cooperative termination protocol that reduces the likelihood of blocking, blocking is still possible and the blocked process will just have to keep on trying to unblock as failures are repaired

25.5 Describe the protocol used to recover two-phase and three-phase commit in a distributed environment.

The two phase commit is described in section 25.4.3 and the protocol used to recover 2pc is discussed in detail in the subsections of the same section. The three phase commit is described in section 25.4.4 and the protocol used to recover 2pc is discussed in detail in the subsections of the same section

25.6 Specify the layers of distributed query optimization and detail the function of each layer.

See start of Section 25.6.
.

25.7 Discuss the costs that need to be considered in distributed query optimization and discuss two different cost models.

See Section 25.6.3.
.
25.8 Discuss the distributed query optimization algorithms used by R* and SDD-1.

See Section 25.6.3.
.
25.9 Briefly describe the distributed functionality of Oracle11g.

See Section 25.7.1.
.
Exercises

25.10 You are the systems analyst for DreamHome. One of your responsibilities is to ensure that every business transaction performs to the desired standards at all the sites. You have currently received complaints from site managers that customers are experiencing difficulties in accomplishing their transactions. Enough details about the nature of the failure of their transactions have not been provided to you. You are therefore required to prepare an investigation plan that shall be approved by your manager. Indicate in your plan the possible cause of problems and how you are going to approach the problem. Your plan should also guarantee that such problems will not occur again

A well-presented report is expected. Justification must be given for any recommendations made.

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 ‘begin global commit’ message to log
send ‘vote’ message to all participants
do until votes received from all participants
wait
on timeout go to STEP C2b
end do

STEP C2a GLOBAL COMMIT
if all votes are ‘commit’
then begin
write ‘global commit’ record to log
send ‘global commit’ to all participants
end

STEP C2b GLOBAL ABORT
at least one participant has voted abort or coordinator has timed out
else begin
write ‘global abort’ record to log
send ‘global abort’ to all participants
end
end if

STEP C3 TERMINATION
do until acknowledgement received from all participants
wait
end do
write ‘end global transaction record’ to log
finish
end

Algorithm (b) 2PC participants algorithm
begin

STEP P0 WAIT FOR VOTE INSTRUCTION
do until ‘vote’ instruction received from coordinator
wait
end do

STEP P1 VOTE
if vote = ‘commit’ then send ‘commit’ to coordinator
else send ‘abort’ and go to STEP P2b
do until global vote received from coordinator
wait
end do

STEP P2a COMMIT
if global vote = ‘commit’
then perform local commit processing

STEP P2b ABORT
at least one participant has voted abort
else perform local abort processing
end-if

STEP P3 TERMINATION
send acknowledgement to coordinator
finish
end

Algorithm Cooperative termination protocol for 2PC
begin
do while P0 is blocked

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)
then begin
Pi conveys decision to P0
P0 unblocks and finishes
end
end if

STEP 2 HAS Pi VOTED?
if Pi has not voted
then begin
Pi unilaterally aborts
P0 told to abort
P0 unblocks and finishes
end
end if
STEP 3 Pi CANNOT HELP; TRY Pi+1
next Pi
end do
end

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 ‘commit’
then go to STEP 2
else begin
Pr voted ‘abort’ prior to failure or had not voted
Pr aborts unilaterally
Pr recovers independently and finishes
end
end if

STEP 2 IS GLOBAL DECISION KNOWN?
if Pr knows global decision
then begin
Pr takes action in accordance with global decision
Pr recovers independently and finishes
end
end if

STEP 3 Pr CANNOT RECOVER INDEPENDENTLY AND ASKS FOR HELP
Pr asks for help from participant Pr+1 using the cooperative termination protocol
end do
end

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 ‘begin global commit’ message to log
send ‘vote’ message to all participants
do until votes received from all participants
wait
on timeout go to STEP C2b
end do

STEP C2a PRE-COMMIT
if all votes are ‘commit’
then begin
write ‘pre-commit’ message to log
send ‘pre-commit’ message to all participants
end

STEP C2b GLOBAL ABORT
at least one participant has voted abort or coordinator has timed out
else begin
write ‘global abort’ record to log
send ‘global abort’ to all participants
go to STEP 4
end
end if

STEP C3 GLOBAL COMMIT
do until all (pre-commit) acknowledgements received
wait
end-do
write ‘global commit’ record to log
send ‘global commit’ to all participants
end

STEP C4 TERMINATION
do until acknowledgement received from all participants
wait
end do
write ‘end global transaction record’ to log
finish
end

Algorithm (b) 3PC participants algorithm
begin

STEP P0 WAIT FOR VOTE INSTRUCTION
do until ‘vote’ instruction received from coordinator
wait
end do

STEP P1 VOTE
if participant is prepared to commit
then send ‘commit’ message to coordinator
else send ‘abort’ message to coordinator and go to STEP P2b
do until global vote received from coordinator
wait
end do

STEP P2a PRE-COMMIT
if global instruction = ‘pre-commit’
then go to STEP P3 (and wait for global commit)
end-if

STEP P2b ABORT
at least one participant has voted abort
perform local abort processing
go to STEP P4

STEP P3 COMMIT
do until ‘global commit’ received from coordinator
wait
end-do
perform local commit processing