Introduction to Database System (IS230)

First Semester 1437/1438 (Fall 2016)

Normalization Study Guide

Q1) What constraint does the one functional dependency DeptNo  Dname define for the
relation schema DeptSales(DeptNo, Dname, Month, Year, Sales)?
a) DeptNo must be a primary key for DeptSales
b) DeptNo must be a superkey for DeptSales
c) If two tuples have the same value for DeptNo then they have the same value for Dname
d) All of the above

Q2) Given the relation schema, DeptSales(DeptNo, Dname, Month, Year, Sales) and the
set of functional dependencies,
F = {DeptNoDname; DeptNo,Month,YearSales}, then which of the following
functional dependencies is a valid inference?
a) DeptNoSales
b) DeptNo,Month,YearDname
c) DnameSales
d) Other Specify

Q3) Two sets of functional dependencies, F and G are equivalent if

a) F and G contain no redundant functional dependencies
b) G is a subset of F
c) F and G have the same number of functional dependencies
d) Other Specify

Q4) Given the relation DeptSales(DeptNo, Dname, Month, Year, Sales) with FDs
{DeptNoDname; DeptNo,Month,YearSales}, then DeptSales could suffer from
a) Insertion anomalies
b) Redundancy and inconsistency
c) Deletion anomalies
d) All of the above

Q5) Given the relation R(A,B,C,D) with FDs F = {ABC; AD} shown below. What
values could be inserted for the missing D and A column values. The domain for D is
{d1,d2,d3,d4,d5,d6,d7} and the domain for A is {a1,a2,a3,a4}.

A B C D
a1 b1 c1 d1
a1 b2 c2
b1 c1 d3
a4 b1 c4 d4
a) d1 and a1
b) d5 and a4
c) d1 and a3
d) Other Specify

Q6)Given the relation schema R(A,B,C,D) with FDs {ABC; ABD; CDA;
CDB}. Is relation schema R in BCNF?
a) yes
b) No
c) 3NF but not BCNF
d) Other Specify

Q6)Given relation schema R(A,B,C,D) with FDs F = {ABC; BCD; AB},

then which of the following statements is true?
a) BC is a member of F+
b) ABCD is a member of F+
c) CDCD is a member of F+
d) Both b and c

Q7) The BCNF decomposition algorithm could produce the following results for relational
schema R(A,B,C,D) with the FDs {AB; BC; CD}
a) R1(A,B) and R2(B,D) and R3(B,C)
b) R1(A,B) and R2(B,C) and R3(C,D)
c) both a and b
d) Other Specify

Q8) Given the relation schema R(A,B,C) and functional dependencies F =

{AB C, BA; CB }. Which attribute(s) are prime, i.e. part of a candidate key?
a) only A
b) only B
c) A and B
d) B and C

Q9) The highest normal form for relation schema R(A,B,C) with functional
dependencies F = {AB C; BA; CB } is
a) 1NF
b) 2NF
c) 3NF
d) Boyce-Codd Normal Form

Q10) Given the relation schema R(A,B,C,D) and functional dependencies

F ={AC, DB}. Which functional dependency causes a violation of second normal
form?
a) AC
b) DB
c) both AC and DB
d) Other Specify
 Q11) Given the relation schema R(A,B,C) and functional dependencies
F = {AB, BC, ACB}. What is the result of using the Relational database design
algorithm for producing a database schema which is dependency preserving and has the
lossless join property for relations in 3rd normal form?
a) R1(A,B), R2(B,C) and R3(A,C,B)
b) R1(A,B) and R2(A,C)
c) R1(A,B) and R2(B,C)
d) Other Specify

Q12)The highest normal form that a relation with no nontrivial functions dependencies can
be in is
a) 1NF
b) 2NF
c) 3NF
d) BCNF

FUNCTION DEPENDENCEY NORMALIZATION :

Q1) a) Let R(ABCDE) be a relation schema with two sets of functional dependencies.

F = {C  AB, AD  E, A  D} G = {C  ABD, AE  D, A  E} Determine

if F and G are equivalent. Show all work.

a) Let R be a relation schema defined as R(ABCDEFGH). A corresponding set of FDs is

defined as follows: J = {ABCD  EF, AC  E, DH  G, D  B, HB  E} Find
the minimal cover for J.

b) Suppose relation schema R contains Y attributes. Let X be a subset of attributes that are a
proper subset of Y. Assume we have the following definition: A set of attributes are limited
if X+  X and nothing else. Prove or disprove that the set of attributes X must be part of
the key for R.

c) Let R be a relation schema defined as R(ABCDEFGH). A corresponding set of FDs is

