Closure of FDs F+

 If F is a set of functional dependencies then

the closure of F denoted as F+, is the set of
all functional dependencies logically
implied by F.
 F+ is the set of all FDs deduced from F by
applying the inference rules (Armstrong’s
Axioms)
Armstrong’s Axioms
Armstrong’s Axioms
 Armstrong's Axioms are a set of rules (rules of
inference), that when applied repeatedly, generate a
closure of functional dependencies.
 They were developed by William W. Armstrong and
others (Armstrong, Nakamura and Rudnicki, 2003)
 The axioms must be sound and complete set of
inference rules
 These rules are sound because they generate only FDs
that actual hold on R (only correct FDs).
 They are also complete as they generate all FDs (of F+)
of R that hold.
A1: Reflexive rule
 If X is a set of attributes and Y is a subset of X then X
determines Y
 If Y ⊆ X, then X→Y Such FDs are called trivial FDs
 Given a relation Schema R(A,B,C,D)
 Given AB ⊆ AB then ABAB is a trivial dependency
 Given A ⊆ AB then AB A is a trivial dependency
 Given B ⊆ AB then AB B is a trivial dependency
 Trivial dependency − If a functional dependency (FD) X
→ Y holds, where Y is a subset of X, then it is called a trivial
FD. Trivial FDs always hold.
 Non-trivial dependency − If an FD X → Y holds, where Y
is not a subset of X, then it is called a non-trivial FD.
 Given a relation Schema R(A,B,C,D)
 If 𝑩 ⊄ A then AB is a non-trivial dependency
A2: Augmentation rule
 If a → b holds and y is attribute set, then ay → by also
holds.
 That is adding attributes in dependencies, does not
change the basic dependencies.
 Also known as a Partial dependency
 If X Y, then XZ  YZ for any Z
 XZ Y is a partial dependency
 Y is partially dependent on XZ
 Y is not fully dependent on XY because ∃ 𝑋 ⊂ 𝑋𝑍 𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 𝑋 →Y
 XZ Z; is a partial dependency,
 Z is partially dependent on XZ
 ∃ 𝑍 ⊂ 𝑋𝑍 𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 𝑍 →Z
 XZZ is a trivial dependency
A3:Transitivity rule
 If a → b holds and b → c holds, then a → c also holds.
 Given a relation Schema R(A,B,C,D) and a set of FDs
F= {ABC, CD)
 D is transitively dependent on AB
ADDITIONAL RULES
Union Rule
Decomposition Rule
Pseudo-Transitivity Rule
UNION RULE
 Union Rule
 If XY and X Z then X  YZ
If X determines Y and X
determines Z then X must also
determines Y and Z.
DECOMPOSITION RULE
 Decomposition Rule
 IF XYZ then X Y and X Z
 If X determines Y and Z, then X
determines Y and X determines Z
separately. This is the reverse of Union. If
you have a table that appears to contain
two entities that are determined by the
same PK, consider breaking them up into
two tables.
PSEUDO-TRANSITIVITY RULE
 Pseudo-Transitivity Rule
 if XY holds, and aYZ holds, then
XaZ holds.
Exercise
Use Armstrong's Axioms to prove the
following rules
 Union Rule
 Decomposition Rule
 Pseudo-Transitivity Rule
Proof Union Rule
 If X → Y and X → Z then X → Y Z.
 Proof:
1. X → Y , Given
2. X → Z, Given
3. XX → XZ  X → XZ, Augment 2 by X
4. XZ → YZ, Augment 1 by Z
5. If X → XZ and XZ → YZ then X → YZ, Transitivity
using 3 and 4
Proof Decomposition Rule
 If X → YZ then X → Y and X → Z
 Proof:
1. X → YZ, Given
2. YZ → Y , Reflexivity
3. If X → YZ and YZ → Y then X → Y , Transitivity
on 1 and 2.
Similar proof for X → Z.
Proof Pseudo-transitivity Rule
 if XY holds, and aYZ holds, then XaZ holds
 Proof:
1. X → Y, Given
2. aYZ , Given
3. XaYa; Augment 1 by a
4. If Xa→ Ya and Ya → Z then Xa → Z , Transitivity on
2 and 3.
Exercise
Given R(A,B,C) and F={AB, BC}
Apply Armstrong’s axioms to determine
non-trivial FDs in F+
Attribute Closure
Closure of a Attribute Sets
 To test whether a set of attributes or
attribute is a super key, we need to find
the set of all attributes functionally
determined by that attribute
 Given a set of the attribute(s) A and a set of
FDs F that hold on R, the closure of A
denoted A+ is the set of all attributes that
are functionally determined by A under F
Algorithm to compute A+

result ← A;
while (result changes) do
for each functional dependency B → C in F
if B is contained in result then result ←
result  C;
end;
A+ ← result;
Uses of Attribute closure
 Testing for super key: To check if the
attribute(s) closure A+ contains all
attributes of R
 Testing functional dependencies: To
check if a functional dependency X→Y
holds (or, in other words, is in F+), just
check if Y⊆X+
Exercise:
If R(ABCDEF) is given and a set F =
{ABC, ADE, BD, AFB} holds.
a) Determine the closure of all the
determinants
b) Find any 3 super keys of R
c) Find a candidate key of R
Exercise
Given relation R(A,B,C,D,E,F) and a set
of FDs F that hold on R:
F= {A → B, A → C, CD → E, CD → F, B
→E}
a. Show that ADF is a super key
b. Determine if ADF is a candidate key
Exercise
Consider a relation R(A,B,C,D,E)
with set of Functional Dependencies
(FDs) F ={AB, BCE, EDA}
Determine
Two Candidate keys of R
Redundant FDs
Redundant FDs
A functional dependency in the set
is redundant if it can be derived
from the other functional
dependencies in the set.
 Apply Armstrong’s axioms to remove
