• A simpler way to prove that an inference rule for functional

dependencies is valid is to prove it by using inference rules

• For example, we can prove IR4 through IR6 by using IR1

Slide 15- 22
Proof of IR4 (Using IR1 through IR3).
• IR4. (Decomposition) { X → YZ} ╞ X → Y

1. X→YZ (given).
2. YZ→Y (using IR1 and knowing that YZ ⊇ Y).
3. X→Y (using IR3 on 1 and 2).

Slide 15- 23
• Proof of IR5 (using IR1 through IR3): {X → Y, X → Z} |=X → YZ.

1. X →Y (given).
2. X → Z (given).
3. X → XY (using IR2 on 1 by augmenting with X; notice that XX = X).
4. XY → YZ (using IR2 on 2 by augmenting with Y).
5. X → YZ (using IR3 on 3 and 4).

Slide 15- 24
Proof of IR6 (using IR1 through IR3).
• IR6. (Psuedotransitivity) { X → Y, WY → Z} ╞ {WX → Z}

1. X→Y (given).
2. WY→Z (given).
3. WX→WY (using IR2 on 1 by augmenting with W).
4. WX→Z (using IR3 on 3 and 2).

Slide 15- 25
Exercise
Consider the following relation: R={A, C, D, E, H} and the
following set of FDs:
F={ A→C, AC→D, E→AB, E→H}.
Prove that:
1. F ╞ E→AH,
2. F ╞ A→D

Slide 15- 26
Definition
Let X be a set of attributes, and F be set of FDs.
The set X+ is the set of attributes that are functionally determined
by X based on F. X+ is called the closure of X under F.

Slide 15- 27
Example 4
F= { Ssn → { Ename, Bdate, Address, Dnumber} }

{Ssn}+ = { Ssn, Ename, Bdate, Address, Dnumber }

Slide 15- 28
Algorithm to determine Closure
Algorithm 15.1. Determining X+, the Closure of 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.

X+ := X;
repeat
oldX+ := X+;
for each FD Y → Z in F do
if X+  Y then X+ := X+  Z;
until (X+ = oldX+);

Slide 15- 29
• Algorithm 15.1 starts by setting X+ to all the attributes in X.
• By IR1, we know that all these attributes are functionally
dependent on X.
• Using inference rules IR3 and IR4, we add attributes to X+, using
each functional dependency in F.
• We keep going through all the dependencies in F (the repeat
loop) until no more attributes are added to X+ during a
complete cycle (of the for loop) through the dependencies in F.
• The closure concept is useful in understanding the meaning and
implications of attributes or sets of attributes in a relation.

Slide 15- 30
Example 5
• Consider the following relation schema about classes held at a
university in a given academic year.
CLASS ( Classid, Course#, Instr_name, Credit_hrs, Text, Publisher, Classroom, Capacity).
• Let F, the set of FDs for the above relation include the following :
FD1: Classid → Course#, Instr_name, Credit_hrs, Text, Publisher, Classroom,
Capacity;
FD2: Course# → Credit_hrs;
FD3: {Course#, Instr_name} → Text, Classroom;
FD4: Text → Publisher
FD5: Classroom → Capacity
These FDs above represent the meaning of the individual attributes
and the relationship among them and defines certain rules about the
classes.

Slide 15- 31
• Note that the above FDs express certain semantics about the data
in the relation CLASS.
• FD1 states that each class has a unique Classid.
• FD3 states that when a given course is offered by a certain
instructor, the text is fixed and the instructor teaches that class in
a fixed room.

Slide 15- 32
 { Classid } + = { Classid , Course#, Instr_name, Credit_hrs, Text,
Publisher, Classroom, Capacity } = CLASS
{ Course#} + = { Course#, Credit_hrs}
{ Course#, Instr_name } + = { Course#, Credit_hrs, Text, Publisher,
Classroom, Capacity }
• Note that each closure above has an interpretation that is revealing
about the attribute(s) on the left-hand-side.
• The closure of { Classid } + is the entire relation CLASS indicating
that all attributes of the relation can be determined from Classid
and hence it is a key.

Slide 15- 33
Example 6
PROJECT( SSN, PNUMBER, HOURS)
• From the semantics of the attributes :
F= {{Ssn, Pnumber } → Hours}

• Using the algorithm , we calculate the following closure sets with

Slide 15- 34
 15.1.2 Equivalence of Sets of FDs

Definition
• A set of FDs F is said to cover another set of FDs E if every FD in E is
also in F + ( E  F +) ; that is, if every dependency in E can be inferred
from F; alternatively, we can say that E is covered by F.

Definition
• Two sets of FDs E and F are equivalent if: E+ = F+
• Therefore, equivalence means that every FD in E can be inferred from
F, and every FD in F can be inferred from E; that is, E is equivalent to
F if E  F+ and F  E +.

Slide 15- 35
• We can determine whether F covers E as follows:
for each FD X → Y in E
1. calculating X+ with respect to F,
2. checking whether Y  X+
• If this is the case for every FD in E, then F covers E.

Slide 15- 36
Exercise
• Show that the following two sets of FDs are equivalent:
F ={A→C, AC→D, E→AD, E→H}
G ={A→CD, E→AH}

Slide 15- 37
 F ={A→C, AC→D, E→AD, E→H}
G ={A→CD, E→AH}
Abbreviated notation: w.r.t.
• G covers F:
A. Consider A→ C, A+ (w.r.t. G) ={ A, C , D }, CA  A+
B. Consider AC→ D, AC+ (w.r.t. G ) ={ A, C , D }, D  AC+
C. Consider E→ AD, E+ (w.r.t. G ) ={ E, A , H, C, D }, AD  E+
C. Consider E→ H, E+ (w.r.t. to G ) ={ E, A , H }, H  E+

• F covers G: left as exercise.

Slide 15- 38
15.1.3 Minimal Sets of FDs
Definition
• An attribute in a FD is considered an extraneous attribute if we
can remove it without changing the closure of the set of
dependencies.
• Formally, given F, the set of FDs, and an FD : X → A in F, attribute
Y is extraneous in X if Y ⊂ X, and F is equivalent to
(F − (X → A) ∪ { (X − Y) → A } ).

Slide 15- 39
• A set of FDs is minimal if it satisfies the following conditions:
(1) Every FD in F has a single attribute for its RHS.
(2) We cannot remove any FD from F and have a set of FDs that is
equivalent to F.
(3) We cannot replace any FD X → A in F with Y → A, where Y
proper-subset-of X and still have a set of dependencies that is
equivalent to F.

Slide 15- 40
• Condition 1 just represents every dependency in a canonical
form with a single attribute on the right-hand side .
• Conditions 2 and 3 ensure that there are no redundancies in
the dependencies either by having redundant attributes
(referred to as extraneous attributes) on the left-hand side of
a dependency (Condition 2) or by having a dependency that
can be inferred from the remaining FDs in F (Condition 3).

Slide 15- 41
• So, we can define a minimal cover of a set of FDs E as a
minimal set of dependencies (in the standard canonical form
and without redundancy) that is equivalent to E.
• We can always find at least one minimal cover F for any set of
dependencies E using Algorithm 15.2.

Slide 15- 42
• There can be several equivalent minimal sets

Slide 15- 43
Algorithm 15.2. find a minimal cover F for a Set of FDs E
1.Set F=E;
2.Replace each X→ {A1, A2,… An} in F by:
X→A1, X→A2, X→An
3. For each functional dependency 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 set F=(F-{ X→A}){( X-B)→A}
4. For each remaining functional dependency X → A in F
if {F − {X → A} } is equivalent to F,
then remove X → A from F.

Slide 15- 44
• Step 3 is equivalent to
For each functional dependency 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.

Slide 15- 45
Exercise
Let E = {B → A, D → A, AB → D}.
find a minimal cover of E?

Slide 15- 46
Example 7
Find a minimal cover for E = {B → A, D → A, AB → D}.

Slide 15- 47
Solution
• All dependencies are in canonical form (that is, they have only one
attribute on the right-hand side).
• In step 2 we need to determine if AB → D has any redundant
(extraneous) attribute on the left-hand side; that is, can it be
replaced by B → D or A → D?
• Since B → A, by (IR2), we have BB → AB, or B → AB
• Hence by the transitive rule (IR3), we get B → D.
• Thus AB → D may be replaced by B → D.
• We now have the set E′: {B → A, D → A, B → D}.
• In step 3 we look for a redundant FD in E′. By using the transitive rule
on B → D and D → A, we derive B → A. Hence B → A is redundant
can be eliminated.
• Therefore, the minimal cover of E is F: {B → D, D → A}.

Slide 15- 48
Exercise
Let R= {S , A, B, D, G, M, N} ,
F = { S → ABD, D →MG, M →N , D →N}
I) Find {S}+
II) Find a minimal cover for F

Slide 15- 49