1

Lesson 5
Database design: Bottom-up Approach
Part 1: Functional Dependency

2
Learning objective
•Upon completion of this lesson, students will be able to:
1. Recall the concept of functional dependency, Armstrong's axioms
and secondary rules
2. Identify closure of a FD set, closure of a set of attributes
3. Find a minimal key of a relation under a set of FDs
4. Identify the equivalence of sets of FDs and find the minimal cover of
a set of FDs
Outline
1. Functional Dependency
2. Armstrong's Axioms and secondary rules
3. Closure of a FD set, closure of a set of attributes
4. A minimal key
5. Equivalence of sets of FDs
6. Minimal Sets of FDs
1. Functional Dependency
• 1.1. Introduction
• 1.2. Definition

5
1.1. Introduction
• We have to deal with the problem of database design
• anomalies, redundancies
• The most important concepts in relational schema design theory

6
1.2. Definition

• Suppose that R = {A1, A2, ... , An} , X and Y are non-empty subsets of R.
• A functional dependency (FD), denoted by X → Y, specifies a constraint on
the possible tuples that can form a relation state r of R. The constraint is
that, for any two tuples t1 and t2 in r that have t1[X] = t2[X], they must also
have t1[Y] = t2[Y].
• X: the left-hand side of the FD
• Y: the right-hand side of the FD

7
1.2. Definition

• This means that the values of the X component of a tuple

uniquely
(or functionally) determine the values of the Y component.
• A FD X → Y is trivial if X Y
• If X is a candidate key of R, then X → R

8
1.2. Definition
• Examples
• AB  C A B C D
a1 b1 c1 d1
a1 b1 c1 d2
a1 b2 c2 d1 subject
a2 b1 c3 d1

• subject_id  name,
• subject_id  credit,
• subject_id  percentage_final_exam,
• subject_id  {name, credit}

9
2. Armstrong's axioms
2.1. Armstrong's axioms
2.2. Secondary rules
2.3. An example

10
2.1. Armstrong's axioms

• Given
• R = {A1, A2, ... , An}, X, Y, Z, W are subsets of R.
• XY denoted for XY
• Reflexivity
• If Y  X then XY
• Augmentation
• If XY then XZYZ
• Transitivity
• If XY, YZ then XZ

11
2.2. Secondary rules
• Union
• If XY, XZ then XYZ.
• Pseudo-transitivity
• If XY, WYZ then XWZ.
• Decomposition
• If XY, Z  Y then XZ

12
2.3. An example
• Given a set of FDs: F = {AB  C, C  A}
• Prove: BC  ABC
• From C  A, we have BC  AB (Augmentation)
• From AB  C, we have AB  ABC (Augmentation)
• And we can conclude BC  ABC (Transitivity)

13
3. Closure of a FD set, closure of a set of
attributes
3.1. Closure of a FD set
3.2. Closure of a set of attributes
3.3. A problem

14
3.1. Closure of a FD set

• Suppose that F = {A  B, B  C} on R(A, B, C,…). We can infer many

FDs such as:
A  C, AC  BC,…
• Definition
• Formally, the set of all dependencies that include F as well as all
dependencies
that can be inferred from F is called the closure of F, denoted by F+.
•F X  Y to denote that the FD X  Y is inferred from the set of FDs F.

15
3.2. Closure of a set of attributes
• Problem
• We have F, and X  Y, we have to check if F X  Y or not

• Should we calculate F+?  Closure of a set of attributes

• Definition
• For each such set of attributes X, we determine the set X+ of attributes
that are functionally determined by X based on F; X+ is called the
closure of X under F.

16
3.2. Closure of a set of attributes

• To find the closure of an attribute set X+ under F

• Input: A set F of FDs on a relation schema R, and a set of attributes X,
which is a subset of R.
X0 := X;
repeat
for each functional dependency Y  Z in F do
if Xi-1 Y then Xi := Xi-1 Z;
else Xi := Xi-1
until (Xi unchanged);
X+ := Xi

17
3.2. Closure of a set of attributes
• An example
• Given R = {A, B, C, D, E, F} and F = {AB  C, BC  AD, D  E, CF  B}.
Calculate (AB)+F
• X0 = AB
• X1 = ABC (from AB  C)
• X2 = ABCD (from BC  AD)
• X3 = ABCDE (from D  E)
• X4 = ABCDE
• (AB)+F=ABCDE

18
3.3. A Problem
• X  Y can be inferred from F if and only if YX+F
• F X  Y  YX+F
• An example
• Let R = {A, B, C, D, E}, F = {A  B, B  CD, AB  CE}.
Consider whether or not F AC
• (A)+F = ABCDE  {C}

19
4. Minimal key
4.1. Definition
4.2. An algorithm to find a minimal key
4.3. An example

20
4.1. Definition

• Minimal key
• Given R = {A1, A2, ... , An}, a set of FDs F
• K is considered as a minimal key of R if:
• K R

• K→R F+

• Với K’ K, thì K’→R F+

• K+= R and K\{Ai} →R F+

21
4.2. An algorithm to find a minimal key

• To find a minimal key

• Input: R = {A1, A2, ... , An}, a set of FDs F

- Step0 K0= R
- Stepi If (Ki-1\{Ai})→R then Ki= Ki-1\ {Ai}
else Ki= Ki-1
- Stepn+1 K = Kn

