CHAPTER 3 QUESTIONS:

COMPLEXITY LEVEL:HIGH -> H

Mid->M

Easy-> E

[Link] the universal relation R = {A, B, C, D, E, F, G, H, I, J} and the set of functional

dependencies FX = { {A, B}→{C}, {A}→{D, E}, {B}→{F}, {F}→{G, H}, {D}→{I, J} }. What is the key
for R? Decompose R into 2NF and then 3NF relations. [H]

SOLUTION:

Step 1: Universal Relation and FDs

We have:

 Relation R = {A, B, C, D, E, F, G, H, I, J}

 Functional Dependencies (FDs):

1. {A, B} → {C}

2. {A} → {D, E}

3. {B} → {F}

4. {F} → {G, H}

5. {D} → {I, J}

Step 2: Find the Key

We need the closure of attributes to see what determines all of R.

 Start with {A, B}:

o {A, B}+ = {A, B}

o From FD1: {C} → add C

o From FD2: {D, E} → add D, E

o From FD3: {F} → add F

o From FD4: {G, H} → add G, H

o From FD5: {I, J} → add I, J

So {A, B}+ = {A, B, C, D, E, F, G, H, I, J} = all attributes.

Therefore, {A, B} is a candidate key.

No smaller subset works (A alone or B alone doesn’t cover everything).

Key = {A, B}

Step 3: Decompose into 2NF

 Recall: 2NF removes partial dependencies (non-prime attributes depending on part

of a composite key).

 Key = {A, B}, so partial dependencies are:

o A → D, E

o B→F

Decomposition:

1. R1(A, D, E)

2. R2(B, F)

3. R3(A, B, C) (to preserve {A, B} → C)

4. Plus dependencies from F → G, H and D → I, J:

o R4(F, G, H)

o R5(D, I, J)

Now all relations are in 2NF.

Step 4: Decompose into 3NF

 Recall: 3NF removes transitive dependencies (non-prime → non-prime).

 Check each relation:

1. R1(A, D, E):

o A → D, E (A is part of key in original, fine).

o D → I, J is separate, already handled in R5.

2. R2(B, F):

o B → F, fine.

3. R3(A, B, C):

o {A, B} → C, fine.

4. R4(F, G, H):

o F → G, H, fine.

5. R5(D, I, J):
 o D → I, J, fine.

All relations are now in 3NF.

Final Answer

 Key for R: {A, B}

 2NF Decomposition:

o R1(A, D, E)

o R2(B, F)

o R3(A, B, C)

o R4(F, G, H)

o R5(D, I, J)

 3NF Decomposition: Same as above (already satisfies 3NF).

Q2. Let the set of functional dependencies, FX = {A→C, E→F, E→AD} and GX = {A→CD,
E→AF}. Are FX and GX equivalent? [M]

Let’s carefully check whether FX and GX are equivalent sets of functional dependencies.

Step 1: Given Sets

 FX = { A → C, E → F, E → AD }

 GX = { A → CD, E → AF }

Step 2: Expand FX

From FX:

1. A → C

2. E → F

3. E → AD (means E → A and E → D)

So FX implies:

 A→C

 E→F

 E→A

 E→D
Now, since E → A and A → C, by transitivity: E → C So FX also implies E → A, C, D, F.

Step 3: Expand GX

From GX:

1. A → CD (means A → C and A → D)

2. E → AF (means E → A and E → F)

So GX implies:

 A→C

 A→D

 E→A

 E→F

Now, since A → C and E → A, by transitivity:

E → C And since A → D and E → A: E → D

So GX also implies E → A, C, D, F.

Step 4: Compare

 FX gives: A → C, E → A, E → D, E → F, E → C

 GX gives: A → C, A → D, E → A, E → F, E → C, E → D

Both sets generate the same closure of dependencies.

Final Answer

Yes, FX and GX are equivalent because they imply the same set of functional dependencies.

Q3. Consider a relation R = (A, B, C, D, E) with the dependencies X = {AB→C, CD→E, DE→B}.
Is AB a candidate key of this relation? If not, is ABD? Explain your answer. [M]

SOLUTION:

Relation and FDs

 Relation R = (A, B, C, D, E)

 Functional Dependencies (FDs):

1. AB → C

2. CD → E

3. DE → B
Step 1: Test if AB is a Candidate Key

Compute closure of {A, B}:

 Start: {A, B}

 From AB → C ⇒ add C → {A, B, C}

 Now we have {A, B, C}, but:

o CD → E requires D (not present).

