Applied Class 10: Normalisation, BCNF Decomposition and 3NF Synthesis

exercises
tutorial
databases
normalisation
bcnf
3nf
minimal-cover

Practice for 2026-05-04-normalisation-and-relational-database-schema-design. Note: “consider the FDs in the order provided” is a default guideline — only FDs that actually violate BCNF get split on; other correct decompositions can exist depending on split order.

Two things to have at hand before starting Section A:

Section A — BCNF decomposition (top-down)

Question A.1

R [A, B, C, D, E] with {A} → {C}, {A, B} → {D, E}. Decompose into BCNF.

{A,B}⁺ = {A,B,C,D,E} — {A, B} is the only candidate key.

{A} → {C} violates BCNF (A isn’t a superkey) → split into R1 [A, C] and R2 [A, B, D, E]. Within R2, {A,B} is a key (it already was for the whole relation), so {A,B} → {D,E} doesn’t violate BCNF there — no further splitting needed.

Final answer: R1 [A, C] ({A}→{C}), R2 [A, B, D, E] ({A,B}→{D,E}).

Question A.2

R [A, B, C, D, E] with {A} → {B}, {C} → {D, E}. Decompose into BCNF.

{A,C}⁺ = {A,B,C,D,E} — {A, C} is the only candidate key.

{A} → {B} violates BCNF (A alone isn’t a superkey) → split into R1 [A, B] and R2 [A, C, D, E]. In R2, {C} → {D, E} violates BCNF (C alone isn’t a superkey for R2) → split into R3 [C, D, E] and R4 [A, C].

Final answer: R1 [A, B], R3 [C, D, E], R4 [A, C] (no non-trivial FD).

Figure 1: The decomposition tree for A.2 — and, as it turns out, for A.4 as well. Each split is labelled with the FD that violated BCNF; the leaves are the answer. Each split puts X ∪ Y on the left and Q − Y on the right. Nothing hangs on the order — it is the set of leaves that is the decomposition.

Question A.3

R [A, B, C, D, E, F] with {A} → {B, C}, {C} → {D, E}, {E} → {F}. Decompose into BCNF.

{A}⁺ = {A,B,C,D,E,F} — A is the only candidate key. A → {B, C} does not violate BCNF here, since A is the key — so we skip it and look for an FD whose LHS genuinely isn’t a superkey.

{C} → {D, E} violates BCNF (C isn’t a superkey) → split into R1 [C, D, E] and R2 [A, B, C, F]. Within R2, the explicit FDs don’t obviously violate BCNF — but the implicit FD C → F (derivable transitively via C → E and E → F) does (C isn’t a superkey for R2 either) → split R2 into R3 [C, F] and R4 [A, B, C].

Final answer: R1 [C, D, E] ({C}→{D,E}), R3 [C, F] ({C}→{F}, implicit), R4 [A, B, C] ({A}→{B,C}).

Note: {E} → {F} is lost by this decomposition — E and F never end up together in any final relation, so that FD can no longer be checked directly against the decomposed schema.

Figure 2: A.3’s tree. The second split is driven by an FD that was never written down: C → F follows from C → E and E → F, and C is not a superkey of R2, so R2 is not in BCNF even though none of the three given FDs says so. Miss it and you stop with R2 [A, B, C, F] wrongly declared finished. Each split puts X ∪ Y on the left.

Question A.4

R [A, B, C, D, E] with {A} → {B}, {C} → {D, E}, {A, D, E} → {C}, {B, C} → {A}. Decompose into BCNF.

{A, C}, {A, D, E} and {B, C} are all candidate keys.

{A} → {B} violates BCNF → split into R1 [A, B] and R2 [A, C, D, E]. Within R2, {C} → {D, E} violates BCNF → split into R3 [C, D, E] and R4 [A, C].

Final answer: R1 [A, B], R3 [C, D, E], R4 [A, C] — the exact same result as Question A.2, splitting on the same two FDs in the same order, so Figure 1 is A.4’s tree unchanged, even though A.4 started with twice as many FDs. {A, D, E} → {C} and {B, C} → {A} are both lost in this decomposition (their attributes never all end up together in one final relation) — this is worth noticing: extra FDs don’t necessarily survive decomposition, and a differently-ordered decomposition might have preserved different (but not necessarily more) FDs.

Section B — 3NF synthesis (bottom-up)

Question B.1

