Functional Dependencies

Functional Dependency

A Functional Dependency (FD) on a relation R is a

formal expression of the form
R: X → Y (or X → Y when R is implicit), where X, Y
R.
Roles of Functional Dependencies
The purpose of functional dependencies and normalization
theory is to ensure that the relational schema defined for a
database is correctly constructed.

A bad relational schema can indeed lead to anomalies during

manipulations.
 Functional Dependency

An attribute or group of attributes Y of a relation functionally

depends on X if every value of X (occurrence of X) corresponds to
a unique value of Y (we say that Y is determined by X).

X determines Y or Y functionally depends on X

In a relation, every attribute is in FD with the primary key.

 Functional Dependency

Example 1:
PRODUCT(Ref_prod, Label_Prod, PU)
Ref_prod → Label_prod
Ref_prod → PU

Example 2:
EVALUATION(Matricule, Lname, Fname, level, module,
score_module)

Contains the following FDs:

Matricule → Lname
Matricule → Fname
Matricule → Level
Matricule, module → score_module
 Functional Dependency
Example 3
Consider the following extension of the relation R
- Existing FD in R :
- A  B (since a1 b1 et a2  c2
but not C since a1 c1 et a1  c2).
- B does not determine C (since b1  c1 et b1  c2).
- C does not determine A (since c2  a1 et c2  a2)
- C does not determine B (since c2  b1 et c2  b2)

R A B C
a1 b1 c1
a1 b1 c2
a2 b2 c2
 Armstrong's Axioms

Armstrong's system allows to systematize the search for all FDs

involved by other FDs.

Properties of functional dependencies

Functional dependencies have three fundamental properties that
are commonly called Armstrong's axioms because they were
highlighted by W. Armstrong.

Assuming that X,Y,Z, are three sets of attributes, it is worthful

to make the following remarks before stating the properties:
The writing X , Z is a simplified writing of the set union of the two
sets of attributes X and Z. This means that the writing X , Z
should be interpreted as X Z.
 Armstrong's Axioms

It should also be noted that the set union is an associative and

commutative operator:

((X Y) Z ) = (X (Y Z))
X Z=Z X
 Armstrong's Axioms

1. Reflexivity
Any group of attributes determines itself and
determines each of its attributes (or subgroup of its
attributes).
if X Y Y→X

Example:
brand (n_car,brand) n_car, brand  brand
 Armstrong's Axioms

2. Augmentation
If an attribute X determines an attribute Y, then any
group composed of X enriched with other attributes
determines a group composed of Y and enriched with
the same other attributes.
Let X, Y and Z be attributes:
X → Y Z, XZ → YZ
 Armstrong's Axioms

3. Transitivity
If an attribute X determines an attribute Y and that
attribute Y determines another attribute Z, then X
determines Z.

Let X, Y and Z be attributes :

X → Y and Y → Z X → Z

Example:
n_carmodel AND modelbrand n_carbrand
 Armstrong's Axioms

Other properties deduced from Armstrong's axioms

From Armstrong's axioms, a number of additional

properties can be deduced:
• Pseudo-transitivity
• Decomposition
• Union
 Armstrong's Axioms
4. Pseudo-transitivity

If an attribute X determines another attribute Y, and

Y belongs to a group G which determines a third
attribute Z, then the group G' obtained by
substituting Y for X in G also determines Z.

Let W, X, Y and Z be attributes:

X→Y and WY→Z WX→Z

This property is deduced from augmentation and

transitivity:
X→Y and WY→Z WX→WY and WY→Z WX→Z
 Armstrong's Axioms
5. Decomposition

If an attribute determines a group of attributes, then it

determines each of the attributes in that group taken
individually.

Let X, Y and Z be attributes:

X→YZ X→Z et X→Y

This property is deduced from reflexivity and

transitivity:
X→YZ X→YZ and YZ→Z X→Z
 Armstrong's Axioms

6. Union

If an attribute determines several other

attributes, then it determines any group
composed of these attributes.

Let X, Y and Z be attributes:

X→Y and X→Z X→YZ
 Armstrong's Axioms
Demonstration

x→x x→xx
x→y xx→xy
alors x→xy –--(1)
x→z yx→yz ---(2)
Donc x→yz

This property is deduced from reflexivity,

augmentation and transitivity:
X→Y and X→Z X→XX and XX→XY and YX→YZ
X→YZ
 Armstrong's Axioms
Exercise
Consider the set of the following functional
dependencies: {A → B, D → E}
Show that AD → BE

Demonstration:
A → B by augmentation with D => AD → BD(1)
D → E by augmentation with B => BD → BE (2)
By transitivity = > AD → BE
 Functional Dependency
Trivial Functional Dependencies
A trivial functional dependency is a functional dependency of
the form
X → Y, where Y X.
In other words, a functional dependency is trivial if it is
obtained through the reflexivity property.
Example : Consider
(1) A ,B→ B
(2) B,C→ C
(3) A ,C→ D
(1) is trivial since B A ,B
(2) is trivial since C B ,C
(3) is not trivial since D A ,C
 Functional Dependency
Elemantary functional dependencies
Let G be an attribute group and A an attribute, a FD G→A
is elementary if A is not included in G and if there is no
attribute A' of G that determines A.

Example:
AB→C is elementary if neither A nor B
determines C.
 Functional Dependency

Non-Elemantary functional dependencies

Say why?
AB→A?
AB→CB?
 Functional Dependency

Remark
We can always rewrite a set of FDs into a set of elementary
functional dependencies:
1. Delete trivial DFs obtained by reflexivity,
2. Decompose the non-atomic right part of the FDs into several EFDs.
 Functional Dependency
Rewriting FD to EFD

We can rewrite the non-elementary FDs of the

previous example by decomposing them into
EFDs:
AB→A is not considered because it is a trivial
FD obtained by reflexivity.
AB→CB is decomposed into AB→C and AB→B, and
AB→B is no longer considered since it is trivial.
 Functional Dependency
Example and FD representation
Example

Car(Immat, Brand, Model, Power, Color).

F = { Immat → Model, Model → Brand, Model → Power}.

 Functional Dependency

Example and FD representation

•A set of EFDs can be represented by a directed graph, such

that the nodes are the attributes, and the arcs are the EFDs
(with a single attribute at the destination of each arc and
possibly several at the source).
 Functional Dependency
Definition of a functional dependency closure

Let F be a set of FDs, the closure of F is the set of all FDs

logically implied by F

1. Transitive closure (F+)

The transitive closure of a set of FDs is this same set enriched by
all the FDs deduced by transitivity and/or augmentation.
 Functional Dependency

Example:
Consider this set F = {A→B, B→C, B→D, A→E}.

The transitive closure of F is:

F+ = { A→B, B→C, B→D, A→E, A→C, A→D }

F = {CARN  TYPE, TYPE  BRAND, TYPE  POWER, CARN  COLOR}

F+ = F  {CARN  BRAND, CARN  POWER}

 Functional Dependency

1. Transitive closure (F+)

Example
F = {A → B, B → C, B → D, B → E}.

The transitive closure of F is:

F+ = {A → B, B → C, B → D, B → E, A → C, A → D, A → E}.
 Closure of Functional Dependency

Remark
Inference rules have a way to compute the closure of F+.

Computing F+ can be time-consuming, because the cardinality of F+

can be large even if F is restricted.

On the other hand, there is an efficient way to determine if a given

FD belongs to F+. For this, we need to introduce the notion of
attribute closure
 Closure of Functional Dependency

2. Attribute Closure

Let the relation R, and F a set of FDs satisfied by R,

Let A be an attribute (or a group of attributes) of R,

We call closure of A, denoted A+, the set of all attributes which are in
functional dependence with A.

According to the definition of the closure of F, we have equivalently:

X + = {A | X → A F +}
 Closure of Functional Dependency

Closing attributes
The following algorithm allows us to calculate this closure:
Algorithm
Begin
A+={A}
while (True) do
for each FD XY of F do
if X is a set in A+ then
A+=A+ ∪ {Y}
end;
end;
if A+ is not changed in this iteration then break;

end;
End
 Closure of Functional Dependency

Remark
• If X is a candidate key or a superkey of the
relation R then X+ is the set of attributes of R,
 Closure of Functional Dependency

Closing attributes
Exercise
Consider R(A,B,C,D,E,G,H) and FD set F={GA,ABC, BD, CDE, CEGH}
a) Compute G+
G+={G}
1st iteration
GA: G∈G+ then G+={G,A}
ABC:AB ∉ G+ then G+ unchanged
BD: B ∉ G+ then G+ unchanged
CDE: CD ∉ G+ then G+ unchanged
CEGH: CE ∉ G+ then G+ unchanged
G+={G,A} has been changed, continue
 Closure of Functional Dependency

Closing attributes
F={GA,ABC, BD, CDE, CEGH}
2nd iteration
G+={G,A}
GA: G∈G+ then G+={G,A} then G+ unchanged
ABC:AB ∉ G+ then G+ unchanged
BD: B ∉ G+ then G+ unchanged
CDE: CD ∉ G+ then G+ unchanged
CEGH: CE ∉ G+ then G+ unchanged
G+={G,A}: G+ unchanged, STOP!
 Closure of Functional Dependency

Closing attributes
F={GA,ABC, BD, CDE, CEGH}
2) Compute BC+
BC+={B,C}
1st iteration
GA : G ∉ BC+ then BC+ is unchanged
ABC:AB ∉ BC+ then BC+ is unchanged
BD: B ∈ BC+ then BC+ ={B,C,D}
CDE: CD ∈ BC+ then BC+ ={B,C,D,E}
CEGH: CE ∈ BC+ then BC+ ={B,C,D,E, G,H}
BC+={B,C,D,E, G,H} has been changed, continue
 Closure of Functional Dependency

Closing attributes
F={GA,ABC, BD, CDE, CEGH}
BC+={B,C,D,E, G,H}
2nd iteration
GA : G ∈ BC+ ={A,B,C,D,E, G,H}
ABC:AB ∈ BC+ then BC+ is unchanged
BD: B ∈ BC+ then BC+ is unchanged
CDE: CD ∈ BC+ then BC+ is unchanged
CEGH: CE ∈ BC+ then BC+ is unchanged
BC+={A,B,C,D,E, G,H} has been changed, Continue
 Closure of Functional Dependency

Closing attributes
F={GA,ABC, BD, CDE, CEGH}
BC+={A,B,C,D,E, G,H}
3rd iteration
GA : G ∈ BC+ then BC+ is unchanged
ABC:AB ∈ BC+ then BC+ is unchanged
BD: B ∈ BC+ then BC+ is unchanged
CDE: CD ∈ BC+ then BC+ is unchanged
CEGH: CE ∈ BC+ then BC+ is unchanged
BC+=={A,B,C,D,E, G,H} is unchanged, STOP!
So, BC+={A,B,C,D,E, G,H}
 Closure of Functional Dependency
Exercise
Let R(A,B,C,D,E,F) and G={B→E, A→BC, CD→EF}
Compute B+, AD+

B+={B,E}
AD+={A,D,B,C,E,F}
 Closure of Functional Dependency
Coverage and Minimum Coverage
Definition of a cover
Let R be a relation and F1, F2 two sets of FDs defined in R:
F1 is a cover of F2 iff F2+ is included in F1+

Remark
To show that F1 is a cover of F2, it suffices to show that any FD of F2
belongs to F1+ (is derivable from the FDs of F1)
 Closure of Functional Dependency
Example
R(A,B,C,D,E,F)
F={(1) ABC, (2) BD}
F’={(3) ABD, (4) ABC, (5) BD}
Show that F’ is a cover of F.

To show that F1 is a cover of F2, it suffices to show that any FD of F2

belongs to F1+ (is derivable from the FDs of F1)
 Closure of Functional Dependency

F={(1) ABC, (2) BD}

F’={(3) ABD, (4) ABC, (5) BD}

(1) ABC
(3) By decomposition (6) AB and (7) AD
(6) and (4) yield by pseudo-transitivity (8) AC
(6) and (8) yield by union ABC so (1) is derivable by F’ (belongs
to F’+)
(2) is identical to (5) so df(2) is derivable by F’ (belongs to F’+)
Hence, F’ is a cover of F
 Definition of two sets of equivalent DFs

Let R be a relation, F1 and F2 sets of FDs defined in R,

F1 and F2 are equivalent if and only if F1+=F2+
iff F1 is a cover of F2 and F2 is a cover of F1.
 Minimum coverage

Minimum coverage (Generating family)

The minimum coverage of a EFD set is a minimum subset
of the EFDs that can generate all other EFDs.

Any set of EFDs (and therefore any set of FDs) admits at

least one minimal cover.

Example :
F = {A→B, A→C, B→C, C→B} admits two minimal cover:

CM1 = {A→C, B→C, C→B} and CM2 = {A→B, B→C, C→B}

 Minimum coverage
Minimum coverage (Generating family)

A set of functional dependencies is irreducible iff it satisfies

the following three properties:
1. The right-hand side (the dependent) of each functional
dependency of F contains a single attribute (singleton set).
2. The left-hand side (the determinant) of every functional
dependency of F is irreducible, (i.e., no attribute can be removed
from the determinant without changing the closure F+). We will
say that such a functional dependency is left-irreducible or
elementary.
3. No functional dependency is redundant (no FD can be removed
from F without changing the F+ closure)
 Minimum coverage
Minimum coverage (Generating family)

Example
Let F={ACD, BAF, CBE, FEC}

Property 1:

Right members of FDs (determinants) are singletons:

F={ACD, BA, BF, CB, CE, FE, FC}
 Couverture minimale
F={ACD, BA, BF, CB, CE, FE, FC},
Property 2:

Left members of irreducible FDs (determinants)?

ACD
CB and BA then CA
From which ACD is reducible to CD
F={CD, BA, BF, CB, CE, FE, FC}
 Minimum coverage
F={CD, BA, BF, CB, CE, FE, FC}
Property 3:
No FDs are redundant
FC and CE then FE, hence FE is redundant
CM1= {CD, BA, BF, CB, CE, FC}
Also
CB and BF then CF
CF and FE then CE
Hence, CE is redundant,
CM2={CD, BA, BF, CB, FE, FC}
 Key
Formal definition of Key
Let R(A1,A2,...,An) be a relation and K a subset of A1,A2,... ,An.

K is a key of R iff:

a) K→A1,A2,...,An

b) and there does not exist X included in K such that X→A1,A2,...,An.

A key is therefore a minimum set of attributes of a relation

that determines all the others.
 Key
Candidate keys and primary key
If a relation has multiple keys, each is called a candidate key
and one in particular is chosen to be the primary key.

"All-key" relation

Provided that a relation must has a key, if a relation R does

not admit any key K a subset of the attributes A1..An of R,
then it is that K=A1..An (the key is composed of all the
attributes of R).

We are talking about an “all-key” relation.

 Key

Consider the schema of the following relation:

R(A, B, C, D, E)
This relation is defined in extension by the tuples below:
After stating the FDs, determine which of the following
groups of attributes are keys?
A,B,C,D,E,{B,E},{A,B,C,D,E}.

A B C D E
a1 b2 c2 d3 e2
a1 b2 c2 d1 e4
a2 b3 c2 d1 e5
a2 b4 c5 d1 e5
 Key

Superkey

A constituent that includes a key is called a superkey.

 Key

Exercise
Consider R(A,B,C,D,E,F) and FD set{ACD, BAF, CBE,
FEC}
Determine candidate keys?

Candidate keys
Let the superkey formed from the set of attributes of R be: ABCDEF
or let the superkey formed from the attributes of the left members of
the FDs (determinants): ABCF