Functional Dependencies, Closure and Canonical Cover: short notes (Database Management Systems)

Introduction

A functional dependency (FD) $X \to Y$ says that the values of attributes $X$ determine the values of attributes $Y$ : two tuples that agree on $X$ must agree on $Y$ . FDs are how the real-world rules of an application ("a roll number determines the student's name", "a course and a semester determine the instructor") are written down for a relation.

FDs drive the rest of database design. Keys are defined through them, the later FD-based tests for 2NF, 3NF and BCNF are conditions on them, and lossless decomposition is tested with them. The three computations that the later notes rely on are taught here: attribute closure, implication of an FD, and the canonical (minimal) cover.

Prerequisites

Relational Model and Keys: superkey and candidate key, which are re-expressed through closure.

Core concepts

Definition. For attribute sets $X, Y \subseteq R$ , relation instance $r$ satisfies $X \to Y$ if for all tuples $t_1, t_2 \in r$ , $t_1[X] = t_2[X]$ implies $t_1[Y] = t_2[Y]$ . The FD holds on schema $R$ if every legal instance satisfies it. As with keys, an instance can refute an FD but never prove it.

Term	Meaning
Trivial FD	$X \to Y$ with $Y \subseteq X$ ; satisfied by every instance
$F^+$ (closure of $F$ )	all FDs logically implied by the set $F$
$X^+$ (attribute closure)	all attributes $A$ with $X \to A$ in $F^+$
Superkey	$X$ with $X^+ = R$
Equivalent sets	$F$ and $G$ with $F^+ = G^+$
Extraneous attribute	an attribute that can be removed from a left or right side without changing $F^+$

Armstrong's axioms

For attribute sets $X, Y, Z, W$ :

Reflexivity. If $Y \subseteq X$ then $X \to Y$ .
Augmentation. If $X \to Y$ then $XZ \to YZ$ .
Transitivity. If $X \to Y$ and $Y \to Z$ then $X \to Z$ .

They are sound (they derive only FDs that hold) and complete (they derive every FD in $F^+$ ). Derived rules:

Union. $X \to Y$ and $X \to Z$ give $X \to YZ$ .
Decomposition. $X \to YZ$ gives $X \to Y$ and $X \to Z$ .
Pseudotransitivity. $X \to Y$ and $WY \to Z$ give $WX \to Z$ .

Not a rule. $XY \to Z$ does not give $X \to Z$ , and $X \to Z$ with $Y \to Z$ does not give anything about $X$ and $Y$ together beyond $XY \to Z$ .

How it works: attribute closure

To compute $X^+$ , start from $X$ and repeatedly apply any FD whose left side is already inside the current set, adding its right side, until a full pass adds nothing.

Trace of computing the closure of AB under BE to G, D to E, AB to C, C to D, G to A: pass 1 adds C then D, pass 2 adds E, pass 3 adds G, pass 4 adds nothing, giving ABCDEG — Figure 1. Closure of $AB$ under $F = \{BE \to G, D \to E, AB \to C, C \to D, G \to A\}$ , scanning the FDs in the listed order: four passes, result $ABCDEG$ , so $AB$ is a superkey.

Algorithms and pseudocode

Text

CLOSURE(X, F)
  result <- X
  repeat
      changed <- false
      for each FD (L -> R) in F
          if L is a subset of result and R is not a subset of result then
              result <- result union R; changed <- true
  until not changed
  return result

Each pass costs $O(|F| \cdot |R|)$ set operations, and there are at most $|R|$ productive passes, so the simple algorithm is $O(|F| \cdot |R|^2)$ ; a counter-based version runs in time linear in the total size of $F$ .

Uses: $X \to Y$ is in $F^+$ iff $Y \subseteq X^+$ ; $X$ is a superkey iff $X^+ = R$ ; $F$ and $G$ are equivalent iff every FD of $G$ follows from $F$ and every FD of $F$ follows from $G$ .

Text

