Functional dependencies and closure

Why it exists

A key says that one set of attributes determines all the others. A functional dependency (FD) generalises this: one set of attributes determines some others, such as a course id determining the course title. FDs are the raw material of normalisation: they tell which facts are stored redundantly, which in turn causes anomalies. GATE asks for attribute closures, for implication between FDs, and for the keys and normal forms that follow (normal forms).

Prerequisites

You need relations, keys and the idea of legal instances (relational model and keys).

Precise definitions

Let $R$ be a relation schema with attribute sets $X, Y \subseteq R$. A relation instance $r$ satisfies the functional dependency $X \to Y$ if for any two tuples $t_1, t_2 \in r$:

$t_1[X] = t_2[X] \ \Longrightarrow\ t_1[Y] = t_2[Y].$

In words: tuples that agree on $X$ also agree on $Y$; the value of $X$ determines the value of $Y$. A dependency of the schema is a constraint: it must hold in every legal instance. From an instance one can only refute an FD (two tuples that agree on $X$ and differ on $Y$), never prove it.

• $X \to Y$ is trivial if $Y \subseteq X$ (it holds in every relation). Otherwise it is non-trivial.
• $X \to R$ says exactly that $X$ is a superkey: a key is a special case of an FD.
• For a set $F$ of FDs, the closure $F^+$ is the set of all FDs implied by $F$: those that hold in every relation that satisfies $F$. We write $F \models X \to Y$.

Armstrong's axioms (sound and complete for FDs):

1. Reflexivity: if $Y \subseteq X$ then $X \to Y$.
2. Augmentation: if $X \to Y$ then $XZ \to YZ$ for any $Z$.
3. Transitivity: if $X \to Y$ and $Y \to Z$ then $X \to Z$.

Sound means every FD derived this way really is implied; complete means every implied FD can be derived. Derived rules: union ($X \to Y$, $X \to Z$ give $X \to YZ$), decomposition ($X \to YZ$ gives $X \to Y$ and $X \to Z$), pseudotransitivity ($X \to Y$, $WY \to Z$ give $WX \to Z$).

How it works

The closure of a set of attributes

The closure $X^+$ (with respect to $F$) is the set of all attributes $A$ with $F \models X \to A$. It is computed by a simple loop:

1. start with $\text{result} = X$;
2. while some dependency $L \to M$ of $F$ has $L \subseteq \text{result}$ and $M \not\subseteq \text{result}$: add $M$ to the result;
3. stop when nothing can be added.

Then $F \models X \to Y$ exactly when $Y \subseteq X^+$. For $R(A, B, C, D, E)$ with $F = \{A \to B,\ BC \to E,\ DE \to A\}$:

$AC^+ = ABCE$: $A \to B$ adds $B$, then $BC \to E$ adds $E$; $DE \to A$ needs $D$. So $AC \to BE$ is implied, but $AC$ is not a superkey. $CD^+ = CD$: nothing fires. $CDE^+ = ABCDE$: $DE \to A$ adds $A$, $A \to B$ adds $B$, so $CDE$ is a superkey.

Why the loop is correct. Each attribute added is derived from $X$ by Armstrong's rules (soundness). Conversely, if $A \notin X^+$, the relation with two tuples that agree exactly on $X^+$ and differ everywhere else satisfies $F$ (any dependency whose left side lies inside $X^+$ has its right side inside $X^+$ too) and violates $X \to A$: so $A$ is not implied (completeness). This construction was run by program: the closure agrees with semantic implication on all relations over a small domain.

Testing an FD and comparing sets of FDs

• Does $F$ imply $X \to Y$? Compute $X^+$ and check $Y \subseteq X^+$.
• Are two sets $F$ and $G$ equivalent ($F^+ = G^+$)? Check that every FD of $F$ is implied by $G$ and every FD of $G$ is implied by $F$ (compute closures with respect to the other set).
• Is a single FD redundant in $F$? Remove it and test whether it is still implied by the rest.

For example $\{A \to B,\ B \to C,\ A \to C\}$ is equivalent to $\{A \to B,\ B \to C\}$: the third dependency follows by transitivity.

How large can $F^+$ be

$F^+$ can be much larger than $F$. From $F = \{A \to B_1, A \to B_2, \ldots, A \to B_m\}$ follows $A \to Y$ for every subset $Y$ of $\{B_1, \ldots, B_m\}$: $2^m$ dependencies with left side $A$ alone (counted by program for $m \le 5$). That is why algorithms work with closures of attribute sets and with small covers, never with $F^+$ itself.

Dependencies in an instance

For the instance $R(A, B, C)$ = {(1, x, p), (2, x, p), (3, y, q), (4, y, q)} the single-attribute FDs that hold are $A \to B$, $A \to C$, $B \to C$ and $C \to B$ (computed by testing each pair). $B \to A$ and $C \to A$ fail ($B = x$ occurs with $A = 1$ and $A = 2$). Remember: that these hold in the instance does not make them constraints of the schema; the designer decides from the meaning of the data.

Worked examples

Cheat box

Traps and GATE patterns

Connections

Closures give the candidate keys (finding candidate keys), which in turn define the normal forms (normal forms); minimal covers are treated further on the page for decomposition (lossless join and dependency preservation).

PYQs

In the context of schema normalization in relational
DBMS, consider a set F of functional dependencies. The
set of all functional dependencies implied by F is called
the closure of F. To compute the closure of F,
Armstrong's Axioms can be applied. Consider X, Y, and
Z as sets of attributes over a relational schema. The three
rules of Armstrong's axioms are described as follows.

Reflexivity: If Y ⊆ X, then X → Y
Augmentation: If X → Y, then XZ → YZ for any Z
Transitivity: If X → Y and Y → Z, then X → Z

The additional rule of Union is defined as follows.

Union: If X → Y and X → Z, then X → YZ

It can be proved that the additional rule of Union is also
implied by the three rules of Armstrong's Axioms.
Listed below are four combinations of these three rules.
Which one of these combinations is both necessary and
sufficient for the proof?

Let P, Q, R and S be the attributes of a relation in a
relational schema. Let X → Y indicate functional
dependency in the context of a relational database, where
X, Y ⊆ {P, Q, R, S}.

Which of the following options is/are always true?

The symbol → indicates functional dependency in the
context of a relational database. Which of the following
options is/are TRUE?

A functional dependency F: X→Y is termed as a useful
fimctional dependency if and only if it satisfies all the
following three conditions:
 X is not the empty set.
 Y is not the empty set.
 Intersection of X and Y is the empty set.

For a relation R with 4 attributes, the total number of
possible useful functional dependencies is ____

Suppose the following functional dependencies hold on a
relation U with attributes P, Q R, S, and T:

P → QR

RS → T

Which of the following functional dependencies can be
inferred from the above functional dependencies?

Consider the relation X(P, Q, R, S, T, U) with the
following set of functional dependencies
F = {{P, R} → {S, T}
{P, S, U} → {Q, R}}
Which of the following is the trivial functional
dependency in F+ is closure of F?

The following functional dependencies are given:

AB → CD
AF → D
DE → F
C → G
F → E
G → A

Which one of the following options is false?

In a schema with attributes A, B, C, D and E following set
of functional dependencies are given

A → B A → C CD → E B → D E → A

Which of the following functional dependencies is NOT
implied by the above set?

The following functional dependencies hold for
relations R(A, B, C) and S(B, D, E):

B -> A , A -> C

The relation R contains 200 tuples and the relation S
contains 100 tuples. What is the maximum number of
tuples possible in the natural join of R and S (R ⋈S) ?

Self-check

Revision card

References