Functional Dependencies

FUNCTIONAL DEPENDENCY AND
NORMALIZATION
FUNCTIONAL DEPENDENCY
 Definition: Let α с(subset) R, β с (subset) R. The functional
dependency α →β holds on R if in any legal relation r(R) for all
pairs of tuples t1 and t2 in r such that t1[α]=t2[α], it is also the
case that t1[β]=t2[β].
 Alternatively, the value of α-component of a tuple can uniquely

determine the value of β-component.
 FD is basically a many-to-one relationship from one set of

attributes to another.
Note: с denotes subset

FUNCTIONAL DEPENDENCY
 The left side of FD is determinant and the right side is

dependent.
 FD is a property of relation schema(or intension), not a

particular legal relation state(or extension).
 It can be defined explicitly by someone who knows the

semantics of the attributes of R.
EXAMPLE
 R=(a, b, c, d) and r(R) is a legal relation as follows:
A B C D
A1 B1 C1 D1
A1 B2 C1 D2
A2 B2 C2 D2
A2 B3 C2 D3
A3 B3 C2 D4
 In the above example

 A→C holds, but C → A does not hold.
 AB→ D holds.
EXAMPLES OF FDS
FDs of Branch_name(branch-name, b_city, assets)
 Branch-name→ b_city
 Branch-name→ assets
FDs of Loan-schema(branch-name, loan-number, amount)

 Loan-number → amount
 Loan-number →branch-name
FDs of Customer(C-ID, cust-name, cust-city)

 C-ID→ cust-name
 C-ID→ cust-city
EXAMPLE
SCP
Supplier_number City Product_number Quantity
S1 Kolkata P1 100
S2 Mumbai P1 80
S3 Mumbai P2 150
S4 Kolkata P1 110
S5 Kolkata P3 50
What are the FDs of the above relation?:

Supplier_number → city
{Supplier_number, product_number }→ quantity

PICTORIAL REPRESENTATION
 EMP_PROJECT( SSN, PNO, HOURS, ENAME, PNAME,
PLOCATION) is the relation-schema.
 SSN, PNO, HOURS, ENAME, PNAME, PLOCATION
 The left hand side attributes of the FD s are connected by vertical lines to
the horizontal line representing the FD, while the right –hand-side attributes
are connected by arrow pointing toward the attributes.
TRIVIAL & NON-TRIVIAL DEPENDENCY
 Trivial dependency: FD is trivial if and only if the right side is a
subset(not necessarily a proper subset) of the left side. Otherwise FD is
non-trivial.
 A trivial dependency cannot possibly fail to satisfy(because A→A is

satisfied by all relations). It is satisfied by all instances of a relation.
Trivial dependency is not interesting in practice.
 Example: Supplier(Supplier_number, product_number,city)

Trivial dependency:
 {Supplier_number, product_number }→ Supplier_number
Non-trivial dependency:
 Supplier_number → city
INFERENCE RULES
 Schema designer specifies the FD that are semantically obvious.
 However other FDs hold in all legal relation instances that satisfy the
dependencies in F. Those dependencies can be deduced or inferred from
the FDs in F. The set of all such dependencies is called the closure of F
and is denoted by F+.
 An FD a→b is inferred from a set of dependencies F specify on R if

a→b holds in every relation state r that is a legal extension in F.
INFERENCE RULE
 Relation schema R(A, B, C, G, H,I)
 The set of FDs: F={A→B, A→C, CG→H, CG→I and
B→H}
 The FD A→H is logically implied.
 Proof: Given that A→B , if t1[A]=t2[A]

then t1[B]=t2[B]
Now, B→ H if t1[B]=t2[B]
then t1[H]=t2[H]
It is shown that whenevert1 and t2 are tuples such that t1[A]=t2[A]
it must be that t1[H]=t2[H]. Hence,
A→H
DETERMINATION OF F+
 We can find all of F+ from F by applying Axioms or rules of inference for
functional dependencies repeatedly. These inference rules are called
Armstrong’s axioms.
 Reflexivity: If α is a set of attributes and β с α then α→β holds.
 Augmentation: If α→β holds and γ is a set of attributes then γα→

γβ holds.
 Transitivity: If α→β holds and β→γ holds then α→γ.
Note: с denotes subset

DETERMINATION OF F+
 Several additional rules can be designed from the previous rules:
 Union rule: If α→β holds and α→γ holds then α→ γβ holds.

 Decomposition: If α→βγ holds then α→β and α→γ holds.
 Pseudo transitivity: If α→β holds and γβ→δ holds, then
αγ→δ holds
 Self-determination: α→ α
 Composition: If α→β, γ →δ holds, then αγ→δβ holds