CANONICAL-COVER(F)
  replace each FD X -> A1...Ak by X -> A1, ..., X -> Ak      // single attribute right sides
  for each FD X -> A and each attribute B in X               // left-reduce
      if A is in CLOSURE(X - {B}, F) then replace X by X - {B}
  for each FD f in F                                          // remove redundant FDs
      if f follows from F - {f} then delete f
  return F    (optionally merge FDs with equal left sides by union)

The left-reduction test uses the original $F$ : $B$ is extraneous in $X \to A$ when $A \in (X - \{B\})^+$ computed under $F$ . Left-reduce before removing redundant FDs; doing it the other way round can leave a redundant FD behind.

Mathematical explanation

Why closure is correct. Every attribute added is justified by transitivity and union from FDs already derived, so the algorithm is sound. For completeness, build a two-tuple instance that agrees exactly on $X^+$ and differs elsewhere: it satisfies every FD of $F$ (any FD whose left side is inside $X^+$ has its right side inside $X^+$ , by the stopping condition), yet violates $X \to A$ for every $A \notin X^+$ . So no attribute outside $X^+$ is implied.

Counting trivial FDs. On $n$ attributes, choosing $Y \subseteq X \subseteq R$ means deciding for each attribute whether it is in $Y$ , in $X$ only, or in neither: $3^n$ trivial FDs (empty sets allowed). The total number of FDs $X \to Y$ is $2^n \cdot 2^n = 4^n$ .

A canonical cover is not unique. $F = \{A \to B, B \to C, C \to A, A \to C, C \to B, B \to A\}$ has the two canonical covers $\{A \to B, B \to C, C \to A\}$ and $\{A \to C, C \to B, B \to A\}$ ; both are minimal and both are equivalent to $F$ .

Worked examples

Example 1: closure and keys. With $F$ of Figure 1 on $R(A, B, C, D, E, G)$ :

$(AB)^+ = ABCDEG$ , so $AB$ is a superkey; neither $A^+ = A$ nor $B^+ = B$ is $R$ , so $AB$ is a candidate key.
$D^+ = DE$ , so $D \to A$ does not hold.
$B$ appears on no right side, so $B$ is in every key. Trying $B$ with each other attribute: $AB$ , $BC$ , $BD$ , $BE$ , $BG$ all have closure $R$ . The candidate keys are exactly these five.

Example 2: canonical cover. $F = \{A \to BC, B \to C, AB \to D, AD \to C\}$ .

Split: $A \to B, A \to C, B \to C, AB \to D, AD \to C$ .
Left-reduce $AB \to D$ : $A^+ = ABCD$ contains $D$ , so $B$ is extraneous: $A \to D$ . Left-reduce $AD \to C$ : $A^+$ contains $C$ , so $D$ is extraneous: $A \to C$ , a duplicate.
Remove redundant FDs: $A \to C$ follows from $A \to B$ and $B \to C$ .

Canonical cover: $\{A \to B, B \to C, A \to D\}$ , or merged, $\{A \to BD, B \to C\}$ .

Example 3: equivalence. $F = \{A \to B, AB \to C, C \to D\}$ and $G = \{A \to BC, C \to D, A \to D\}$ are equivalent: under $F$ , $A^+ = ABCD$ covers $A \to BC$ and $A \to D$ ; under $G$ , $A^+ = ABCD$ covers $A \to B$ and $AB \to C$ . $H = \{A \to B, B \to C, C \to D\}$ is not equivalent to $F$ : $B \to C$ does not follow from $F$ , because $B^+ = B$ under $F$ .

Example 4: does an instance satisfy an FD? Instance of $R(A, B, C)$ : $(1, x, p)$ , $(1, x, q)$ , $(2, y, p)$ , $(3, y, p)$ . Holds: $A \to B$ (the two tuples with $A = 1$ both have $x$ ), $B \to A$ ? No: $y$ appears with 2 and 3. $C \to B$ ? No: $p$ appears with $x$ and $y$ . $AC \to B$ : yes. $B \to C$ : no.

