Chapter 3 - Functional Dependencies

ĐẠI HỌC FPT CẦN THƠ
Chapter 3
Design theory for
Relational Database - FDs
Objectives
1 Understand what are functional dependencies
2 Understand the rules about FDs
33 Understand what are keys, super-keys
4 Understand what are closure-sets and how to determine them
5 Understand what are closing sets of FD’s and how to determine them
6 Understand what is projecting FD’s

Contents
1 Functional Dependencies
2 Rules about FDs
3 Key & Super-Key
4 Closure-sets and Algorithm for calculating the closure-set of a relation
5 Closing set of FD’s
6 Projecting FD’s
1. Functional Dependency Definition
A functional dependency (FD) is a constraint between

two sets of attributes in a Relation from a database
Given a relation R, a set of attributes X in R is said to

functionally determine another set of attributes Y,
also in R, (written X → Y) if and only if each X value is
associated with precisely one Y value
Customarily we call X the determinant set and Y the

dependent attribute
A functional dependency FD is called trivial if Y is a subset

of X
1. Functional Dependency Definition
A Functional
Dependency (FD) X → Y
X Y
on a relation R is a
statement of the form:
“If 2 tuples of R agree

on s.o.a. X, then they
must also agree on
s.o.a. Y”
X->Y  (t1(X) = t2(X)

=> t1(Y) = t2(Y))
Example: Functional Dependency
Movies1
? 1. The following FD is true or false:

(title, year) → (length, genre, studioName)
Relation:
Attributes:
2. How about this FD (TRUE or FALSE)?
Rows: (title, year) → (starName)
1. TRUE
(title, year) → (length, genre, studioName)
2. FALSE
(title, year) → (starName)
1. TRUE/FALSE
A→B
2. TRUE/FALSE
AB → C
2. Properties of
functional dependencies
Given that X, Y, and Z are sets of attributes in a relation R,
one can derive several properties of functional dependencies.
Among the most important are Armstrong’s axiom, which are used in
database normalization:
• Subset Property (Reflexivity): If Y is a subset of X, then X → Y
• Augmentation (Augmentation): If X → Y, then XZ → YZ
• Transitivity (Transitivity): If X → Y and Y → Z, then X → Z
From these rules, we can derive these secondary rules:

• Union: If X → Y and X → Z, then X → YZ
• Decomposition: If X → YZ, then X → Y and X → Z
• Pseudo transitivity: If X → Y and YZ → W, then XZ → W
• Accumulation: If X → YZ and Z → V, then X → YZV
• Extension: If X → Y and W → Z, then WX → YZ
3. Keys
A set of one or more attributes {A1, A2, .., An} is

called a key of the relation R if:
1. Those attributes functionally determine all

other attributes of R.
This means that: It is impossible for 2 tuples of R
to agree on all of {A1, A2, .., An}
2. No proper subset of {A1, A2, .., An}

functionally determines all other attributes
of R
This means that: A Key must be minimal
Example: Keys
Exercise 1:
(title, year) forms a key?
Exercise 2:
(title, year, starName) forms a key ?
Example: Keys
Exercise 1:
(title, year) forms a key? Not a key
Row 1 and 2: agree in (title, year) but do not agree in
starName → (title, year) do not determine starName
Exercise 2:
(title, year, starName) forms a key ? A key
Find keys
A B C D E F
13
Find keys
A B C D E F
Custid Cphone
14
3. Super-key
A set of attributes that contains a key is called a

Super-key
A superkey is a set of attributes of a relation

whose values can be used to uniquely identify a
row
Example: Super-key
There are many Super-key in the above schema:

(title, year, starName)
(title, year, starName, length, studioName)
Exercise: Can (title, year, starName, length, studioName)

form a key?
Example: Super-key
There are many Super-key in the above schema:

(title, year, starName)
(title, year, starName, length, studioName)
Exercise: Can (title, year, starName, length, studioName)