o DE → B requires D and E (not present).

So {A, B}+ = {A, B, C}. Not all attributes are covered. AB is NOT a candidate key.

Step 2: Test if ABD is a Candidate Key

Compute closure of {A, B, D}:

 Start: {A, B, D}

 From AB → C ⇒ add C → {A, B, C, D}

 From CD → E ⇒ add E → {A, B, C, D, E}

 From DE → B ⇒ B already present.

So {A, B, D}+ = {A, B, C, D, E} = all attributes. ABD is a candidate key.

Final Answer

 AB is not a candidate key (its closure misses D and E).

 ABD is a candidate key because its closure covers the entire relation R.

CONSIDER THE FOLLOWING SET Y of functional dependencies on the relational schema

R(A,B,C,D,E,F,G,H):AB->CD, D->C,DE->B,DEH->AB,AC->DC

i) Find all the candidate keys for R.

ii) Compute the canonical cover for Y. Explain each step in derivation.

Solution:

Given

 Relation R(A, B, C, D, E, F, G, H)

 Functional Dependencies Y:

1. AB → CD

2. D → C
 3. DE → B

4. DEH → AB

5. AC → DC

i) Candidate Keys for R

Step 1: Attribute closures

 Start with DEH:

o DEH → AB

o So DEH+ = {D, E, H, A, B}

o From AB → CD ⇒ add C, D (already there)

o From D → C ⇒ C already there

o From DE → B ⇒ B already there

o From AC → DC ⇒ C already there

o Altogether: {A, B, C, D, E, H}

o Missing F, G.

So DEH+ = {A, B, C, D, E, H}. Not full relation.

 Try DEHF:

o DEHF+ = {D, E, H, F}

o From DEH → AB ⇒ add A, B

o From AB → CD ⇒ add C, D

o From D → C ⇒ C already there

o From DE → B ⇒ B already there

o From AC → DC ⇒ C already there

o Now we have {A, B, C, D, E, F, H}.

o Still missing G.

 Try DEHFG:

o DEHFG+ = {D, E, H, F, G}

o From DEH → AB ⇒ add A, B

 o From AB → CD ⇒ add C, D

o From D → C ⇒ C already there

o From DE → B ⇒ B already there

o From AC → DC ⇒ C already there

o Now we have {A, B, C, D, E, F, G, H} = all attributes.

Candidate Key = {D, E, H, F, G}

ii) Canonical Cover for Y

Step 1: Break RHS into single attributes

 AB → C

 AB → D

 D→C

 DE → B

 DEH → A

 DEH → B

 AC → D

 AC → C

Step 2: Remove redundant attributes from LHS

 Check AB → D:

o Since D → C, AB → D may be redundant. But AB → D is needed to derive D

directly.

 Check AC → C: trivial (C → C), so remove.

 Check DEH → B: already implied by DE → B, so redundant.

Step 3: Simplify

Canonical cover becomes:

 AB → C

 AB → D

 D→C

 DE → B
  DEH → A

 AC → D

Step 4: Group by common LHS

 AB → CD

 D→C

 DE → B

 DEH → A

 AC → D

Canonical Cover F c = { AB → CD, D → C, DE → B, DEH → A, AC → D }

Final Answer

1. Candidate Key(s): {D, E, H, F, G}

2. Canonical Cover: { AB → CD, D → C, DE → B, DEH → A, AC → D }

Problem Set: Candidate Keys & Canonical Cover[M]

Problem 1

Relation: R(A, B, C, D, E) FDs: { AB → C, C → D, D → E }

1. Find all candidate keys.

2. Compute the canonical cover.

Problem 2

Relation: R(P, Q, R, S, T) FDs: { PQ → R, R → S, S → T, T → Q }

1. Determine candidate keys.

2. Simplify into canonical cover.

Problem 3

Relation: R(A, B, C, D, E, F) FDs: { A → BC, C → D, DE → F, F → A }

1. Identify candidate keys.

2. Derive canonical cover step by step.

Problem 4

Relation: R(X, Y, Z, W) FDs: { XY → Z, Z → W, W → Y }

1. Is XY a candidate key?
 2. Find all candidate keys.

3. Compute canonical cover.

Problem 5 (Challenge)

Relation: R(A, B, C, D, E, F, G, H) FDs: { AB → CD, D → C, DE → B, DEH → AB, AC → DC }

1. Find all candidate keys.

2. Compute canonical cover.

[Link] two set of functional dependencies.

