Functional Dependency

1
FUNCTIONAL DEPENDENCIES
K.Yeshwanth
M.sc-CS
2022239008
2
WHAT IS FUNCTIONAL DEPENDENCY?
• Functional dependency is a relationship that

exists when one attribute uniquely determines
another attribute.
• It typically exists between the primary key and

non-key attribute within a table.
3

• Let R be a relation with attributes X and Y,
X->Y
X=>determinant set
Y=>determinant attribute
Y is functionally dependent on X
4

Example:
(roll_no) -> (name)

(roll_no) ->(dept_name)
(roll_no) -> (name, dept_name)
5
In functional dependency theory,

• Closure of a set of functional dependency
• Closure of attributes
• Canonical cover
• Lossless decomposition
• Dependency preservation
6
CLOSURE OF ATTRIBUTE:
• The closure of a set of attributes X is the set of
those attributes that can be functionally
determined from X.
• The closure of X is denoted as X+.

7
CLOSURE OF ATTRIBUTE:
• Consider a relation R with attributes A,B,C and
D where,
A->B
B->D
C->B
In this case the closure of A is,
{A+ } -> {A,B,D}
8
CLOSURE OF A SET OF FUNCTIONAL

DEPENDENCY:
• Closure of set of functional dependency F is set
of all functional dependencies that include F as
well as all dependencies that can be inferred
from F.
• Denoted as F+.
9
RULES FOR FINDING CLOSURE FOR F:

• Reflexivity rule: If A is a set of attributes and
B ⊆ A, then A→B holds.
• Augmentation rule: If A→B holds and C is a

set of attributes, then CA→CB holds.
• Transitivity rule: If A→B holds and B→C

holds, then A→ C holds.
10
RULES FOR FINDING CLOSURE FOR F:

• Union rule: If A→ B holds and A→C holds,
then A→ BC holds.
• Pseudotransitivity rule: If A →B holds and

BC→ D holds, then AC→ D holds.
• Decomposition rule: If A→ BC holds, then

A→B holds and A→C holds.
11
EXAMPLE:
Let us apply our rules to the example
of schema R(A, B, C, G, H, I) and the
set F of functional dependencies
{A→B, A→C,CG→H, CG→I, B→H}.
• A →H.(Transitivity rule)
• CG →HI, A →BC.(Union rule)
• AG →I.(Pseudotransitivity rule)
12
CANONICAL COVER:
• In DBMS, a canonical cover is a set of functional
dependencies that is minimal, irreducible, and
equivalent to the original set of dependencies.
• It is irreducible set of functional dependency.

13
CANONICAL COVER:
• To achieve this we have to follow 3 rules:
Make singleton attribute in RHS.
No functional dependency in Fc contains an
extraneous attribute in LHS.
No redundant functional dependency.
Extraneous attributes: A attribute which in

removal does not affect F.
14
Q1.Find the canonical cover for

the given F= {A->BC, B->C, AB->D}?
15
MAKE SINGLETON ATTRIBUTES IN RHS:

• F= {A->BC, B->C, AB->D}.
Using decomposition rule we can split A->BC as,
o A->B
o A->C
F becomes,
F= {A->B, A->C , B->C, AB->D}.
16
CHECK FOR EXTRANEOUS ATTRIBUTE:

• Let us consider the functional dependency
F= {A->B, A->C , B->C, AB->D}.
To check A is extraneous in AB->D:
Closure(B)=BC (B->C)
To check B is extraneous in AB->D:
Closure(A)=ABC (A->B),(A->C)
Since we have FD (A->B), B in (AB->D) is
extraneous , hence F becomes,
F= {A->B, A->C , B->C, A->D}.
17
REMOVE REDUNDANT FUNCTIONAL

DEPENDENCY:
F= {A->B, A->C , B->C, A->D}
Remove A->C from F.
F’ = {A->B, B->C, A->D}
Closure(A)=ABCD.
Closure of A contains all the other attributes.
Hence A is redundant.
F becomes,
F={A->B, B->C, A->D}.
18
LOSSLESS DECOMPOSITION:
• A decomposition (R1,R2,R3……..Rn) of a relation
R is called lossless decomposition for R, if the
natural join of R1,R2,R3……..Rn produces
exactly the value of R.
• That is a relation must not loose it’s information