defined as follows G = {ABC  EH, F  E, D  BG, and A  CD}. Assume that R is
decomposed into W(ABCG), X(ADH), Y(ABF) and Z(BCE). Determine if this
decomposition is lossless. Show all work.

d) Let R be a relation schema defined as R(ABCDEFGH). A corresponding set of FDs is

defined as follows FDs = {A  DG, C  B, F  AH, and FGH  BE}. Suppose R is
decomposed into the following relations: R1(ABCD), R2(AFG), R3(BEF), R4(FGH).
Does this decomposition preserve dependencies?

***************************************************************************
Q2) Consider the relation schema EMP_DEPT in following Figure

and the following set G of functional dependencies on EMP_DEPT: G = {SSN ->{ENAME,

BDATE, ADDRESS, DNUMBER} , DNUMBER ->{DNAME, DMGRSSN} }.

A) Calculate the closures {SSN} + and {DNUMBER} + with respect to G.

******************************************************************************************************
Q3-A) F. Consider the following relation:
Employee (EmpID, Bdate, Dependent_name, Car_lic_tag#)
Assuming that Dependent-name and Car_lic_tag# are both multivalued, this relation is not in
1NF. Convert it into a set of 1NF relations. Show the keys in resulting relations clearly.

Q3-B) Consider the relation:

FLIGHT_RESERVATION (Flight#, Date, Cust_name, Plane_type, Seat#, Plane_capacity)

Assume that each reservation is for one customer and assigns a unique Seat# to the customer.

Flight# --> Plane_type

Plane_type --> Plane_capacity

Normalize this relation successively into 2NF and 3NF. Clearly show intermediate relations at
each level of normalization then state if the result in BCNF?

***************************************************************************

Q4- A) Consider the relational schema R(ABCDEFGH) with FDs

J = {AB  D, CE  H, CF  E, D  A, FC  G}
Assume that J is already a minimum cover. Find a decomposition of R which is lossless and
preserves dependencies such that the subschemas are in 3NF.

Q4-B) Consider the relational schema R(ABCDEFGH) with FDs

J = {AB  D, CE  H, CF  E, D  A, FC  G}
Using the "Paired Attribute" algorithm, find a lossless decomposition of R into subschemas that
are in BCNF. Determine if your solution preserves dependencies?

Q4-C) Consider the following two sets of functional dependencies F= {A ->C, AC ->D,
E ->AD, E ->H} and G = {A ->CD, E ->AH}. Check whether or not they are
equivalent.

Q4-D) Consider the universal relation R = {A, B, C, D, E, F, G, H, I} and the set of

functional dependencies F = { {A, B} -> {C}, {A} -> {D, E}, {B} -> {F}, {F} ->
{G, H}, {D} -> {I, J} }. What is the key for R? Decompose R into 2NF, then 3NF
relations.
 More Examples on Normalization

S1) Consider the following two sets of functional dependencies

F= {A ->C, AC ->D, E ->AD, E ->H} and G = {A ->CD, E ->AH}.
Check whether or not they are equivalent.

To show equivalence, we prove that G is covered by F and F is covered by G.

Proof that G is covered by F:
{A} + = {A, C, D} (with respect to F), which covers A ->CD in G
{E} + = {E, A, D, H, C} (with respect to F), which covers E ->AH in G

Proof that F is covered by G:

{A} + = {A, C, D} (with respect to G), which covers A ->C in F
{A, C} + = {A, C, D} (with respect to G), which covers AC ->D in F
{E} + = {E, A, H, C, D} (with respect to G), which covers E ->AD and E ->H in F
**********************************************************************

S2) Consider the universal relation R = {A, B, C, D, E, F, G, H, I} and the set of

functional dependencies
F = { {A, B} -> {C}, {A} -> {D, E}, {B} -> {F}, {F} -> {G, H}, {D} -> {I, J} }.
What is the key for R? Decompose R into 2NF, then 3NF relations.

Since the closure of{A, B},

{A, B}+ = R, one key of R is {A, B}
To normalize R intuitively into 2NF then 3NF, we take the following steps

1. First, identify partial dependencies that violate 2NF.

2. These are attributes that are functionally dependent on either parts of the key, {A}
or {B}, alone.
3. We can calculate the closures {A}+ and {B}+ to determine partially dependent
attributes:
{A}+ = {A, D, E, I, J}. Hence {A} -> {D, E, I, J} ({A} -> {A} is a trivial dependency)
{B}+ = {B, F, G, H}, hence {B} -> {F, G, H} ({B} -> {B} is a trivial dependency)