redundant FDs
Steps for determining redundant
FDs.
 Step 1: Start with a set of S of functional dependencies
(FDs).
 Step 2: Remove an FD f and create a set of FDs S' = S -
f.
 Step 3: Test whether f can be derived from the FDs
in S'; by using the set of Armstrong's axioms and
derived rules.
 Step 4: If f can be so derived, it is redundant , and
hence S' = S. Otherwise replace f into S'; so that
now S' = S + f.
 Step 5: Repeat steps 2 to 4 for all FDs in S.
Example
Given that the set of FDs F= {AB, B
C, A C }
hold on R(ABC). Show that A C is a
redundant.
 F- {AC} = {AB, B C} =S
 AC transitively dependent on A
Example
Given that the set of FDs F holds on R(A, B, X, Y, Z).
Show that ZB Y is a redundant FD in F
F= {ZA, B X, AX Y, ZB Y}
F- ZB Y = {ZA, B X, AX Y} =S
 Z  A by augmentation rule will yield ZB  AB.
 B  X and AX  Y by the pseudo-transitivity rule
will yield AB  Y.
 ZB AB and AB  Y by transitivity rule will yield
ZBY.
 F+ = S+
Membership Algorithm for
determining redundant FDs.
Input: Set F of FDs that hold for R
1. Choose an FD f(X Y) and remove it from F such that F’ =
F-f
2. result ← X;
3. for each FD, A → B, remaining in the reduced set of FDs F’
Do
If A ⊆ result
then result = result B
endif
4. if Y ⊆ result
then the FD X → Y is redundant.
endif
Exercise
1. Given that the set of FDs F = {AB, B C, A C } holds on R(ABC).
Use the Membership algorithm to remove redundant FDs in F
2. Given that the set of FDs F = {ZA, BX, AXY, ZBY}
holds on R(ABXYZ). Use the Membership algorithm to
remove redundant FDs in F
3. A relational schema R(ABCDE) is given and a set of functional
dependencies F = {A  B, C  D, BD  E, AC  E} holds on R.
Use the Membership algorithm to show that AC E is redundant
FDs in F
4. Given relation R(A, B, C, D, E, F) and a set of FDs F that holds on R.
F = {AB, A C, A F, EC, EF, BF, CD E, CDF}
a) Find the closure of CD
b) Find any two super keys of R
c) Determine candidate key for R.
Canonical Cover
Canonical Cover of F
 A canonical cover of F is a “minimal” set of functional
dependencies equivalent to F, having no redundant
dependencies or redundant parts of dependencies
 There may be further redundancy in a set of FDs in the
form of redundant attributes in the determinants of
the FDs.
 If we also remove such attributes we arrive at what is
called a minimal cover for the set of FDs.
 The minimal cover must also have the property of
having single attributes on the right hand side of all
FDs in the set.
Canonical cover ctd
The minimal cover for a set of FDs F is the set of FDs
G such that:
 G+ = F+ (that is G and F are equivalent)
 the right hand side of each FD in G is a single
attribute
 G is minimal, that is, if we remove any attribute
from an FD in G or remove any FD from G, then G+
will no longer equal F
Minimal Set of Functional
Dependencies
A set of FDs, F, is said to be minimal if it satisfies these
three conditions
1. the right side of every FD in F has a single attribute.
This form is called standard or canonical form for
FDs.
2. no attribute on the left side of any FD in F is
extraneous. This means that if X → Y is an FD in F
then there is no proper subset S of X such that S → Y
can be used in place of X → Y and the resulting set is
equivalent to F.
3. F has no redundant FDs.
Examples
 Given F = {A → B, AB → C }
 F is canonical RHD single attributes
 B is extraneous in AB → C because
{A → B, AB → C} logically implies A → C
(i.e. the result of dropping B from
AB → C)
 F becomes {AB, AC}
Examples
 Given F = {A → C, AB → CD}
 F is not canonical,
 By decomposition rule AB CD  AB C,
AB D
 F becomes {A → C, AB C, AB D}
 ABC is redundant
 F becomes {A → C, AB D}
Exercise
Consider following set F of functional dependencies on
schema R(A, B, C) and compute the minimal cover for F = {A
 BC, B  C, A  B, AB  C}
 Canonical form
F={AB, AC, BC, AB, ABC}
 Remove extraneous FDs from LHS
F={AB, AC, BC, AB, ABC}
ABC; B is extraneous because AB
F becomes F={AB, AC, BC, AB}
 Remove redundant FDs
F={AB, AC, BC, AB}
 Minimal cover
F={AB, BC}
Exercise
Consider relation R(ABCDE) with the following set of FDs
F={AC → B, CE → D, C → E, D → B } and compute the
minimal cover of F.
 Express F in canonical form
F={AC → B, CE → D, C → E, D → B }
 Remove extraneous attributes LHS
F={AC → B, CE → D, C → E, D → B }
F={AC → B, C → D, C → E, D → B }
 Remove redundant FDs
F={AC → B; C → D; C → E; D → B }
 Minimal cover F={C → D, C → E, D → B }
Exercise
Given R(A, B, C) and F = {A → BC, B → C, A → B, AB →
C} that hold on R. Find the minimal cover of F
1. F= {A → B, AC, B → C, A → B, AB → C}  {A →
B, AC, B → C, AB → C}
2. A is extraneous in AB → C, B → C is already present
Now, F = {A → B, AC, B → C}
3. AC is redundant, A → C is logically implied by A
→ B and B C transitively. Or use attribute closure
 The minimal set is: {A → B, B → C}