even after its decomposition.
19
LOSSLESS DECOMPOSITION:
20
LOSSY DECOMPOSITION:
21
DEPENDENCY PRESERVATION:
• A decomposition D={R1,R2,…,Rn} of R is
dependency preserving with respect to set F of
functional dependency if closure(F1 U F2 U….U
Fn)=closure(F).
• That is, if R is decomposed into R1 with (F1)

and R2 with (F2).Then,
closure(F1 U F2) = closure(F).
22
Q1.Let R(A,B,C,D) be a relational

schema with the following functional
dependencies: (A->B),(B->C),(C->D) and
(D->B). Check whether decomposition
of R into (A,B), (B,C) and (B,D) is
dependency preserving or not?.
23
SOLUTION:
• Let’s say relation R is decomposed into R1, R2
and R3 with functional dependency F1, F2 and
F3 respectively,
To prove a decomposition of R is dependency

Preserving we have to prove,
Closure(F1 U F2 U F3) = Closure(F).

24
SOLUTION: F={A->B, B->C, C->D, D->B}.

• To find F1, F2 and F3,
R1(A,B) R2(B,C) R3(B,D)
Closure(A)=ABCD Closure(B)=BCD Closure(B)=BCD
A->B, A->C, A->D B->C, B->D B->C, B->D
Here, C and D are not Here, D is not present Here, C is not present
present in the sub- in the sub-relation R2. in the sub-relation R3.
relation R1.
Closure(C)=CBD Closure(D)=DBC
Closure(B)=BCD C->B, C->D D->B, D->C
C and D are not D is not present in R2, C is not present in R3,

present in R1, hence hence hence
F1={A->B} F2={B->C, C->B} F3={B->D, D->B}

25
SOLUTION:
Now F1 U F2 U F3 is,
F1 U F2 U F3={A->B, B->C, C->B, B->D, D->B}.
Given,
F={A->B, B->C, C->D, D->B}.
Using transitivity rule,
If C->B and B->D holds, then C->D holds.
(F1 U F2 U F3)+={A->B, B->C, C->D, D->B}.
(F)+={A->B, B->C, C->D, D->B}.
Hence the dependency is preserved.
26
THANK YOU!

Functional Dependency

Uploaded by

Copyright:

Available Formats

Functional Dependency

Uploaded by

Document Information

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 Dependency

Uploaded by

Copyright:

Available Formats

1

WHAT IS FUNCTIONAL DEPENDENCY?

• Functional dependency is a relationship that

• It typically exists between the primary key and

WHAT IS FUNCTIONAL DEPENDENCY?

WHAT IS FUNCTIONAL DEPENDENCY?

(roll_no) -> (name)

In functional dependency theory,

• The closure of X is denoted as X+.

CLOSURE OF A SET OF FUNCTIONAL

RULES FOR FINDING CLOSURE FOR F:

• Augmentation rule: If A→B holds and C is a

• Transitivity rule: If A→B holds and B→C

RULES FOR FINDING CLOSURE FOR F:

• Pseudotransitivity rule: If A →B holds and

• Decomposition rule: If A→ BC holds, then

• CG →HI, A →BC.(Union rule)

• It is irreducible set of functional dependency.

Extraneous attributes: A attribute which in

Q1.Find the canonical cover for

MAKE SINGLETON ATTRIBUTES IN RHS:

CHECK FOR EXTRANEOUS ATTRIBUTE:

REMOVE REDUNDANT FUNCTIONAL

• That is a relation must not loose it’s information

• That is, if R is decomposed into R1 with (F1)

Q1.Let R(A,B,C,D) be a relational

To prove a decomposition of R is dependency

Closure(F1 U F2 U F3) = Closure(F).

SOLUTION: F={A->B, B->C, C->D, D->B}.

A->B, A->C, A->D B->C, B->D B->C, B->D

C and D are not D is not present in R2, C is not present in R3,

F1={A->B} F2={B->C, C->B} F3={B->D, D->B}

You might also like