NATIONAL UNIVERSITY OF LESOTHO

DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE

CS4430 - DISTRIBUTED DATABASE SYSTEMS

Tutorial 02 - Distributed Database Design

26 April 2023

1. Consider the following schemas:

Global schema: Student (regno, name, coursename, year_of admission, DOB)

 
Fragment schema:

STU1 = sv coursename MBA ( Pregno, name, course-name (Student))

STU2 = sv coursename MBA (Pregno, year-of-admission, DOB (Student))
STU3 = sv coursename PGDBM ( P regno, name, course-name (Student))

 STU4 = sv coursename PGDBM ( P regno,year-of-admission, DOB (Student))


 
Allocation schema:

STU1 at sites 1, 5
STU2 at sites 2, 6
STU3 at sites 3, 7 and

 STU4 at sites 4, 8

(a) Write an application that requires the student ID (regno) from the terminal and outputs
the name, course name, DOB, and year-of-admission at levels fragment, location, and
local mapping transparency.

(b) Write an application that moves the student No 102 from the course MBA to the
course PGDBM at dierent levels of data distribution transparency

2. A country-wide drug supplier chain operates from ve dierent cities in the country and

 
maintains the following database:

SHOP (ds-id, ds-city, ds-contactno)

MEDICINE (med-id, med-name, manuf-id)
MANUFACTURER (manuf-id, manu-name, manu-city)

 ORDER (med-id, ds-id, qty)


Suggest a fragmentation and allocation schema considering the following frequent queries:

(a) List the manufacturers' names who belong to the same city in which the drug shop that
has placed an order resides.

(b) How many orders are generated from a city, say C?

Justify your design and mention your assumptions clearly.

1
3. Comment on the following statement:

(a) Semijoin can be used to reduce the cost of a join operation in a distributed environment.

(b) Join operation should be done after selection, projection and union operations for
distributed database systems.


4. Assume that relation PROJ of the sample database is horizontally fragmented as follows:

PROJ1 = sv PNO "P2" (PROJ)

PROJ2 = sv PNO>"P2" (PROJ)


Transform the following query into a reduced query on fragments:

SELECT ENO, PNAME


FROM PROJ NATURAL JOIN ASG
WHERE PNO = "P4"

5. Assume that relation PROJ is horizontally fragmented as in Problem 3 above, and that

 
relation ASG is horizontally fragmented as:

ASG1 = sv PNO "P2" (ASG)

ASG2 = sv "P2"<PNO"P3" (ASG)

 ASG3 = sv PNO>"P3" (ASG)


Transform the following query into a reduced query on fragments, and determine whether it

 
is better than the fragment query:

SELECT RESP, BUDGET

FROM ASG NATURAL JOIN PROJ

WHERE PNAME = "CAD/CAM"


6. Consider the following join graph and the following relation information and describe an
optimal join program based on the objective function of total transmission time.

 size(EMP) = 100

size(ASG) = 200
size(PROJ) = 300
size(EMP ASG) = 300

 size(ASG PROJ) = 200.


7. Consider the join graph shown in Problem 5, and give a program (possibly not optimal) that
reduces each relation fully by semijoins.

2
 
8. Consider the following relations:

EMP (ENO, ENAME, TITLE)

ASG (ENO, PNO, RESP, DUR)

Write down suitable queries in SQL-like syntax and in relational algebra for nding the names
of employees who are managers of any project. Is the query optimized? If not optimize it.

 
9. Consider the following schemas:

EMP (ENO, ENAME, TITLE)

PROJ (PNO, PNAME, BUDGET)

 ASG (ENO, PNO, RESP, DUR)


Using INGRES algorithm, detach and substitute for the query Retrieve names of employees
working on the ORACLE project, considering there are four dierent values for ENO, which
are E1, E2, E3 and E4.

 
10. Consider the following query on our engineering database:

SELECT ENAME,SAL
FROM PAY NATURAL JOIN EMP NATURAL JOIN ASG
NATURAL JOIN PROJ
WHERE (BUDGET>200000 OR DUR>24)

 AND (DUR>24 OR PNAME = "CAD/CAM")

Assume that relations EMP, ASG, PROJ, and PAY have been stored at sites 1, 2, and 3

according to the table below. Assume also that the transfer rate between any two sites is
equal and that data transfer is 100 times slower than data processing performed by any site.
Finally, assume that size(R./S) = max (size(R), size(S)) for any two relations R and , and
the selectivity factor of the disjunctive selection of the query is 0.5. Compose a distributed
program that computes the answer to the query and minimizes total time.

Relation Site 1 Site 2 Site 3

EMP 2000
ASG 3000
PROJ 1000
PAY 500

It is the work of true education to train the youth to be thinkers, and not mere reectors of other men's thought -
Education, p17.