form a key?
→ No. Reason: Not minimal
4.Closure sets
Suppose: {A1,…, An} is a set of attributes; S is a set of FD’s.

The closure of {A1,…, An} under the FD’s in S is the
set of attributes B such that every relation that
satisfies all the FD’s in set S also satisfies:
{A1,..,An}→B
This means that: {A1,..,An}→B follows from the FD’s of S
Closure of a set of attributes {A1, ..., An} is denoted
{A1, A2, ..., An}+
Closure of a set of FD’s S is the set of functional
dependencies Q that includes all FDs are derived
from S by Amstrong rules.
5. Closure sets
Algorithm (courtesy [DBSC] Fig. 7.9 [p. 281])

• INPUT: A set of attributes A={A1,..,An} and a set of FD’s F
OUTPUT: The closure result = A+
• Step 1: Split all FDs in F such that: each FD has a single

attribute on the right;
Step 2: result = A;
Step 3: while (changes to result)

for each (FD X → Y of F) do
if (X is the sub-set of result)
result = result U Y;
Example: Closure Set
Example: Closure Set
Exercises
Exercises
Closures and Keys
An efficient algorithm
to finding KEYS for a relation
Suppose L contains those attributes that occur only on the left-hand

side of FDs
Suppose R contains those attributes that occur only on the right-hand

side of FDs
Suppose M contains those attributes that occur on both side of FDs

Note:
L Intersects M = EMPTY
M Intersects R = EMPTY
L Intersects R = EMPTY
25
Some LEMAs
Lema 1: for every attribute A, if A is only in L then

A must be part of every key
Lema 2: for every attribute A, if A is only in R
then A will not be part of any key
Conclusion: we only focus only on L and M to

find all keys
26
Exercises 1
R (A, B, C, D)
S = {BC→D, D→A, A→B}
What are all the keys of R?
What are all the super-keys for R that are not
keys?
Exercises 2
R (A, B, C, D)
S = {AD→B, AB→C, BC→D, CD→A}
What are all the keys of R?
What are all the super-keys for R that are not
keys?
Closing sets of FD’s
A minimal basis (or closing sets) of FD’s for a relation
is a set of functional dependencies B that satisfies three
conditions:
All the FD’s in B have singleton right sides.
If any FD is removed from B, the result is no longer the
basic.
If for any FD in B we remove one or more attributes
from the left side, the result is no longer the basic.
No trivial FD can be in a minimal basis.
Projecting FD’s
Algorithm for projecting a set of FD’s
Ex. The attribute closures
1. R = (A,B,C,D,E), F = {A -> C, E -> D, B -> C}
a. {A, B, E}+ b. {A, B, C, E}+ c. {A, B, D, E}+
2. R = (A,B,C,D,E), F = {A -> BE, C -> BE, B -> D}
a. {A, C}+ b. {A, B, C}+ c. {A, C, E}+
3. R = (A,B,C,D,E,F), F = {A -> B, B -> D, C -> D, E -> F}
a. {A, C, E}+ b. {A, B, C, E}+ c. {A, C, D, E, F}+
4. R = (A,B,C,D), F = {AB -> C, BC -> D, CD -> A}
a. {A, B}+ b. {B, C}+ c. {B, C, D}+
5. R = (A,B,C,D), F = {A -> BCD, C -> A}
a. {A}+ b. {C}+ c. {A, D}+ d. {A, B, C}+
Let’s compute the attribute closures.

32
Ex. Closing sets of FD’s
Find closure of FD:

1. R = <U, F>, U = {ABCDEGH}, F = {ABH → CK, A → D, C →E,
BGH → F, F → AD, E →F, BH → E}
2. R = <U, F>, U = {ABCDEGH}, F = {A→ BC, BE → G, E → D,
D → G, A → B, AG → BC}
3. R = <U, F>, U = {ABCDEGHIJ}, F = {A → BDE, DE → G, H
→ J, J → HI, E → DG, BC→ GH, HG→J, E→G}
33
Objectives
1 Understand what are anomalies
2 Understand why must decompose a relation
3 Understand what are normal forms (1NF, 2NF, 3NF, BCNF)
4 Understand the good, bad and ugly of decomposition

Contents
1 Anomalies
2 What are decomposition?
3 Decomposition: The good, bad and the ugly
4 1NF, 2NF, 3NF, BCNF definition
5 Algorithms to decompose a relation into BCNF, 3NF

1. Anomalies introduction
Careless selection of a relational database schema
can lead to redundancy and related anomalies
title year length genre studioName starName
Star Wars 1977 124 SciFi Fox Carrie Fisher
Star Wars 1977 124 SciFi Fox Mark Hamill
Star Wars 1977 124 SciFi Fox Harrison Ford
Gone With The Wind 1939 231 drama MGM Vivien Leigh
Wayne's World 1992 95 comedy Paramount Dana Carvey
Wayne's World 1992 95 comedy Paramount Mike Meyers
Which problems do you see in the relation?

1. Anomalies introduction
Careless selection of a relational database schema
can lead to redundancy and related anomalies
Which problems do you see in the relation?

→ redundant
1. Anomalies
Problems such as redundancy that occur when we try

to cram too much into a single relation are called
anomalies
The principal kinds of anomalies:
Redundancy: information maybe repeated
unnecessarily in several tuples
Update Anomalies: We may change information
in one tuple but leave the same information
unchanged in another
Deletion Anomalies: If a set of values becomes
empty, we may lose other information as a side
effect
1. Anomalies
The principal kinds of anomalies in the relation:
Redundancy:
Update Anomalies:
Deletion Anomalies:
1. Anomalies
The principal kinds of anomalies in the relation:
Redundancy: the length and genre
Update Anomalies: if we found that Star Wars is 125 minutes
long, we may change the length in the first tuple but not in the
second and third tuples
Deletion Anomalies: if we delete “Vivien Leigh” from the set
of stars of Gone with the Wind, then we have no more stars for
that movie. The last tuple for the movie would disappear also
its information of length, genre
2. Decomposition
The accepted way to eliminate anomalies is the

decomposition of relations
Decomposition of a relation R involves splitting
the attributes of R to make the schemas of 2 new
relations
Definition: Given a relation R(A1,..,An), we say R is
decomposed into S(B1,..,Bm) and T(C1,..,Ck) if:
+ {A1,..,An} = {B1,..,Bm} U {C1,..,Ck}
+ S = ∏B1,..Bm(R)
+ T = ∏C1,..,Ck(R)
Example: Decomposition
Movies
How can you split the attributes of Movies relation

into 2 new schema?
Example: Decomposition
Movies
Movies1 Movies2
title year length genre studioName title year starName
Star Wars 1977 124 SciFi Fox Star Wars 1977 Carrie Fisher
Gone With The Wind 1939 231 drama MGM Star Wars 1977 Mark Hamill
Wayne's World 1992 95 comedy Paramount Star Wars 1977 Harrison Ford
Gone With The1939
Wind Vivien Leigh
Wayne's World1992 Dana Carvey
Wayne's World1992 Mike Meyers
Discuss
Movies1 Movies2
title year length genre studioName title year starName
Star Wars 1977 124 SciFi Fox Star Wars 1977 Carrie Fisher
Gone With The Wind 1939 231 drama MGM Star Wars 1977 Mark Hamill
Wayne's World 1992 95 comedy Paramount Star Wars 1977 Harrison Ford
Gone With The1939
Wind Vivien Leigh
The redundancy is eliminated (the length of each film

appears only once)
The risk of an update anomaly is gone (we only have to
change the length of Star Wars in one tuple)
The risk of a deletion anomaly is gone (if we delete all the
stars for Gone with the wind, that deletion makes the movie
disappear from Movies2 but still be found in Movies1)
Boyce – Codd Normal Form (BCNF)
Movies title year length genre studioName starName

Is relation Movies in BCNF? Why?

Movies title year length genre studioName starName

Movies1
title year length genre studioName
Star Wars 1977 124 SciFi Fox
Gone With The Wind 1939 231 drama MGM
Wayne's World 1992 95 comedy Paramount
Is relation Movies1 in BCNF?

Movies1
Relation Movies1 is in BCNF.

3. Decomposition:
The Good, Bad and Ugly
After we decompose a relation schema into BCNF,

the resulting relation do not exhibit anomalies;
That’s the “Good”
But decomposition can also have some bad/ugly

consequences, such as:
We can’t recovery the original information; OR
After reconstruction, the FDs maybe not hold
Example: Loss of information
after decomposition
R3
A B C
R R1 R2 1 2 3
A B C A B B C 1 2 5
1 2 3 1 2 2 3 4 2 3
4 2 2 5 4 2 5
4 2 5
Example: Dependency Loss
If we check the projected FD’s in the relations of the

decomposition, can we can be sure that when we
reconstruct the original relation from the
decomposition by joining, the result will satisfy the
original FD’s?
4. Normal Forms (NF)
1NF
1NF A relation R is in first normal form (1NF) if and

only if all underlying domains contain atomic
values only (singled valued attribute)
Example: 1NF? Why?
22
23
1NF
24
1NF
25
1NF
26
1NF
27
1NF
28
2NF
A relation R is in second normal form (2NF) if and
only if it is in 1NF and every non-key attribute
is fully dependent on the primary key
Example: 2NF? Why?
2NF
Example: 2NF? Why?
2NF
Example: 2NF? Why?
2NF
2NF
33
2NF
34
2NF
35
2NF
36
2NF
37
2NF
38
39
40
41
3NF
A relation R is in third normal form (3NF) if and
is non-transitively dependent on the primary
key.
An attribute C is transitively dependent on
attribute A if there exists an attribute B such that:
A->B and B->C
Note that 3NF is concerned with transitive
dependencies which do not involve candidate keys.
A relation with more than one candidate key will
clearly have transitive dependencies of the form:
primary_key -> other_candidate_key -> any_non-
key_column
Employee No. → Department No.
3NF
Department No. → Department Name
A B C D
43
3NF
44
1NF -> 2NF -> 3NF?
45
1NF -> 2N -> 3NF?
MASV HOTEN DIACHI MAMON TENMON DIEM

A01 Lê Na 12 Thái Hà M01 CSDL 8
A01 Lê Na 12 Thái Hà M02 Anh 9
A02 Trần An 56 Mã Mây M01 CSDL 8
A03 Hà Nam 24 Cầu Gỗ M01 CSDL 6
A03 Hà Nam 24 Cầu Gỗ M02 Anh 8
A03 Hà Nam 24 Cầu Gỗ M03 Toán 1 9
46
MASV HOTEN DIACHI 1NF ->
MAMON 2N
TENMON ->DIEM
3NF?
A01 Lê Na 12 Thái Hà M01 CSDL 8
A01 Lê Na 12 Thái Hà M02 Anh 9
A02 Trần An 56 Mã Mây M01 CSDL 8
A03 Hà Nam 24 Cầu Gỗ M01 CSDL 6
A03 Hà Nam 24 Cầu Gỗ M02 Anh 8
A03 Hà Nam 24 Cầu Gỗ M03 Toán 1 9
MASV HOTEN DIACHI MASV MAMON DIEM

A01 Lê Na 12 Thái Hà A01 M01 8
A02 Trần An 56 Mã Mây A01 M02 9
A03 Hà Nam 24 Cầu Gỗ A02 M01 8
A03 M01 6
MAMON TENMON
A03 M02 8
M01 CSDL
A03 M03 9
M02 Anh
M03 Toán 1
47
1NF -> 2N -> 3NF?
48
BCNF
A relation R is in BCNF if and only if: Whenever

there is a Non-Trivial FD
A1A2..An -> B1B2..Bm for R, it is the case that:
{A1,..,An} is a super-key for R
That is: the left side of every Non-Trivial FD must be a

super-key
Example: BCNF or not

The above relation is not in BCNF because:

Consider the FD:
{title,year} -> {length, genre, studioName}
We know that {title, year} is not a super-key

The above relation is in BCNF because:

{title,year} -> {length, genre, studioName}
And: neither title nor year by itself functionally
determines any of the other attributes
title year starName

Star Wars 1977 Carrie Fisher
Star Wars 1977 Mark Hamill
Star Wars 1977 Harrison Ford
Gone With The1939
Wind Vivien Leigh
The above relation is in BCNF because: it has no

Non-Trivial FD
Differences between BCNF and 3NF
3NF Boyce-Codd
a nontrivial functional dependency: a nontrivial functional dependency
X -> A holds in R, either X -> A holds in R, then:
(a) X is a superkey of R, or a) X is a superkey of R
(b) A is a prime attribute of R.
Note:Attributes which are parts of any candidate key of relation are called
as prime attribute, others are non-prime attributes
A functional dependency X -> Y is a full functional dependency if
removal of any attribute A from X means that the dependency does not
hold any more; A partial functional dependency is not a full functional
dependency
1 or 2 or 3 NF?
1 or 2 or 3 NF?
BCNF?
BCNF?
BCNF?
5. Decompose a relation
into BCNF, 3NF
The goal of decomposition is to replace a relation by

several relations that do not exhibit anomalies
So, it turns out, a simple condition under which the
anomalies can be guaranteed not to exist. This
condition is called Boyce-Codd Normal Form, or BCNF
5. Decompose a relation
into BCNF, 3NF
BCNF is a solution for eliminating Anomalies

But, BCNF can lead to the loss of information and
functional dependencies (in some cases, after
decomposition into BCNF, we can’t keep both the
lossless-join and dependency-preservation
properties)
So, 3NF is the solution that have both the lossless-
join and dependency-preservation properties
BCNF decomposition algorithm
Input: A relation R with a set of FD’s F

Output: A BCNF decomposition of R with lossless join
Method:
At each step compute the key for the sub-relation R
if not in BCNF, pick any FD X->Y which violates
break the relation into 2 sub-relations
R1(XY)
R2(S - Y)
this has a lossless join
project FD's onto each sub-relation
continue until no more offending FD's
3NF decomposition algorithm
Input: A relation R with a set of FD’s F

Output: A decomposition of R into a collection of
relations, all of which are in 3NF. This decomposition has a
lossless join and dependency-preservation.
Method:
Find minimal basic for F, say G.
∀ X->A ∈ G, use XA as the schema of one relations in the
decomposition.
If none of the sets of relations from Step 2 is a super key for
R, add another relation whose schema is a key for R.
3NF decomposition algorithm
Step 1: Find the minimal cover of FDs

Step 2. Find all (candidate) keys.
Step 3: Merge FDs with same LHS and whose RHS are non-key
attributes, we get the set F1.
Step 4: Check each FD in the set F1 for violation of 3NF, and
split table accordingly.
Checking FD: if the FD X --> Y violates 3NF as its LHS is not
a superkey (and RHS is a set of non-key attributes), then
the 3NF table is obtained by attributes {X,Y} with with FDs X
--> Y
Step 5: Finally, add the table into normalized 3NF table set
(obtained by removing RHS attributes of FDs using which we
produced a table) with remain FDs
3NF decomposition example
Example: Consider r(ABCDEF) subject to the following FDs:
F = {A →BCF, B →DE, ABD →CF, AC →DE }
Find a 3NF database for r under F.
Step 1: Find the minimal cover of FDs

Step 2. Find all (candidate) keys.
Step 3: Merge FDs with same LHS and whose RHS are non-key attributes,
we get the set F1.
Step 4: Check each FD in the set F1 for violation of 3NF, and split table
accordingly.
Checking FD: if the FD X --> Y violates 3NF as its LHS is not a superkey
(and RHS is a set of non-key attributes), then the 3NF table is obtained
by attributes {X,Y} with with FDs X --> Y
Step 5: Finally, add the table into normalized 3NF table set (obtained by
removing RHS attributes of FDs using which we produced a table) with
remain FDs
❖Step 1: Find the minimal cover of FDs, which

contains
a --> b
b --> d
b --> e
a --> c
a --> f
❖Step 2. Find all candidate keys. The set of

candidates keys is { (a) }.
The set of key attributes is: { a }.
❖Step 3: Merge FDs with same LHS and whose

RHS are non-key attributes, we get the set F1
which contains:
a --> f,c,b
b --> e,d
❖Step 4: Check each FD in the set F1 for violation of 3NF,

and split table accordingly.
Checking FD a --> f,c,b: FD does not violate 3NF
Checking FD b --> e,d: The FD violates 3NF as its LHS is
not a superkey (and RHS is a set of non-key attributes).
The following 3NF table is obtained: b,e,d
with FDs: b --> e,d
❖Step 5: Finally, add the following table into normalized

3NF table set (obtained by removing RHS attributes of
FDs using which we produced a table): a,b,c,f
with FDs: a --> b,c,f
❖Solution: Find a canonical cover for (R,F):

F= { A →B, B → DE, A →CF } same as
F= { A →BCF, B →DE }
❖Final decomposition: r = ( ABCF, BDE )

71
❖Step 1: Find the minimal cover of FDs, which contains
b --> c
d --> a
72
❖Step 2. Find all candidate keys. The set of candidates
keys is { (b,d) }.
The set of key attributes is: { b,d }.
73
❖Step 3: Merge FDs with same LHS and whose RHS are
non-key attributes, we get the set F1 which contains:
b --> c
d --> a
74
❖Step 4: Check each FD in the set F1 for violation of 3NF,
and split table accordingly.
Checking FD b --> c: The FD violates 3NF as its LHS is not a
superkey (and RHS is a set of non-key attributes).
The following 3NF table is obtained: b,c; with FDs: b --> c
Checking FD d --> a: The FD violates 3NF as its LHS is not a
The following 3NF table is obtained: d,a; with FDs: d --> a
75
❖Step 5: Finally, add the following table into normalized
3NF table set (obtained by removing RHS attributes of FDs
using which we produced a table): b,d; with FDs: empty
76
77
Step 1: Find the minimal cover of FDs, which contains
s,d --> p
j,p --> c
j --> s
78
Step 2. Find all candidate keys. The set of candidates
keys is { (j,d,q,v), }.
The set of key attributes is: { j,d,q,v }.
79
Step 3: Merge FDs with same LHS and whose RHS are
non-key attributes, we get the set F1 which contains:
s,d --> p
j,p --> c
j --> s
80
Step 4: Check each FD in the set F1 for violation of 3NF, and
split table accordingly.
Checking FD s,d --> p: The FD violates 3NF as its LHS is not a
The following 3NF table is obtained:s,d,p; with FDs: d,s --> p
Checking FD j,p --> c: The FD violates 3NF as its LHS is not a
The following 3NF table is obtained: j,p,c; with FDs: j,p --> c
Checking FD j --> s: The FD violates 3NF as its LHS is not a
The following 3NF table is obtained: j,s; with FDs: j --> s
81
Step 5: Finally, add the following table into normalized 3NF table
set (obtained by removing RHS attributes of FDs using which we
produced a table): j,d,q,v; with FDs: empty
82
Summary 1
Decompose a relation into BCNF is a solution for

eliminating anomalies
But BCNF can cause information loss and
dependency loss
3NF is a relax solution of BCNF that keep loss-less
join and dependency-preservation properties
Summary 2:
2NF 3NF Boyce-Codd

every nonprime a nontrivial functional a nontrivial functional
attribute A in R is not dependency: X => dependency X =>
partially A holds in R, A holds in R, then:
dependent on any key either a) X is a superkey of
of R (a) X is a superkey of R
R, or
(b) (b) A is a prime
attribute of R.
Note:A functional dependency X => Y is a full functional dependency if

removal of any attribute A from X means that the dependency does not
hold any more; A partial functional dependency is not a full functional
dependency
Fourth Normal Form
87
Fourth Normal Form
88
Fifth Normal Form (5NF)
89
Fifth Normal Form (5NF)
90
Reference
1NF, 2NF, 3NF, BCNF, 4NF and 5NF in Database

Normalization (questionsolves.com)
https://www.javatpoint.com/dbms-canonical-cover
91
ĐẠI HỌC FPT CẦN THƠ

Chapter 3 - Functional Dependencies

Uploaded by

Copyright:

Available Formats

Chapter 3 - Functional Dependencies

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

Chapter 3 - Functional Dependencies

Uploaded by

Copyright:

Available Formats

ĐẠI HỌC FPT CẦN THƠ

1 Understand what are functional dependencies

2 Understand the rules about FDs

33 Understand what are keys, super-keys

4 Understand what are closure-sets and how to determine them

6 Understand what is projecting FD’s

2 Rules about FDs

3 Key & Super-Key

4 Closure-sets and Algorithm for calculating the closure-set of a relation

5 Closing set of FD’s

A functional dependency (FD) is a constraint between

Given a relation R, a set of attributes X in R is said to

Customarily we call X the determinant set and Y the

A functional dependency FD is called trivial if Y is a subset

“If 2 tuples of R agree

X->Y  (t1(X) = t2(X)

? 1. The following FD is true or false:

From these rules, we can derive these secondary rules:

A set of one or more attributes {A1, A2, .., An} is

1. Those attributes functionally determine all

2. No proper subset of {A1, A2, .., An}

A set of attributes that contains a key is called a

A superkey is a set of attributes of a relation

There are many Super-key in the above schema:

Exercise: Can (title, year, starName, length, studioName)

There are many Super-key in the above schema:

Exercise: Can (title, year, starName, length, studioName)

Suppose: {A1,…, An} is a set of attributes; S is a set of FD’s.

Algorithm (courtesy [DBSC] Fig. 7.9 [p. 281])

• Step 1: Split all FDs in F such that: each FD has a single

Step 3: while (changes to result)

Suppose L contains those attributes that occur only on the left-hand

Suppose R contains those attributes that occur only on the right-hand

Suppose M contains those attributes that occur on both side of FDs

Lema 1: for every attribute A, if A is only in L then

Conclusion: we only focus only on L and M to

Let’s compute the attribute closures.

Find closure of FD:

1 Understand what are anomalies

2 Understand why must decompose a relation

3 Understand what are normal forms (1NF, 2NF, 3NF, BCNF)

4 Understand the good, bad and ugly of decomposition

2 What are decomposition?

3 Decomposition: The good, bad and the ugly

4 1NF, 2NF, 3NF, BCNF definition

5 Algorithms to decompose a relation into BCNF, 3NF

Which problems do you see in the relation?

Which problems do you see in the relation?

Problems such as redundancy that occur when we try

The accepted way to eliminate anomalies is the

How can you split the attributes of Movies relation

The redundancy is eliminated (the length of each film

Movies title year length genre studioName starName

Is relation Movies in BCNF? Why?

Movies title year length genre studioName starName

Is relation Movies1 in BCNF?

Relation Movies1 is in BCNF.

After we decompose a relation schema into BCNF,

But decomposition can also have some bad/ugly

If we check the projected FD’s in the relations of the