Example 5: minimal covers can differ in size. Take the $F$ of the non-uniqueness remark in the Mathematical explanation: every pair of $A$ , $B$ , $C$ determines each other in both directions, so $A^+ = B^+ = C^+ = ABC$ . A minimal cover here is any set of single-attribute FDs, with no redundant FD, under which all three attributes reach each other. Checking every candidate set gives exactly five:

two cycles with 3 FDs: $\{A \to B, B \to C, C \to A\}$ and $\{A \to C, C \to B, B \to A\}$ ;
three stars with 4 FDs, one centred on each attribute, for example $\{A \to B, B \to A, B \to C, C \to B\}$ centred on $B$ .

In a star no FD is redundant: dropping $B \to A$ leaves nothing that reaches $A$ . So "the number of FDs in a minimal cover" is not determined by $F$ ; a question that asks for it has to fix the procedure or the starting order.

Example 6: counting the FDs in $F^+$ . $R(A, B, C)$ , $F = \{A \to B, B \to C\}$ . For a left side $X$ , the FDs $X \to Y$ in $F^+$ are exactly those with $Y \subseteq X^+$ , so there are $2^{|X^+|}$ of them (the empty $Y$ included).

$X$	$\emptyset$	$A$	$B$	$C$	$AB$	$AC$	$BC$	$ABC$
$X^+$	$\emptyset$	$ABC$	$BC$	$C$	$ABC$	$ABC$	$BC$	$ABC$
$2^{\lvert X^+ \rvert}$	1	8	4	2	8	8	4	8

Total with empty sets allowed: $43$ ; with a nonempty left side: $42$ .
Trivial FDs ( $Y \subseteq X$ ): $\sum_X 2^{|X|} = 3^3 = 27$ . Nontrivial ( $Y \not\subseteq X$ ): $43 - 27 = 16$ .

State which convention you use: whether the empty set may appear on either side, and whether trivial FDs are counted.

Important properties and observations

Right sides split, left sides do not. $X \to YZ$ is equivalent to the pair $X \to Y$ , $X \to Z$ ; $XY\to Z$ does not in general imply $X\to Z$ or $Y\to Z$ . A left-side attribute may be removed only when the extraneous-attribute closure test succeeds.
Every FD with a superkey on the left holds. Superkeys are exactly the left sides whose closure is $R$ ; candidate keys are inclusion-minimal such sets.
Order of canonical-cover steps matters: left-reduce first, then remove redundant FDs.
Extraneous on the right: after splitting into single attributes, an extraneous right-side attribute shows up as a redundant FD.
FD versus relation property. An FD $X \to Y$ on $R$ says $\pi_{XY}(r)$ is the graph of a function from $X$ -values to $Y$ -values (see Relations).

Common misconceptions.

" $AB \to C$ implies $A \to C$ ." It does not.
"The canonical cover is unique." Several are possible; all are equivalent.
"An instance that satisfies $X \to Y$ proves the FD." It only fails to refute it.

GATE examination perspective

Closure computations. Compute $X^+$ , decide whether an FD is implied, decide whether a set is a key.
Candidate keys from FDs. Core attributes (on no right side) plus minimal extensions.
Canonical cover. Count the FDs in a minimal cover, or pick which set is a minimal cover of $F$ .
Equivalence of FD sets. Check each direction with closures.
Instance questions. Which FDs a given table satisfies.

Summary

Relational Model and Keys: prerequisite; keys re-expressed through closure.
Relations: related; an FD makes a projection a function.
Normal Forms: 1NF, 2NF, 3NF and BCNF: dependent; the 2NF, 3NF and BCNF tests here are FD-based.

Functional Dependencies, Closure and Canonical Cover

Introduction

Prerequisites

Core concepts

Armstrong's axioms

How it works: attribute closure

Algorithms and pseudocode

Mathematical explanation

Worked examples

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

Armstrong's axioms

How it works: attribute closure

Algorithms and pseudocode

Mathematical explanation

Worked examples

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps