Normal forms formulas

Integrity constraints, functional dependencies and normal forms. 9 formulas for GATE DA Database Management and Warehousing, each with when to use it. Each is explained in the topic notes.

All 9 Normal forms formulas

ARMSTRONG'S AXIOMS (SOUND AND COMPLETE)

Reflexivity: Y \subseteq X \Rightarrow X \to Y Augmentation: X \to Y \Rightarrow X Z \to Y Z Transitivity: X \to Y, Y \to Z \Rightarrow X \to Z

Sound: they derive only FDs implied by F. Complete: they derive every FD in the closure F^+.

DERIVED RULES

Union: X \to Y, X \to Z \Rightarrow X \to Y Z Decomposition: X \to Y Z \Rightarrow X \to Y, X \to Z Pseudotransitivity: X \to Y, W Y \to Z \Rightarrow W X \to Z

All follow from the three axioms. Decomposition applies to the right side only; $X Y \to Z$ does not give $X \to Z$ .

ATTRIBUTE CLOSURE

X^{+} = {A ∣ X \to A is derivable from F}

Algorithm: start with result = X; repeatedly, for any FD $U \to V$ in F with $U \subseteq$ result, add $V$ ; stop when nothing is added.

MEMBERSHIP TEST AND SUPERKEY TEST

X \to Y \in F^{+} ⟺ Y \subseteq X^{+} X is a superkey of R ⟺ X^{+} = R

Use the closure algorithm for both. A candidate key is a minimal superkey: removing any attribute breaks $X^{+} = R$ .

COUNTING SUPERKEYS

One candidate key K, ∣ R ∣ = n : Keys K_{1}, K_{2} : 2^{n - ∣ K ∣} 2^{n - ∣ K_{1} ∣} + 2^{n - ∣ K_{2} ∣} - 2^{n - ∣ K_{1} \cup K_{2} ∣}

A superkey is any set containing at least one candidate key. For more keys, extend by inclusion and exclusion over unions of keys. Example: keys AB, BC, BD in R(A,B,C,D) give $3 \cdot 4 - 3 \cdot 2 + 1 = 7$ .

MAXIMUM NUMBER OF CANDIDATE KEYS

at most (⌊ n /2 ⌋ n) candidate keys for n attributes

No candidate key contains another, and this bound is reached (for example, when every set of $⌊ n /2 ⌋$ attributes is a key).

3NF AND BCNF CONDITIONS

3NF: BCNF: \forall X \to A non-trivial : X superkey \lor A prime \forall X \to A non-trivial : X superkey

For the relation R on which F is given, it is enough to test the FDs of F after splitting right sides into single attributes. For a part $R_{i}$ of a decomposition, test the FDs of $F^{+}$ that lie inside $R_{i}$ (the projection), not just those of F.

LOSSLESS-JOIN TEST FOR A BINARY DECOMPOSITION

R_{1} ⋈ R_{2} = R ⟺ (R_{1} \cap R_{2}) \to (R_{1} - R_{2}) or (R_{1} \cap R_{2}) \to (R_{2} - R_{1}) in F^{+}

Conditions: $R_{1} \cup R_{2} = R$ and F is the only set of constraints. The common attributes must be a superkey of at least one of the two parts. For more than two parts, use the tableau (chase) test.

DEPENDENCY PRESERVATION

(i ⋃ F_{i})^{+} = F^{+} where F_{i} = {X \to Y \in F^{+} ∣ X Y \subseteq R_{i}}

Practical test for each $X \to Y$ in F: set $Z = X$ , and repeat $Z \leftarrow Z \cup ((Z \cap R_{i})^{+} \cap R_{i})$ for every $R_{i}$ , with closures computed using F, until Z stops growing. The FD is preserved if $Y \subseteq Z$ .

Where this was asked: 2024 (1), 2025 (3), 2026 (2). See the 6 previous-year questions on Normal forms. This shows what was asked, not what will be asked.

KEEP GOING

Normal forms: the notes and 6 solved previous-year questions