22
4.3. An example
• Given R = {A, B, C, D, E}, F = {AB  C, AC  B, BC  DE}.
• Find a minimal key
• Step0: K0= R = ABCDE
• Step1: Check if or not (K0\{A})  R (i.e, BCDE  R).
• (BCDE)+= BCDE ≠ R. Vậy K1 = K0 = ABCDE
• Step2: Check if or not (K1\{B})  R (i.e, ACDE  R).
• (ACDE)+ = ABCDE = R. So, K2 = K1\{B} = ACDE
• Step3: K3 = ACDE
• Step4: K4 = ACE
• Step5: K5 = AC
• We infer that AC is a minimal key

23
4.4. An other algorithm to find a minimal
key
Input: U = {A1, A2, …, An} , F
Output: a minimal key
• Step 1:
VT = set of all attributes on the left-side of FD in F X = U \ VP: set of attributes that must be in K
VP = set of all attributes on the right-side of FD in F Y = VP \ VT: set of attributes that must NOT be in K
Z = VP  VT: set of attrbutes that may be in K

• Step 2: If (X)+ = U then X is the minimal key: K = X. End!

• Step 3: If (X)+ ≠ U then
- K0 = X  Z
- Repeat: check if we can remove any attribute from Z (similar to slide 22)
- K = Ki

24
5. Equivalence of Sets of FDs
5.1. Definition
5.2. An example

25
5.1. Definition

• Definition:
• A set of FDs F is said to cover another set of FDs G if every FD in G is
also
in F+ (every dependency in G can be inferred from F).
• Check if F and G are equivalent:
• Two sets of FDs F and G are equivalent if F+ = G+.
• Therefore, equivalence means that every FD in G can be inferred from F,
and every FD in F can be inferred from G;
• That is, G is equivalent to F if both the conditions - G covers F and F
covers G - hold.

26
5.2. An example
• Prove that F = {A → C, AC → D, E → AD, E → H} and G = {A → CD, E →
AH} are equivalent
• For each FD of F, prove that it is in G+
• A → C: (A)+G = ACD  C, so A → C  G+
• AC → D: (AC)+G = ACD  D, so AC → D  G+
• E → AD: (E)+G = EAHCD  AD, so E → AD  G+
• E → H: (E)+G = EAHCD  H, so E → H  G+
• F+  G+
• For each FD of G, prove that it is in F+ (the same)
• G+  F+
•  F+ = G +

27
6. A minimal cover of a set of FDs
6.1. Definition
6.2. An algorithm to find a minimal cover of a set of FDs
6.3. An example

28
6.1. Definition
• Minimal Sets of FDs
• A set of FDs F to be minimal if it satisfies:
• Every dependency in F has a single attribute for its right-hand side.
• We cannot replace any dependency X → A in F with a dependency Y → A,
where Y is a proper subset of X, and still have a set of dependencies that
is equivalent to F.
• We cannot remove any dependency from F and still have a set of
dependencies that is equivalent to F.
• A set of dependencies in a standard or canonical form and with no
redundancies

29
6.2. An algorithm to find a minimal cover of a
set of FDs
• Finding a Minimal Cover F for a Set of FDs G
• Input: A set of FDs G.
• 1. Set F := G.
• 2. Replace each functional dependency X → {A1, A2, ..., An} in F by the n
FDs X →A1, X →A2, ..., X → An.
• 3. For each FD X → A in F
• for each attribute B that is an element of X
• if {{F – {X → A}} ∪ {(X – {B}) → A}} is equivalent to F
• then replace X → A with (X – {B}) → A in F.
• 4. For each remaining functional dependency X → A in F
• if {F – {X → A}} is equivalent to F, then remove X → A from F.

30
6.3. An example
• G = {B → A, D → A, AB → D}.
• We have to find the minimal cover of G.
• All above dependencies are in canonical form
• In step 2, we need to determine if AB → D has any redundant attribute
• on the left-hand side; that is, can it be replaced by B → D or A → D?
• Since B → A then AB → D may be replaced by B → D.
• We now have a set equivalent to original G, say G1: {B → A, D → A, B → D}.
• In step 3, we look for a redundant FD in G1. Using the transitive rule on
• B → D and D → A, we conclude B → A is redundant.
• Therefore, the minimal cover of G is {B → D, D → A}

31
Remark
• Functional dependencies
• Armstrong axioms and their secondary rules
• Closure of a set of FDs
• Closure of a set of attributes under a set of FDs
• An algorithm to find a minimal key
• Equivalence of sets of FDs
• Finding a minimal set of a set of FDs

32
Summary
1. Functional Dependency
• A FD X → Y: the values of the X component of a tuple uniquely (or functionally) dete
rmine the values of the Y component
2. Armstrong 's Axioms and secondary rules
• Reflexivity, Augmentation, Transitivity
• Union, Pseudo-transitivity, Decomposition
3. Closure of a FD set, closure of a set of attributes
• All dependencies that can be inferred from F, include F, is called the closure of F, den
oted by F+
• A set of attributes are functionally determined by X based on F
4. A minimal key
• A minimal set of attributes can determine R
5. Equivalence of sets of functional dependencies
• F is equivalent to G if every dependency in G can be inferred from F, and every depen
dency in F can be inferred from G
6. A minimal cover of a set of FDs
• A set of dependencies in a standard or canonical form and with no redundancies

33
Thank you for
your attention!

34
References
• Raghu Ramakrishnan and Johannes Gehrke, Database
Management Systems, 3rd edition, Mc Graw Hill, 2003.
• Elmasri and Navathe, Fundamentals of Database Systems, 6th
edition, Addison-Wesley, 2011.

35