To normalize into 2NF, we remove the attributes that are functionally dependent on part of
the key (A or B) from R and place them in separate relations R1 and R2, and R3 below:

R1 = {A, D, E, I, J}, R2 = {B, F, G, H}, R3 = {A, B, C}

4. We look for transitive dependencies in R1, R2, R3. The relation R1 has the
transitive dependency {A} -> {D} -> {I, J}, so we remove the transitively dependent
attributes {I, J} from R1 into a relation R11 and copy the attribute D they are
dependent on into R11. The remaining attributes are kept in a relation R12. Hence,
R1 is decomposed into R11 and R12 as follows:
R11 = {D, I, J}, R12 = {A, D, E}
The relation R2 is similarly decomposed into R21 and R22 based on the transitive
dependency {B} -> {F} -> {G, H}:
R21 = {F, G, H}, R22 = {B, F}

The final set of relations in 3NF are { {D, I, J}, {A, D, E}, {F, G, H}, {B, F} {A, B, C}}
****************************************************************************
S3) Consider the universal relation R = {A, B, C, D, E, F, G, H, I} and the set of
functional dependencies
G = { {A, B} -> {C}, {B, D} -> {E, F}, {A, D} -> {G, H}, {A} -> {I}, {H} -> {J} }.

 {A}+ -> {A, I}, {B}+ -> {B}, {C}+ -> {C}, {D}+ -> {D}, {E}+ -> {E}, {F}+ -> {F},
{G}+ -> {G}, {H}+ -> {H, J}, {I}+ -> {I}, {J}+ -> {J}
Since none of the single attributes is a key, we next calculate the closures of pairs of
attributes that are possible keys:
{A, B}+ -> {A, B, C, I}, {B, D}+ -> {B, D, E, F}, {A, D}+ -> {A, D, G, H, I, J}
None of these pairs are keys either since none of the closures includes all attributes. But
the union of the three closures includes all the attributes:
{A, B, D}+ -> {A, B, C, D, E, F, G, H, I}
Hence, {A, B, D} is a key.

R = {A, B, D, C, E, F, G, H, I}
The first-level partial dependencies on the key (which violate 2NF) are:
{A, B} -> {C, I}, {B, D} -> {E, F}, {A, D}+ -> {G, H, I, J}

Hence, R is decomposed into R1, R2, R3, R4 :

R1 = {A, B, C, I}, R2 = {B, D, E, F}, R3 = {A, D, G, H, I, J}, R4 = {A, B, D}

Additional partial dependencies exist in R1 and R3 because {A} -> {I}. Hence, we remove
{I} into R5, so the following relations are the result of 2NF decomposition:
R1 = {A, B, C}, R2 = {B, D, E, F}, R3 = {A, D, G, H, J}, R4 = {A, B, D}, R5 = {A, I}

Next, we check for transitive dependencies in each of the relations (which violate 3NF).
Only R3 has a transitive dependency {A, D} -> {H} -> {J}, so it is decomposed into R31
and R32 as follows:
R31 = {H, J}, R32 = {A, D, G, H}
The final set of 3NF relations is {R1, R2, R31, R32, R4, R5}
*****************************************************************

S4) Given relation R(A,B,C,D,E) with dependencies

AB -> C
CD -> E
DE -> B
is AB a candidate key of this relation? If not, is ABD? Explain your answer.

No, AB+ = {A,B,C},a proper subset of {A,B,C,D,E} thus ABD+ = {A,B,C,D,E}

S5) Consider the following relation:

R (Doctor#, Patient#, Date, Diagnosis, Treat_code, Charge)

In this relation, a tuple describes a visit of a patient to a doctor along with a treatment code
and daily charge. Assume that diagnosis is determined (uniquely) for each patient by a
doctor. Assume that each treatment code has a fixed charge (regardless of patient). Is this
relation in 2NF? Justify your answer and decompose if necessary. Then argue whether
further normalization to 3NF is necessary, and if so, perform it.

From the question’s text, we can infer the following functional dependencies:

{Doctor#, Patient#, Date}{Diagnosis, Treat_code, Charge}

{Treat_code}{Charge}

Because there are no partial dependencies, the given relation is in 2NF already. This
however is not 3NF because the Charge is a nonkey attribute that is determined by another
nonkey attribute, Treat_code. We must decompose further:

R (Doctor#, Patient#, Date, Diagnosis, Treat_code)

R1 (Treat_code, Charge)

We could further infer that the treatment for a given diagnosis is functionally dependant,
but we should be sure to allow the doctor to have some flexibility when prescribing cures.