R [A, B, C, D, E, F, G, H] with {A, B} → {C}, {C, D} → {E}, {D} → {F, G}. Synthesise into 3NF.

{A,B,D,H}⁺ = {A,B,C,D,E,F,G,H} — the only candidate key. Prime attributes: A, B, D, H. (H appears on no side of any FD, so it must be in every key; dropping any of A, B or D loses C or E.)

This FD set is already a minimal cover. Step 1 splits {D}→{F,G} into {D}→F and {D}→G; step 2 finds nothing to drop from either compound LHS ({A}⁺ = {A} and {B}⁺ = {B} both miss C; {C}⁺ = {C} and {D}⁺ = {D,F,G} both miss E); step 3 finds no FD implied by the others.

Synthesis: R1 [A, B, C] ({A,B}→C), R2 [C, D, E] ({C,D}→E), R3 [D, F, G] ({D}→{F,G}), and — since the candidate key {A,B,D,H} isn’t contained in any of these — R4 [A, B, D, H] (no non-trivial FD). All four are in 3NF.

Question B.2

R [A, B, C, D, E, F] with {A, B} → {C}, {C} → {D, E}. Synthesise into 3NF.

{A,B,F}⁺ = {A,B,C,D,E,F} — the only candidate key. Prime attributes: A, B, F. Already a minimal cover.

Synthesis: R1 [A, B, C] ({A,B}→C), R2 [C, D, E] ({C}→{D,E}), R3 [A, B, F] (no non-trivial FD, added since the key isn’t otherwise present). All three are in 3NF.

Question B.3

R [A, B, C, D, E] with {A} → {D, E}, {D} → {A}, {B} → {C}, {B, C} → {A, D}, {E, A} → {D}. Synthesise into 3NF.

{B}⁺ = {A,B,C,D,E} — {B} is the only candidate key. Prime attributes: B.

Minimal cover, step by step:

Step 1: RHS split Step 2: LHS simplify Step 3: delete redundant
{A} → D {A} → D {A} → D
{A} → E {A} → E {A} → E
{B,C} → A {B} → A — C redundant, since B → C {B} → A
{B,C} → D {B} → D — same reason dropped — {B} → A then {A} → D
{D} → A {D} → A {D} → A
{E,A} → D {A} → D — E redundant, A alone reaches D dropped — now a duplicate of {A} → D
{B} → C {B} → C {B} → C

leaving {A} → {D, E}, {B} → {A, C}, {D} → {A}.

Synthesis: one relation per FD gives [A, D, E], [A, B, C] and [A, D]; the last is a subset of the first, so it is eliminated and {D} → {A} rides along inside R1. The candidate key {B} is already present in R2, so no extra all-prime-attributes relation is needed.

R1 [A, D, E] ({A}→{D,E}, {D}→{A}), R2 [A, B, C] ({B}→{A,C}). Both are in 3NF.

Question B.4

R [A, B, C, D, E, F] with {A} → {B, C, D, E, F}, {B, C} → {A}, {D, E} → {B}, {C} → {D}. Synthesise into 3NF.

{A}, {B, C} and {C, E} are all candidate keys. Prime attributes: A, B, C, E.

Minimal cover, step by step. Only step 1 and step 3 do anything: neither compound LHS can be shortened ({B}⁺ = {B} and {C}⁺ = {C,D} both miss A; {D}⁺ = {D} and {E}⁺ = {E} both miss B).

Step 1: RHS split Step 2: LHS simplify Step 3: delete redundant
{A} → B {A} → B dropped — A → D, A → E, then {D,E} → B
{A} → C {A} → C {A} → C
{A} → D {A} → D dropped — A → C, then {C} → D
{A} → E {A} → E {A} → E
{A} → F {A} → F {A} → F
{B,C} → A {B,C} → A {B,C} → A
{D,E} → B {D,E} → B {D,E} → B
{C} → D {C} → D {C} → D

leaving {A} → {C, E, F}, {B, C} → {A}, {D, E} → {B}, {C} → {D}. Neither removal is visible from a single FD — both take the closure test, and both survive in either order.

Synthesis: R1 [A, C, E, F] ({A}→{C,E,F}), R2 [B, C, A] ({B,C}→{A}), R3 [D, E, B] ({D,E}→{B}), R4 [C, D] ({C}→{D}). The candidate key {A} is already present in R1, so no extra relation is needed. All four are in 3NF.