EXAMPLE
 Let us consider a relation schema R=(A,B,C, G, H, I) and the set of FDs
{A→B, A→C, CG→H, CG→I, B→H}, list the several members of F+.
 Given A→B, B→H : By transitivity rule : A→H

 Given CG→H, CG→I : By union rule : CG→HI
 Given A→C, CG→H : By pseudo transitivity rule : AG→H
 Given A→C, CG→I : By pseudo transitivity rule : AG→I
 Deduced AG→H, AG→I : By union rule : AG→HI
 F+ ={ A→B, A→C, A→H

CG→H, CG→I, CG→HI
AG→I , AG→H, AG→HI
B→H }
We can further deduce more FDs in F+.
EXAMPLE
R(A,B,C,D,E,F) and FDS are:
F={A→BC, B→E, CD→EF}
Calculate the closure of F.
Given, A→BC
 By decomposition: A→B, A→C
 By augmentation: AD → CD
Given, CD→EF and deduced AD→CD

 By transitivity: AD→EF
Deduced A→B, given B→E

 By transitivity: A→E
ARMSTRONG AXIOMS ARE SOUND AND
COMPLETE
 Armstrong axioms(Reflexivity, Augmentation and transitivity rules) are
sound and complete.
 By sound means: Any dependency that we can infer from a given set of
dependencies F on a relation schema R using Armstrong axioms satisfies
the dependencies in F and every state of relation R.
 By complete means: All possible number of FDs can be formed by

using the Armstrong axioms repeatedly.
CLOSURE OF ATTRIBUTES
 Definition: Given a set of attributes a, define the closure of a under F
(denoted by a+ ) as the set of attributes that are functionally determined
by a under F:
a →  is in F+    a+
 For a given relation R and a set of FDs , suppose Z is a set of attributes

in R. We can determine the set of all attributes of R that are functionally
determined by Z by computing Z+.
 Algorithm for determining the closure of A:
 result:= A
while(changes to result)
for each functional dependency X→Y in F do
begin
if (X is a subset of result) then
result=result U Y;
end
 Relation schema R(A, B, C, G, H,I)
 The set of FDs: F={A→B, A→C, CG→H, CG→I and
B→H}
 Calculate closure of AG(AG+).
Solution:
1. result = AG
2. result = ABG (A → B )
3. result = ABCG (A → C )
4. result = ABCGH (CG → H and CG  AGBC)
5. result = ABCGHI (CG → I and CG  AGBCH)
EXAMPLE
 F={ssn→ename,
pnumber→{pname, plocation}
{ssn, pnumber}→hours}
 Compute ssn+, pnumber+, {ssn, pnumber}+
Solution:
 ssn+={ssn, ename}
 pnumber+={pnumber, pname, plocation}
 {ssn, pnumber}+={ssn,pnumber, ename, pname, plocation, hours}

SUPER KEY & CANDIDATE KEY
 Super key : Using functional dependency notation, we say that k

is a super key of R if k→R i.e. k is a super key if whenever
t1[k]=t2[k], it is also the case that t1[R]=t2[R] (i.e. t1=t2).
 Candidate key: K is a candidate key for R if and only if

 K → R, and
 for no a  K, a → R
Prime & non-prime attribute: An attribute of a relation schema

R is a prime attribute if it is a member of some candidate key.
Otherwise, it is a non-prime attribute.
FINDING A KEY K FOR R FROM A GIVEN SET F OF
FUNCTIONAL DEPENDENCIES
Input: A universal relation R and a set of functional dependencies F

on the attributes of R.
1. Set K := R.
2. For each attribute A in K {
compute (K - A)+ with respect to F;
If (K - A)+ contains all the attributes in R,
then set K := K - {A}; }
CANONICAL COVER
 Sets of functional dependencies may have redundant dependencies that
can be inferred from the others
 Eg : A → C is redundant in: {A → B, B → C, A → C}
 Parts of a functional dependency may be redundant

 E.g. on RHS: {A → B, B → C, A → CD} can be simplified
to
{A → B, B → C, A → D}
 E.g. on LHS: {A → B, B → C, AC → D} can be simplified
to
{A → B, B → C, A → D}
 Intuitively, a canonical cover of F is a “minimal” set of functional
dependencies equivalent to F, having no redundant dependencies or
redundant parts of dependencies
EXTRANEOUS ATTRIBUTES
 Consider a set F of functional dependencies and the functional
dependency a →  in F.
 Case 1:
 Attribute A is extraneous in a if A  a
and F logically implies (F – {a → })  {(a – A) → }.
 Example: Given F = {A → C, AB → C }
 B is extraneous in AB → C because
 {A → C, AB → C} logically implies A → C (I.e. the

result of dropping B from AB → C).
EXTRANEOUS ATTRIBUTES
 Case2:
 Attribute A is extraneous in  if A  
and the set of functional dependencies
(F – {a → })  {a →( – A)} logically implies F.
 Example: Given F = {A → C, AB → CD}

 C is extraneous in AB → CD since
 AB → C can be inferred even after deleting C
Note: implication in the opposite direction is trivial in each of the cases above,
since a “stronger” functional dependency always implies a weaker one
TESTING IF AN ATTRIBUTE IS EXTRANEOUS
 Consider a set F of functional dependencies and the functional dependency a
→  in F.
Case 1:
 To test if attribute A  a is extraneous in a
1. compute ({a} – A)+ using the dependencies in F
2. check that ({a} – A)+ contains all attributes in ; if it does, A is
extraneous
 Example: Given F = {A → C, AB → C }
 B is extraneous in AB → C
 Solution: Compute A+ under F={A → C, AB→ C }.

 A+=AC, it contains C, hence B is extraneous in AB → C .
TESTING IF AN ATTRIBUTE IS EXTRANEOUS
 Case 2:
 To test if attribute A   is extraneous in 
1. compute a+ using only the dependencies in
F’ = (F – {a → })  {a →( – A)},
2. check that a+ contains A; if it does, A is extraneous
Example:
F={AB→CD, A→E, E→C}. Check whether C is extraneous in
AB→CD.
Solution: Compute AB+ under FC= {AB→D, A→E, E→C}.
AB+=ABDEC, it includes C. So C is extraneous.
CANONICAL COVER
 A canonical cover for F is a set of dependencies Fc such that
 F logically implies all dependencies in Fc, and
 Fc logically implies all dependencies in F, and
 No functional dependency in Fc contains an extraneous

attribute, and
 Each left side of functional dependency in Fc is unique.

ALGORITHM
 To compute a canonical cover for F:
 repeat
Use the union rule to replace any dependencies in F
a1 →  1 and a1 →  2 with a1 →  1  2
Find a functional dependency a →  with an
extraneous attribute either in a or in 
If an extraneous attribute is found, delete it from a → 
until F does not change
 Note: Union rule may become applicable after some extraneous

attributes have been deleted, so it has to be re-applied
EXAMPLE OF COMPUTING A CANONICAL
COVER
 R = (A, B, C)
F = {A → BC, B → C, A → B, AB → C}
 Combine A → BC and A → B into A → BC

 Set is now F={A → BC, B → C, AB → C}
 A is extraneous in AB → C
 Check if the result of deleting A from AB → C is implied by the other
dependencies
 In fact, B → C is already present!
 Set is now F={A → BC, B → C}
 C is extraneous in A → BC
 Check if A → C is logically implied by A → B and the other
dependencies
 Using transitivity on A → B and B → C.
 The canonical cover is: A → B, B → C

Functional Dependencies

Uploaded by

Copyright:

Available Formats

Functional Dependencies

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Functional Dependencies

Uploaded by

Copyright:

Available Formats

FUNCTIONAL DEPENDENCY AND

 Alternatively, the value of α-component of a tuple can uniquely

 FD is basically a many-to-one relationship from one set of

Note: с denotes subset

 The left side of FD is determinant and the right side is

 FD is a property of relation schema(or intension), not a

 It can be defined explicitly by someone who knows the

 In the above example

FDs of Loan-schema(branch-name, loan-number, amount)

FDs of Customer(C-ID, cust-name, cust-city)

Supplier_number City Product_number Quantity

What are the FDs of the above relation?:

{Supplier_number, product_number }→ quantity

 A trivial dependency cannot possibly fail to satisfy(because A→A is

 Example: Supplier(Supplier_number, product_number,city)

 An FD a→b is inferred from a set of dependencies F specify on R if

 Proof: Given that A→B , if t1[A]=t2[A]

 Reflexivity: If α is a set of attributes and β с α then α→β holds.

 Augmentation: If α→β holds and γ is a set of attributes then γα→

 Transitivity: If α→β holds and β→γ holds then α→γ.

Note: с denotes subset

 Union rule: If α→β holds and α→γ holds then α→ γβ holds.

 Given A→B, B→H : By transitivity rule : A→H

 F+ ={ A→B, A→C, A→H

Given, CD→EF and deduced AD→CD

Deduced A→B, given B→E

 By complete means: All possible number of FDs can be formed by

 For a given relation R and a set of FDs , suppose Z is a set of attributes

 {ssn, pnumber}+={ssn,pnumber, ename, pname, plocation, hours}

 Super key : Using functional dependency notation, we say that k

 Candidate key: K is a candidate key for R if and only if

Prime & non-prime attribute: An attribute of a relation schema

Input: A universal relation R and a set of functional dependencies F

 Parts of a functional dependency may be redundant

 {A → C, AB → C} logically implies A → C (I.e. the

 Example: Given F = {A → C, AB → CD}

 Solution: Compute A+ under F={A → C, AB→ C }.

 Fc logically implies all dependencies in F, and

 No functional dependency in Fc contains an extraneous

 Each left side of functional dependency in Fc is unique.

 Note: Union rule may become applicable after some extraneous

 Combine A → BC and A → B into A → BC

 The canonical cover is: A → B, B → C

You might also like