Exercises Database Design - 2020 /nvDieu
HO CHI MINH CITY UNIVERSITY OF TRANSPORT
Kiến thức - Kỹ năng - Sáng tạo - Hội nhập
Sứ mệnh - Tầm nhìn
Triết lý Giáo dục - Giá trị Cốt lõi
Contents
0 Database and Tool 2
1 Basic ER Diagram 2
2 Mapping to a Relational Database 3
3 Weak entity 3
4 Functional Dependencies (FDs) 3
5 Amstrong’s Axiom 4
6 Closure 4
7 Keys 7
8 Normal Form by FDs 7
9 Multivalued Dependencies (MVDs) 9
10 Tableau Chase Test 10
11 More Normal form and Dependencies 12
1/12
Exercises Database Design - 2020 /nvDieu
0 Database and Tool
1. MySQL: https://dev.mysql.com/downloads/mysql/
IDE: Workbench
2. PostgreSQL: https://www.postgresql.org
IDE: Pgadmin
3. SQLServer: https://www.microsoft.com/en-us/sql-server/sql-server-downloads. Chọn bản Express.
IDE: SSMS
4. ERD & DFD: https://app.diagrams.net/
1 Basic ER Diagram
Exercise 1.1
Draw an ER diagram for an entity called HOTEL and include no fewer than five attributes for the entity. Of the five
attributes, include at least one composite attribute and one multivalued attribute.
Exercise 1.2
Suppose we reconsider our STUDENT example, and the only attributes of student are student number and name. Let us
suppose we have another entity called HIGH SCHOOL — the high school from which the student graduated. For the
HIGH SCHOOL entity, we will record the high school name and the location (meaning city and state). Draw the ER
diagram for it.
Exercise 1.3
If we have two entities, a PLANE and a PILOT, and describe the relationship between the two entities as
“A PILOT flies a PLANE.”
What should the relationship read from the side of the other entity?
Exercise 1.4
Suppose a college had one dormitory with many rooms. The DOMITORY entity, which is actually a “dormitory room”
entity since there is only one dorm. Dormitory has the attributes room number and singledouble (meaning there are
private rooms and double rooms). Let us suppose the STUDENT entity in this case contains the attributes student
number, student name, and cell telephone number. Draw the ER diagram linking the two entities. Name your
relationships.
Exercise 1.5
West Florida Mall
A new mall, West Florida Mall, just had its grand opening three weeks ago in Pensacola, Florida. This new mall is
attracting a lot of customers and stores. West Florida Mall, which is part of a series of malls owned by a parent company,
now needs a database to keep track of the management of the mall in terms of all its stores as well as the owners and
workers in the stores. Before we build a database for this system of malls, the first step will be to design an ER diagram
for the mall owner. We gathered the following initial user specifications about the mall, with which we can start creating
the ER diagram:
1. We need to record information about the mall and each store in the mall. We need to record the mall’s name and
address. A mall, at any point in time, must contain one or more stores.
2. For each store we will need to keep the following information: store number (which will be unique), the name of
the store, location of store (room number), departments, the owner of the store, and manager of the store. Each
store may have more than one department with each department having a manager. Each store will have only one
manager. Each store is owned by only one owner. Each store is located in one and only one mall.
3. A store manager can manage only one store. We must record information on the store manager—the name, Social
Security number, which store he or she is working for, and the salary.
4. The store owner is a person. We will record name, address, and of cell phone about the store owner. A store owner
must own at least one store and may own more than one.
2/12
Exercises Database Design - 2020 /nvDieu
2 Mapping to a Relational Database
Exercise 2.1
Mapping entity in exercise 1.x to Relational Database.
Exercise 2.2
Mapping Relationship in exercise 1.x to Relational Database.
Exercise 2.3
Consider a STUDENT and ADVISOR database. Students have a student number and student name. Advisors have
names, office numbers, and advise in some major. The major the advisor advises in is designated by a major code (e.g.,
Chemistry, CHEM; Biology, BIOL; Computer Science, COMPSC; . . .). Draw the ER diagram using the Chen-like
model. Follow the methodology and include all English descriptions of your diagram. Map the ER diagram to a
relational database and include some sample data.
Exercise 2.4
You want to record the following data in a database: restaurant name and location, employee names and IDs, capacity of
restaurant, smoking or nonsmoking area in restaurant, hours of operation for restaurant (assume same hours every day),
employee salaries and titles. An employee can work for only one restaurant. A restaurant must have at least one
employee working for it. Draw the ER diagram using the Chen-like model. Follow the methodology and include all
English descriptions of your diagram. Map the ER diagram to a relational database and include some sample data.
Exercise 2.5
Record the following data in a database: business name, owner, location(s), telephone numbers, delivery truck number,
truck capacity, usual route description (e.g., North, West, Central, Lake, . . .). Draw the ER diagram using the Chen-like
model. Present the relational mapping. Follow the methodology and include all English descriptions of your diagram.
3 Weak entity
4 Functional Dependencies (FDs)
Exercise 4.1
Consider relation r below:
r: R( A B C D E)
t1 0 0 0 0 0
t2 0 1 1 1 0
t3 1 0 2 2 0
t4 1 0 3 2 0
t5 2 1 4 0 0
Which of the following FDs does r satisfy (why?):
a) A → B
b) AB → D
c) C → BDE
d) E → A
e) A → E
Exercise 4.2
Prove that r satisfies X → Y if and only if X is a key of π XY (r).
Exercise 4.3
Let r be a relation on R, with X a subset of R. Show that if π X (r) has the same number of tuples as r, then r satisfies
X → Y for any subset Y of R.
3/12
Exercises Database Design - 2020 /nvDieu
Exercise 4.4
Prove or disprove the following inference rules for a relation r(R) with W, X, Y, Z subsets of R.
a) X → Y and Z → W imply XZ → Y W .
b) XY → Z and Z → X imply Z → Y .
c) X → Y and Y → Z imply X → Y Z.
d) X → Y , W → Z , and Y ⊇ W imply X → Z.
5 Amstrong’s Axiom
Exercise 5.1
{ }
Consider F = AB → CD, A → BE, BH → DK, H → BC
Prove by Amstrong: F |= AH → CK
Exercise 5.2
{ }
Consider F = AB → E, AG → J, BE → I, E → G, GI → H
Prove by Amstrong: F |= AB → GH
Exercise 5.3
{ }
Consider F = A → D, B → CE, E → H, D → E, E → C
Prove by Amstrong:
a) F |= B → H
b) F |= AB → CH
Exercise 5.4
{ }
Consider F = D → BK, AB → GK, B → H, CE → AG, H → E, K → G, EH → K, G → AH
Prove by Amstrong:
a) F |= AB → GH
b) F |= DE → AG
c) F |= BH → EK
6 Closure
Exercise 6.1
Show that for any set of FDs F , F + = (F + )+ .
Exercise 6.2
{ R(ABCDE) and set of functional dependencies:
Suppose }
F = A → BC, CD → E, B → D, E → A . Compute:
a) CDF+
b) EF+
Exercise 6.3
{ R(ABCDEK) and set of functional dependencies:
Suppose }
F = AB → C, BC → AD, D → E, CK → B . Compute:
a) BCKF+
b) CDF+
c) DF+
4/12
Exercises Database Design - 2020 /nvDieu
Exercise 6.4
{ R(ABCDEKGH) and set of functional dependencies:
Suppose }
F = A → BC, E → C, AH → D, CD → E, D → AEH, DH → BC . Compute:
a) AEF+
b) BCDF+
Exercise 6.5
Consider:
{ }
F1 = { AB → CD, A → BE, BH → DK, H → BC }
F2 = { AB → E, AG → J, BE → I, E → G, GI →}H
F3 = { A → D, B → CE, E → H, D → E, E → C }
F4 = D → BK, AB → GK, B → H, CE → AG, H → E, K → G, EH → K, G → AH
Compute:
a) AHF+1
b) ABF+2
c) BF+3
d) ABF+3
e) ABF+4
f) DEF+4
g) BHF+4
Exercise 6.6
{ }
Consider F = A → B, A → C, CD → E, B → D, E → A
Which of the following functional dependencies is NOT implied by the above set ?
a) CD → AC
b) BD → CD
c) BC → CD
d) AC → BC
Exercise 6.7
From Axiom 1, 2, 3 prove Axiom 4, 5 and 6.
Exercise 6.8
Prove that inference axioms 1, 2, and 3 are independent. That is, no one of them can be proved from the other two.
Exercise 6.9
R(ABCD)
{ having two FDs sets: }
F = { A → B, B → C, AB → D , }
G = A → B, B → C, A → C, A → D
Are the two sets equivalent ?
Exercise 6.10
R(ABCD)
{ having two FDs sets: }
F = { A → B, B → C, A → C },
G = A → B, B → C, A → D
Are the two sets equivalent ?
Exercise 6.11
R(ACDEH)
{ having two FDs sets: }
F = { A → C, AC → D, E}→ AD, E → H ,
G = A → CD, E → AH
Are the two sets equivalent ?
5/12
Exercises Database Design - 2020 /nvDieu
Exercise 6.12
R(ABCDE)
{ having two FDs sets: }
F = { A → BC, A → D, CD → E , }
G = A → BCE, A → ABD, CD → E
Are the two sets equivalent ?
Exercise 6.13
R(ABCDE)
{ having two FDs sets: }
F = { AB → C, A → B, B → C, }A → C ,
G = AB → C, A → B, B → C
Are the two sets equivalent ?
Exercise 6.14
{ }
Consider F = A → B, B → C, C → A, B → A, A → C
a) Find a minimum cover Fc of F by loop from right to left
b) Find a minimum cover Fc of F by loop from left to right
Exercise 6.15
{ }
Consider F = A → BC, B → C, A → B, AB → C
Find a minimum cover Fc of F
Exercise 6.16
{ }
Consider F = A → BC, CD → E, B → D, E → A
Find a minimum cover Fc of F
Exercise 6.17
{ }
Consider F = B → A, AD → BC, C → ABD
Find a minimum cover Fc of F
Exercise 6.18
{ R(ABC),
Consider }
F = { AB → C, A → B}
G = A → B, B → C
a) Find a minimum cover Fc of F
b) Is G a minimal cover of F ? Otherwise give a data instance of R satisfy F but not G
Exercise 6.19
{ }
Consider R(ABCDE) , F = AB → CD, B → CD, CD → AE, DE → AB, D → E
Compute Projected Functional Dependencies:
a) π R (ABC) (F )
1
b) π R (BCD) (F )
2
c) π R (CDE) (F )
3
d) π R (ADE) (F )
4
e) π R (BDE) (F )
5
f) π R (AE) (F )
6
g) π R (DE) (F )
7
6/12
Exercises Database Design - 2020 /nvDieu
Exercise 6.20
{ R(ABCDEGH) ,
Consider }
F = AB → CD, E → D, ABC → DE, E → AB, D → AG, ACD → BE
Compute Projected Functional Dependencies:
a) π R (ABCD) (F )
1
b) π R (DEGH) (F )
2
c) π R (CDE) (F )
3
d) π R (ADE) (F )
4
e) π R (BDE) (F )
5
f) π R (AE) (F )
6
g) π R (DE) (F )
7
7 Keys
Exercise 7.1
{ R(ABCDEH) with a set of FDs }
Consider
F = A → B, BC → D, E → C, D → A
What are the candidate keys of R
a) AE, BE
b) AE, BE, DE
c) AEH, BEH, BCH
d) AEH, BEH, DEH
Exercise 7.2
{ R(DEGHIJKLM N ) with a set of FDs
Consider }
F = DE → G, D → IJ, EH → KL, K → M, L → N
What is the key for R ?
a) EF
b) DEH
c) DEHKL
d) E
Exercise 7.3
{ R(ABCDEKGH) with a set of FDs
Consider }
F = ABC → DE, AB → D, DE → ABCK, E → C
Find all the candidate keys of R
Exercise 7.4
{ R(ABCDEGHK) with a set of FDs
Consider }
F = CD → A, EC → H, GHB → AB, C → D, EG → A, H → B, BE → CD, EC → B
Find all the candidate keys of R
8 Normal Form by FDs
Exercise 8.1
Which normal form of relational scheme below:
{ }
a) R1 (ABC), F1 = A → C
{ }
b) R2 (ABC), F2 = C → B
{ }
c) R3 (ABCD), F3 = A → B, B → A
{ }
d) R4 (ABCD), F4 = D → C, B → A
7/12
Exercises Database Design - 2020 /nvDieu
{ }
e) R5 (ABCD), F5 = B → D, C → D
{ }
f) R6 (ABCDE), F6 = AB → C, B → A, D → A
{ }
g) R7 (ABCDE), F7 = AB → C, C → D, D → A
{ }
h) R8 (ABCDE), F8 = AB → CD, CD → AE, D → A
{ }
i) R9 (ABCDE), F9 = D → A, BC → E, A → C
{ }
j) R10 (ABCDEG), F10 = AB → CG, G → D, B → D
{ }
k) R11 (ABCDE), F11 = E → D, C → B, A → E B → A, D → C
{ }
l) R12 (ABCDE), F12 = AC → B, BD → C, CE → D
m) R13 (ABCD), F13 = ∅
Exercise 8.2
{ }
Consider R(ABCD), F = A → C, B → D
a) Keys and Normal form?
b) Decompose R
Exercise 8.3
{ }
Consider R(ABCD), F = AC → D
a) Keys and Normal form?
b) Decompose R
Exercise 8.4
{ }
Consider R(ABCDE), F = AB → C, B → A, D → A
a) Keys and Normal form?
b) Decompose R
Exercise 8.5
{ }
Consider R(ABCDE), F = CD → A, EC → B, AD → C
a) Keys and Normal form?
b) Decompose R
Exercise 8.6
{ R(ABCDEGH),
Consider }
F = CD → A, EC → H, GHB → AB, C → D, EG → A, H → B, BE → CD, EC → B
a) Keys and Normal form ?
b) Decompose R
Exercise 8.7
{ }
Consider R(ABCD), F = A → B, B → C, D → B
a) Normal form of R ?
b) If R is not good, let try to find a good decomposition for R
Exercise 8.8
{ }
Consider R(ABCD), F = A → B, B → C, A → D, D → C
One decomposition ρ of R:
R1 (AB), F1
R2 (AC), F2
R3 (BD), F3
a) Fi ?
b) Keys and Normal form of Ri ?
8/12
Exercises Database Design - 2020 /nvDieu
Exercise 8.9
{ R(A B D E M N O P X Y Z V W ),
Consider }
F = D → XM N P E, M P N → EY ABO, M N → ZO, O → V, P → ABW , AB → P, N E → M P
One decomposition ρ of R:
R1 (DXM N P E), F1
R2 (M N P EY ABO), F2
R3 (M N ZO), F3
R4 (OV ), F4
R5 (P ABW ), F5
a) Fi ?
b) Keys and Normal form of Ri ?
c) Evaluate the quality of ρ (Normal form, Conserve information, Conserve FDs)
d) If ρ is not good, let make a improvement of ρ
Exercise 8.10
{ R(ABCDEGH),
Consider }
F = CD → A, EC → H, GHB → AB, C → D, EG → A, H → B, BE → CD, EC → B
Evaluate
{ the decomposition below (Normal form,
} Conserve information, Conserve FDs)
ρ = R1 (ABC), R2 (CDEG), R3 (EGH)
Exercise 8.11
Give an example of a relation in 3NF that has some prime attribute transitively dependent upon a key
Exercise 8.12
Let R1 and R2 be relation schemes with R1 ∩ R2 = X. Show that for any relation r(R1 R2 ) that satisfies X → R2 ,
r = π R1 (r) ▷◁ π R2 (r)
9 Multivalued Dependencies (MVDs)
Exercise 9.1
Consider relation r below:
r: R( A B C D E)
t1 0 0 1 0 0
t2 0 0 2 1 0
t3 0 2 2 0 1
From data instance R above make R satisfies each MVD below:
a) AB ↠ C
b) AB ↠ E
c) D ↠ C
d) AD ↠ C
e) C ↠ DE
Exercise 9.2
{ }
Let R(ABCDE), D = A ↠ BC, A ↠ E, E ↠ CD
Proving by MVDs axiom:
a) D |= A ↠ C
b) D |= A ↠ BD
c) D |= AC ↠ BD
d) D |= AC ↠ BE
e) D |= DE ↠ AC
f) D |= DE ↠ AB
9/12
Exercises Database Design - 2020 /nvDieu
Exercise 9.3
{ }
Let R(ABCDGH), D = A ↠ B, B ↠ GH, CD ↠ G
Proving by MVDs axiom:
a) D |= BC ↠ AD
b) D |= BC ↠ GH
c) D |= BC ↠ DG
d) D |= CD ↠ AB
e) D |= CD ↠ BG
f) D |= CD ↠ GH
Exercise 9.4
{ }
Let R(ABCGHI), D = A ↠ B, B ↠ HI, CG ↠ H
++
Compute XD :
a) A++
D
b) AG++
D
c) BG++
D
++
d) BCD
e) HG++
D
Exercise 9.5
Prove the correctness of inference axioms M1 and M2.
Exercise 9.6
Prove the correctness of inference axiom M3.
Exercise 9.7
We know axiom M7 is correct from Lemma 8.3
Prove the correctness of inference axiom M4 using axioms M3 and M7.
Exercise 9.8
Prove the correctness of inference axiom M5 using axioms M4.
Exercise 9.9
Prove the correctness of inference axiom M6 using axioms M1-M5 and M7
10 Tableau Chase Test
Exercise 10.1
{ }
Consider D = AB → CD, A → BE, BH → DK, H → BC
Prove by Tableau Chase test: D |= AH → CK
Exercise 10.2
{ }
Consider D = AB → E, AG → J, BE → I, E → G, GI → H
Prove by Tableau Chase test: D |= AB → GH
Exercise 10.3
{ }
Consider D = A → D, B → CE, E → H, D → E, E → C
Prove by Tableau Chase test:
a) D |= B → H
b) D |= AB → CH
10/12
Exercises Database Design - 2020 /nvDieu
Exercise 10.4
{ }
Consider D = D → BK, AB → GK, B → H, CE → AG, H → E, K → G, EH → K, G → AH
Prove by Tableau Chase test:
a) D |= AB → GH
b) D |= DE → AG
c) D |= BH → EK
Exercise 10.5
{ R(ABCDE) and set of functional dependencies:
Suppose }
D = A → BC, CD → E, B → D, E → A . Using Tableau Chase test to compute:
+
a) CDD
+
b) ED
Exercise 10.6
{ R(ABCDEK) and set of functional dependencies:
Suppose }
D = AB → C, BC → AD, D → E, CK → B . Using Tableau Chase test to compute:
+
a) BCKD
+
b) CDD
+
c) DD
Exercise 10.7
{ R(ABCDEKGH) and set of functional dependencies:
Suppose }
D = A → BC, E → C, AH → D, CD → E, D → AEH, DH → BC . Using Tableau Chase test to compute:
+
a) AED
+
b) BCDD
Exercise 10.8
Consider:
{ }
D1 = { AB → CD, A → BE, BH → DK, H → BC }
D2 = { AB → E, AG → J, BE → I, E → G, GI →}H
D3 = { A → D, B → CE, E → H, D → E, E → C }
D4 = D → BK, AB → GK, B → H, CE → AG, H → E, K → G, EH → K, G → AH
Using Tableau Chase test to compute:
+
a) AHD1
+
b) ABD 2
+
c) BD 3
+
d) ABD 3
+
e) ABD 4
+
f) DED4
+
g) BHD4
Exercise 10.9
{ }
Consider D = A → B, A → C, CD → E, B → D, E → A
Using Tableau Chase test to compute: Which of the following functional dependencies is NOT implied by the above
set ?
a) CD → AC
b) BD → CD
c) BC → CD
d) AC → BC
11/12
Exercises Database Design - 2020 /nvDieu
Exercise 10.10
{ }
Let R(ABCDE), D = A ↠ BC, A ↠ E, E ↠ CD
Using Tableau Chase test to compute:
a) D |= A ↠ C
b) D |= A ↠ BD
c) D |= AC ↠ BD
d) D |= AC ↠ BE
e) D |= DE ↠ AC
f) D |= DE ↠ AB
Exercise 10.11
{ }
Let R(ABCDGH), D = A ↠ B, B ↠ GH, CD ↠ G
Using Tableau Chase test to compute:
a) D |= BC ↠ AD
b) D |= BC ↠ GH
c) D |= BC ↠ DG
d) D |= CD ↠ AB
e) D |= CD ↠ BG
f) D |= CD ↠ GH
11 More Normal form and Dependencies
Exercise 11.1
Modify the relation r below to satisfy the MVDs A ↠ BC and CD ↠ BE by adding rows.
r: R( A B C D E )
t1 0 0 0 0 0
t2 0 1 0 1 0
t3 1 0 0 0 1
Exercise 11.2
Prove that if a relation r(R) satisfies the MVDs X ↠ Y1 , X ↠ Y2 ... X ↠ Yk , where R = XY1 Y2 ...Yk , then r
decomposes converse information onto the relation schemes XY1 , XY2 , ..., XYk .
Exercise 11.3
Let r(R) be a relation where R1 ⊆ R, R2 ⊆ R and R = R1 R2 . Prove that r = π R1 (r) ▷◁ π R2 (r) if and only if:
Count(π R ([X = x](r))) = Count(π R1 ([X = x](r))) × Count(π R2 ([X = x](r))) for every X-value x in r
Exercise 11.4
Prove that if relation r(R) satisfies X ↠ Y and Z = R − XY , then
π Z (σ X=x (r)) = π Z (σ XY =xy (r))
for every XY -value xy in r
Exercise 11.5
Let relation scheme R} and let W, X, Y, Z ⊆ R. Show that:
{
X ↠ Y , Z ⊆ W |= XW ↠ Y Z
Exercise 11.6
Prove the correctness of inference axiom M6 using axioms M1-M5 and M7
Exercise 11.7
} let X, Y, Z ⊆ R. Show that:
{ relation scheme R and
Let
X ↠ Y , XY → Z |= X → Z − Y
12/12