X={A->B,C->D,AB->E,E->F}

Y={A->B,C->D,A->E,AC->F}

i)Does X covers Y.

ii)Are X and Y equivalent? Explain.

Q. Problem 2

Given:

 X = { P → Q, Q → R, PR → S }

 Y = { P → QR, PR → S }

i) Check if X covers Y. ii) Determine whether X and Y are equivalent.

Q. Problem 3

Relation R(U, V, W, X, Y) with:

 X = { UV → W, W → X, U → Y }

 Y = { UV → WX, U → Y }

i) Does X cover Y? ii) Are X and Y equivalent?

[Link] 4

Consider:

 X = { A → B, B → C, C → D, AD → E }

 Y = { A → BC, C → D, AD → E }

i) Does X cover Y? ii) Are X and Y equivalent?

Q. Problem 5 (Challenge)

Relation R(A, B, C, D, E, F):

 X = { AB → C, C → D, D → E, E → F }

 Y = { AB → CDE, E → F }

i) Does X cover Y? ii) Are X and Y equivalent? Justify with closure computations.

[Link] a relation R(B, C, D, E, F, G, H, I), where each attribute is atomic, and the
following set of functional dependencies exits:

DI H, BCD, CDGI, FB, GFH

 Write the Candidate Key(s)

 Find out highest normal form.[M]

SOLUTION: Consider a relation R(B, C, D, E, F, G, H, I), where each attribute is atomic,

and the following set of functional dependencies exits:

DI H, B CD, C DGI, F B, G FH

• Write the Candidate Key(s)

• Find out highest normal form

Candidate keys (all minimal) are:

• {B, E}

• {C, E}

• {F, E}

• {G, E}

It is not in 2NF.

Reason: 2NF prohibits a partial dependency of a non-prime attribute on part of a

candidate key.

Take candidate key {B,E}:

the FD B → D exists and D is non-prime (D is not in any candidate key).

That is a partial dependency (B is a proper subset of key {B,E}) → violates 2NF.

(Similarly C→I etc. produce partial dependencies relative to candidate key {C,E}.)

Hence the given relation is in 1NF.

Q. Problem 1
Relation R(A, B, C, D, E, F) with FDs:

 A → BC

 C→D

 DE → F

 F→A

1. Find all candidate keys.

2. Determine the highest normal form satisfied by R.

Q. Problem 2

Relation R(P, Q, R, S, T, U) with FDs:

 PQ → R

 R→S

 S→T

 TU → Q

1. Identify candidate keys.

2. State the highest normal form.

Q. Problem 3

Relation R(X, Y, Z, W, V) with FDs:

 XY → Z

 Z→W

 W→Y

 V→X

1. Find candidate keys.

2. Check the highest normal form.

Q. Problem 4

Relation R(M, N, O, P, Q, R) with FDs:

 M→N

 N→O

 OP → Q
 Q→R

1. Compute candidate keys.

2. Determine the highest normal form.

Problem 5 (Challenge)

Relation R(A, B, C, D, E, F, G, H) with FDs:

 AB → CD

 D→C

 DE → B

 DEH → AB

 AC → DC

1. Find all candidate keys.

2. Compute the highest normal form satisfied by R.

Q. Analyze the relation schema R(A,B,C,D,E) with the following set of functional
dependencies: F={A→BC, CD→E, B→D, E→A} }

i. Identify all candidate keys of relation R and Determine the prime attributes.

ii. Test whether R is in 2NF, 3NF, and BCNF for each FD. For each failure, identify which
FD(s) cause it and why.

iii. State the highest normal form satisfied by R, with justification.[END SEM QUESTION]

Solution:
Q. Consider the relational schema R(P, Q, R, S) with the functional dependencies F = {P
→ QR, Q → R, P → Q, PQ → R }.

Find the canonical cover Fc (the minimal set of functional dependencies). [END SEM
QUESTION]

SOLUTION:

Canonical cover for F Given F={ P→QR, Q→R, P→Q, PQ→R }

Step 1 — Split RHS into single attributes F1={ P→Q, P→R, Q→R, PQ→R }. Step 2 —
Remove extraneous attributes from left sides All left sides are single attributes except
PQ→R .

After this step we have (no change needed for single-LHS FDs): F2={ P→Q, P→R, Q→R }
Step 3 — Remove redundant dependencies .

Step 4 — Combine (if possible) Combine FDs with same LHS: none to combine beyond
P→Q (only one for P) and Q→R.

Final canonical cover Fc={ P→Q, Q→R }