Chapter 3

Design Theory for Relational

Databases
第 3 章 关系数据库设计原则
3 Design Theory for Relational Database

Functional Dependencies
Normal forms
How to assure certain form
condition by decomposing
relational model?
3.1.1 Definition of Functional Dependency

X -> A is an assertion about a

relation R that whenever two tuples
of R agree on all the attributes of X,
then they must also agree on the
attribute A.
 Say “X -> A holds in R.”
X A
 Say “X functionally
determine A. t”
u

If t and u Then they

agree here, must agree
here
3.1.1 Definition of Functional Dependency

Corollary 1
A1A2…An → B1
A1A2…An → B2
…
A1A2…An → Bm
iff
A1A2…An → B1B2…Bm
Corollary 2
A→A
3.1.1 Definition of Functional Dependency

Three cases of asserting functional

dependencies
1.If any two tuples with the same
values in their A components also
have the same values in B, then A → B
holds.
A B C D
a1 b1 c1 d1 A->C ?
a1 b2 c1 d2
a2 b2 c2 d2
a2 b3 c2 d3
a3 b3 c2 d4
3.1.1 Definition of Functional Dependency

dependencies
Three cases of asserting functional
(Cont.)
2.If there are two tuples with the
same values in their A components
do not have the same values in B,
then A → B does not hold.
A B C D
a1 b1 c1 d1 C->A ?
a1 b2 c1 d2 BC->D ?
a2 b2 c2 d2
a2 b3 c2 d3
a3 b3 c2 d4
3.1.1 Definition of Functional Dependency

Three cases of asserting functional

dependencies (Cont.)
3.If any two tuples haven’t the
same values in their A components,
then A → B holds.
A B C D
a1 b1 c1 d1 D->A ?
a1 b2 c1 d2 D->B ?
a2 b2 c2 d3 D->C ?
a2 b3 c2 d4
a3 b3 c2 d5
3.1.1 Definition of Functional Dependency

Example: Which functional dependencies exist

in the relation Movies ( title, year, length,
filmtype, studioName, starName )?
title year → length filmType studioName ?
title year → starName ?
title → year length filmType studioName ?

title year length filmType studioName starName

Star Wars 1977 124 color Fox Carrie Fisher
Star Wars 1977 124 color Fox Mark Hamill
Star Wars 1977 124 color Fox Harrison
Mighty Ducks 1991 104 color Disney Ford
Wayne’s 1992 95 color Paramount Emilio
World 1992 95 color Paramount Estevez
Wayne’s Dana Carvey
World Mike Meyers
…
Movies
3.1.1 Definition of Functional Dependency

Consider the functional dependencies in

student ( stuid, name, gender, depid,
dorm, courseid, coursename, score ).
stuid → name gender ？
name → gender ?
stuid → score ?
stuid → courseid ?
stuid courseid → score ?
3.14.2 Keys of Relations

Key:
We say a set of one or more
attributes {A1, A2, ... ,An} is a key
for a relation if:
Those attributes functionally
determine all other attributes of the
relation. (superkey)
No proper subset of {A1,
A2, ... ,An} functionally determines
all other attributes of R. (minimal)
3.1.2 Keys of Relations

Key of the relation Movies ( title,

year, length, filmtype, studioName,
starName )
{title, year} ?
{title, year, starName} ?

If A→B holds in R(A,B,C), the keys

of R?
3.1.2 Keys of Relations

Candidate key:
All keys of a relation.
Primary key:
Sometimes a relation has more
than one key, and one of the
keys is designated as the
primary key.
3.1.3 Superkey

Superkeys:
Superset of a key.
A set of attributes that contains a key.
Those attributes functionally
determine all other attributes of the
relation.
 The relationship between keys and
superkeys:
 Keys are superkeys.
{title, year, starName} ?
 Some superkeys are not keys.
{title, year, length, starName} ?
Exercise

Suppose R is a relation with attributes

A1,A2, .. . , An. As a function of n, tell
how many superkeys R has, if:
a) The only key is A1.
b) The only keys are A1 and A2.
c) The only keys are {A1,A2} and
{A3,A4}.
d) The only keys are {A1,A2} and
{A1,A3}.
3.2 Rules About Functional Dependencies

What are rules about functional

dependencies? Why we need
them?
Suppose we are told of a set of
dependencies that a relation
satisfies, we can deduce other
dependencies by rules about
functional dependencies.
 The ability to discover additional
dependencies is essential when we
discuss the design of good relation
schemas.
3.2 Rules About Functional Dependencies

Some important rules about

functional dependencies:
The splitting/combining rule
The trivial-dependency rule
The transitive rule
Armstrong’s axioms
3.2.1 Reasoning About Functional Dependencies

Example: p90
If we are told that a relation R with
attributes A, B and C, satisfies the
functional dependencies A→B and B→C,
then we can deduce that R also
satisfies the dependency A→C.
Proof: Set (a,b1,c1) and (a,b2,c2) as the
tuples of R.
Since A→B, b1=b2
Since B→C, c1=c2
Then A→C
3.2.1 Reasoning About Functional Dependencies

The relationship between two sets

of functional dependencies:
If every relation instance that
satisfies all the dependencies in a
set of functional dependencies T
also satisfies all the dependencies
in a set of functional dependencies
S, we say that S follows from T.
 If S follows from T and T follows
from S, then S and T are equivalent.
3.2.2 The Splitting/Combining Rule

Splitting/Combining Rule:
A1A2…An → B1B2…Bm
is a shorthand for A1A2…An → B1
A1A2…An → B2
…
A1A2…An → Bm

There is no splitting rule or combining rule for left

sides.
3.2.3 Trivial Dependencies
Trivial dependency:
 A functional dependency A1A2...An→B
is said to be trivial if B is one of the A’s.
 Every trivial dependency holds in every
relation.
 A dependency A1A2...An→B1B2...Bm is
Trivial if the B’s are a subset of the A’s.
among
Nontrivial if at least one of the B’s is not
the A’s.
also
Completely nontrivial if none of the B’s is
one of the A’s.
Example:
 title year→year length is nontrivial
 title year→length is completely
nontrivial
3.2.3 Trivial Dependencies

The trivial-dependency
rule: A C

the
We can remove from
right side of a
B

functional t
dependency those
attributes that appear
on the left. u
That is:
 The functional
dependency If t and u Then they
A1A2...An→B1B2..Bm agree in must agree
is equivalent to the A’s in the B’s
A1A2...An→C1C2...Ck,
So surely they
where the C’s are all
those B’s that are not agree in the C’s
also A’s.
3.2.4 Computing the Closure of Attributes

The closure of attributes:

 Suppose {A1,A2,...,An} is a set of
attributes and S is a set of functional
dependencies. The closure of
{A1,A2,...,An} under the dependencies
in S is the set of attributes B such that
every relation that satisfies all the
dependencies in set S also satisfies
A1A2...An→B. That is, A1A2...An→B
follows from the dependencies of S.
 We denote the closure of a set of
attributes {A1A2...An} by {A1A2...An}
+
.
 A1A2...An are always in {A1A2...An}+.
 If A1A2...An→X, then XB.
3.2.4 Computing the Closure of Attributes

How to compute the closure of attributes?

An easier way to test is to compute
the closure of Y, denoted Y +.
Basis: Y + = Y.
Induction: Look for an FD’s left side
X that is a subset of the current Y +.
If the FD is X -> A, add A to Y +.

Y+ X A

new Y+
3.2.4 Computing the Closure of Attributes

Example:
Let us consider a relation with
schema R(A,B,C,D,E,F) and a set of
functional dependencies
S: {BC→AD, AB→C, D→E, CF→B}
Please computer {A, B}+.
3.2.4 Computing the Closure of Attributes

Example:
Let us consider a relation with
schema R(A,B,C,D,E,F) and a set of
functional dependencies
S: {AB→C, BC→AD, D→E, CF→B}
Please test whether AB→D and
D→A follow from the dependencies
of S?
3.2.4 Computing the Closure of Attributes

Closures and keys:

{A1,A2,...,An}+ is the set of
all attributes if and only if A1,
A2, ... ,An is a superkey for
the relation.
3.2.5 Why the Closure Algorithm Works

Why the closure algorithm works?

Why the closure algorithm claims
only true FD’s?
Why the closure algorithm
discovers all true FD’s?
3.2.6 The Transitive Rule

The transitive rule:

 Cascade two functional
dependencies.
 If A1A2...An→B1B2...Bm and
B1B2...Bm→C1C2...Ck hold in relation
R, then A1A2...An→C1C2...Ck also
holds in R.
Example: MovieStudio ( title, year, length,
fileType, studioName, studioAddr)
 title, year → studioName
 studioName → studioAddr
 then title, year → studioAddr
3.2.7 Closing Sets of Functional Dependencies

We can derive a new set of dependencies

from a set of given dependencies using
rules about functional dependencies.
 Any set of given dependencies from which
we can infer all the dependencies for a
relation will be called a basis for that
relation.
 A relation may have several bases.
 If no proper subset of the dependencies in
a basis can also derive the complete set of
dependencies, then we say the basis is
minimal.
 A relation may have several minimal bases.
3.2.7 Closing Sets of Functional Dependencies

Example: p80
Consider a relation with schema R
(A,B,C) and a set of dependencies
F: { A → B, A → C, B → A, B → C, C →
A, C → B }
Then the minimal bases are {A→B,
B→A, B→C, C→B}, {A→B, B→C, C→
A} and so on.
3.2.7 Closing Sets of Functional Dependencies

Armstrong’s axioms:
Reflexivity
If {B1,B2,…,Bm}{A1,A2,…,An}, then
A1A2…An→B1B2…Bm. ( trivial)
Augmentation
If A1A2…An→B1B2…Bm, then A1A2…
AnC1C2…C→B1B2…BmC1C2…Ck for any
set of attributes C1,C2,…,Ck.
Transitivity
If A1A2…An→B1B2…Bm and B1B2…
Bm→C1C2…Ck, then A1A2…An→C1C2…
Ck.
Example

R(A,B,C,D)
Consider a relation with schema
and functional dependencies
AB → C, C → D and D → A.
1. What are all the nontrivial functional
dependencies that follow from the
given dependencies?
2. What are all the keys of R?
3. What are all the superkeys for R that
are not keys?
4. Does B->C follow from the given FDs?
5. Does C->A follow from the given FDs?
3.3 Design of Relational Database Schemas

Causes of redundancy:
 A fact is repeated in more than one
tuple.
 The most common cause for the
redundancy: attempts to group into one
relation both single-value and multivalued
properties of an object.
title year length filmType studioName starName
Movies
Star Wars 1977 124 color Fox Carrie Fisher
Star Wars 1977 124 color Fox Mark Hamill
Star Wars 1977 124 color Fox Harrison Ford
Mighty Ducks 1991 104 color Disney Emilio Estevez
Wayne’s World 1992 95 color Paramount Dana Carvey
Wayne’s World 1992 95 color Paramount Mike Meyers
3.3 Design of Relational Database Schemas

How to solve this redundancy?

1.Explore in more detail the problems
that arise when our schema is flawed.
2.Introduce the idea of “decomposition”,
breaking a relation schema into two
smaller schemas.
3. Introduce “Boyce-Codd normal form”,
or “BCNF”, a condition on a relation
schema that eliminates these problems.
4. Explain how to assure the BCNF
condition by decomposing relation
schemas.
5. Relax BCNF requirement slightly, and
introduce “Third normal form”, or “3NF”.
6. Introduce “1NF” and “2NF”.
3.3.1 Anomalies

Goal of relational schema design is

to avoid anomalies.
Redundancy : information may be
repeated unnecessarily in several
tuples.
 Update anomaly : one occurrence
of a fact is changed, but not all
occurrences.
 Deletion anomaly : valid fact is
lost when a tuple is deleted.
3.3.1 Anomalies

title year length filmType studioName starName

Star Wars 1977 124 Color Fox Carrie Fisher

Star Wars 1977 124 Color Fox Mark Hamill

Star Wars 1977 124 Color Fox Harrison Ford

Mighty Ducks 1991 104 Color Disney Emilio Estevez

Wayne’s World 1992 95 Color Paramount Dana Carvey

Wayne’s World 1992 95 Color Paramount Mike Meyers

3.3.2 Decomposing Relations

Decomposing relations:
 Given a relation R with schema
{A1,A2,...,An}, we may decompose R into
two relations S and T with schemas
{B1,B2,...,Bm} and {C1,C2,...,Ck}, such that
 {A1,A2,...,An} =
{B1,B2,...,Bm}∪{C1,C2,...,Ck}.
 The tuples in relation S are the projections
onto {B1,B2,...,Bm} of all the tuples in R.
 The tuples in relation T are the projections
onto {C1,C2,...,Ck} of all the tuples in R.
3.3.2 Decomposing Relations

Projection:
For each tuple t in the current
instance of R, take the components
of t in the attributes B1, B2, ...,Bm.
Keep only one copy of each tuple.
3.3.2 Decomposing Relations

Decompose the relation Movies (title, year, length,

filmType, studioName, starName) into two relations:

Movie1 (title, year, length, filmType, studioName)

title year length filmType studioName
Star Wars 1977 124 Color Fox
Mighty Ducks 1991 104 Color Disney
Wayne’s World 1992 95 Color Paramount

Movie2 (title, year, starName)

title year starName

Star Wars 1977 Carrie Fisher

Star Wars 1977 Mark Hamill
Star Wars 1977 Harrison Ford
Mighty Ducks 1991 Emilio Estevez
Wayne’s World 1992 Dana Carvey
Wayne’s World 1992 Mike Meyers
3.3.3 Boyce-Codd Normal Form

Under BCNF, the anomalies can

be guaranteed not to exist.

We say a relation R is in BCNF if

whenever X ->A is a nontrivial FD that
holds in R, X is a superkey.
Remember: nontrivial means A is
not a member of set X.

Remember: a superkey is any

superset of a key (not necessarily a
proper superset).
3.3.3 Boyce-Codd Normal Form

R in BCNF:
1) There is no nontrivial dependency
in R. (none but trivial dependency)

2) The left side of every nontrivial

functional dependency must
contain a key. (superkey)
3.3.3 Boyce-Codd Normal Form

Example: Is student ( stuid, couid,

score, depid, dean) in BCNF?

1) find out all keys

2) check the left side of all nontrivial

functional dependencies
3.3.3 Boyce-Codd Normal Form

Any two-attribute relation is in BCNF

Supposing that the attributes are A and B,
there are four cases to consider:
1)There are no nontrivial functional dependencies.

2) A→B holds, but B→A does not hold. A is the

only key, and each nontrivial dependency
contains key on the left.
3) B→A holds, but A→B does not hold. B is the only key,
and each nontrivial dependency contains key on the
left.

4) Both A→B and B→A hold, then both A and

B are keys. Surely any dependency has
at least one of these on the left.
3.3.3 Boyce-Codd Normal Form

There may be several keys for a

relation, and the BCNF condition
only requires some key be
contained in the left side of any
nontrivial dependency.
3.3.4 Decomposition into BCNF

into
We can break any relation schema
a collection of subset of its
attributes with the following important
properties:
 These subsets are the schemas of
relations in BCNF.
 The data in the original relation is
represented faithfully by the data in
the relations that are the result of
the decomposition, that is, we need
to be able to reconstruct the original
relation exactly from the
decomposed relations.
3.3.4 Decomposition into BCNF

Decomposition strategy:

1) Find a BCNF-violating dependency

A1A2...An→B1B2...Bm.
2) Decompose the relation R into two
relations:
R1(A1,A2,...An,B1,B2...Bm)
R2(A1,A2,...,An, all the other
attributes of R)
3) Repeat decomposition process till
all relations are in BCNF.
3.2.8 Projecting Functional Dependencies

Algorithm:
 Consider each set of attributes X
that is contained in the set of
attributes of S. Compute X+. Then
for each attribute B such that
 B is an attribute of S,
 B is in X+, and
 B is not in X,
 the functional dependency X→B
holds in S.
3.2.8 Projecting Functional Dependencies

Suppose a relation has schema R(U) and

a set of dependencies F.
If S is a subset of R.
We need find what functional
dependencies still hold in S.
3.2.8 Projecting Functional Dependencies

Example:
 Let R have schema R(A,B,C,D), and suppose
the functional dependencies A→B and B→C
are given for R.
 Let S(A,C) be one of the relation in a
decomposition of R. Please compute the
dependencies that hold in S.

{A}+={A,B,C}, then A→C holds in S.

{C}+={C}
{A,C}+={A,B,C}
3.2.8 Projecting Functional Dependencies
Example:
Consider R(A,B,C,D,E) decomposed
into S(A,B,C) and another relation.
Let the functional dependencies
of R be A→D, B→E and DE→C.
Please compute the dependencies
that hold in S.
{A}+={A,D}
{B}+={B,E}
{C}+={C}
{A,B}+={A,B,C,D,E}, then AB→C holds in
S
{A,C}+={A,C,D}
{B,C}+={B,C,E}
{A,B,C}+={A,B,C,D,E}
3.3.4 Decomposition into BCNF

Example: R(stuid, couid, score,

depid, dean) is not in BCNF, then we
decompose it.
1.stuid→depid, head is a BCNF violation.
2.Decompose R into: R1(stuid, depid, dean)
R2(stuid, couid, score)
3.depid→dean is a BCNF violation in R1.
4.Decompose R1 into: R11(stuid, depid)
R12(depid, dean)
5.Finally, we decompose R into (stuid,
depid), (depid, dean) , (stuid, couid, score).
3.4 Decomposition: The Good, Bad, and Ugly

decomposition:
Three distinct properties of a

Elimination of anomalies.
Recoverability of information.
Preservation of dependencies.
3.4.1 Recovering Information from a Decomposition

If we decompose relations in a way that

is not based on a functional dependency,
then we might not be able to recover the
original relation.
3.4.1 Recovering Information from a Decomposition

Example: p95
If we decompose R
A B C
1 2 3
4 2 5
into
R1(A,B) R2(B,C)
A B B C
1 2 2 3
4 2 2 5
Reconstruct R by joining
A B C
1 2 3
1 2 5
4 2 3
4 2 5
3.4.4 Dependence Preservation

 Some relations are not in BCNF, but

they can not decompose further.
Example: p101
Booking (movie, theater, city)
A tuple (m,t,c) means that the movie
with title m is currently being shown at
theater t in city c.
Booking has the following dependencies:
theater → city
movie city → theater
Then there are two keys: {movie, city}
and {movie, theater}
theater → city is a BCNF violation.
3.4.4 Dependence Preservation

Can we decompose Booking into {theater,city}

and {theater, movie}?
Suppose these two relations as follow:
theate city theater movie
r Guild The Net
Guild Menlo Park Park The Net
Park Menlo Park
Reconstruct Booking by joining:
theater city movie
Guild Menlo Park The Net
Park Menlo Park The Net

movie city→theater does not hold in Booking

3.5 Third Normal Form

3NF relax the BCNF

requirement, so that the
relation can be decomposed
without losing FD’s.
3.5.1 Definition of Third Normal Form

Third normal form(3NF):

A relation R is in third normal
form (3NF), iff whenever
A1A2...An→B is a nontrivial
dependency, either
{A1,A2,...,An} is a superkey, or B
is a member of some key ( key
attribute).
3.5.2 The Synthesis Algorithm for 3NF Schemas

There are two important properties

of a decomposition:
 Lossless Join : it should be
possible to project the original
relations onto the decomposed
schema, and then reconstruct the
original.
 Dependency Preservation : it
should be possible to check in the
projected relations whether all
the given FD’s are satisfied.
3.5.2 The Synthesis Algorithm for 3NF Schemas

We can get (1) with a BCNF

decomposition.
We can get both (1) and (2) with a
3NF decomposition.
But we can’t always get (1) and (2)
with a BCNF decomposition.
3.5.2 The Synthesis Algorithm for 3NF Schemas

Decomposition strategy:

1) Find a minimal basis for F (the set

of FD’s), say G.
2) For each FD XA in G, use XA as
the schema of one of the relations
in the decomposition.
3) If none of the sets of relations
from Step 2 is a superkey for R,
add another relation whose
schema is a key for R.
3.5.2 The Synthesis Algorithm for 3NF Schemas
Example: p103
Consider the relation R(A, B, C, D,
E) with FD’s ABC, C B, and A D.
1.{ABC, C B, and A D} is a
minimal basis.
2.So we get S1(A,B,C), S2(B,C), and
S3(A,D). S2 is a proper subset of
S1, so S2 is dropped.
3. There are two keys: {A,B,E},
{A,C,E}. Neither of them is a subset
of S1 or S2, so we add one of them.
4. S1(A,B,C), S3(A,D) and S4(A,B,E)
3.5.4 Why the 3NF Synthesis Algorithm Works

1.Lossless Join: use the chase to

show that the row for the
relation that contains a key can
be made all-unsubscripted
variables.
2. Dependency preservation: each
FD from a minimal basis is
contained in a relation, thus
preserved.
3. 3NF: a property of minimal
bases.
1NF and 2NF

First normal form(1NF):

 Each component of any tuple
must be atomic.
1NF and 2NF

Second normal form(2NF):

For any nontrivial dependency
A1A2...An→B, if B is not a member
of any key, and A1A2...An is not a
proper subset of any key 。
Example

R(A, B, C, D) with functional

dependencies AB → C, C → D, D → A :
Indicate all the BCNF violations.
Decompose the relations, as
necessary, into collection of
relations that are in BCNF.
 Indicate all the 3NF violations.
 Decompose the relations, as
necessary, into collections of
relations that are in 3NF.
QUIZ

Consider a relation with schema R(A,B,C,D)

and functional dependencies A → C and B →C.
1.What are all the nontrivial functional
dependencies that follow from the given
dependencies?
2. What are all the keys of R?
3. What are all the superkeys for R that are
not keys?
4. Indicate all the BCNF violations.
5. Decompose the relations, as necessary,
into collection of relations that are in BCNF.
6. Indicate all the 3NF violations.
7. Decompose the relations, as necessary,
into collections of relations that are in 3NF.
Example

Find the highest normal form of

Students(Sid, Cid, score, depid, dorm)
1NF

Find the highest normal form of Movies

(title, year, length, filmType, studioName,
starName)
1NF

Find the highest normal form of MovieStudio

(title, year, length, filmType, studioName,
2NF
studioAddr)
3.6 Multivalued Dependencies

Causes of multivalued dependencies:

 Two attributes or sets of
attributes are independent of one
another.
 Attribute independence may bring
on redundancy.
 It can not be represented by
functional dependencies.
3.6 Multivalued Dependencies

Multivalued dependencies and

functional dependencies:
Multivalued dependencies are the
generalization of functional
dependencies, and functional
dependencies are special case of
multivalued dependencies.
 Every functional dependency is a
multivalued dependency.
3.6 Multivalued Dependencies

How to solve this redundancy?

Attribute independence and its
consequent redundancy
Definition of multivalued
dependencies
Reasoning about multivalued
dependencies
Fourth normal form
Decomposition into 4NF
Relationships among normal forms
3.6.1 Attributes Independence and Its Consequent
Redundancy
Two multivalued attributes or relationships in a relation
will bring on redundancy, but the relation is in BCNF.
Example: p106 Star (name, street, city, title, year)
name street city title year
Carrie 123 Maple Hollywoo Star Wars 197
Fisher St. d 7
Carrie 5 Locust Ln. Mailbu Star Wars 197
Fisher 7
Carrie 123 Maple Hollywoo Empire Strikes 198
Fisher St. d Back 0
Carrie 5 Locust Ln. Mailbu Empire Strikes 198

 The quantity of tuples = n (addresses) * m (movies)

Fisher Back 0

 nontrivial functional dependencies

Carrie 123 Maple Hollywoo Return of Jedi 198
FisherNo St. d 3
 In BCNF.
Carrie
Fisher
5 Locust Ln. Mailbu Return of Jedi 198
3
3.6.1 Attributes Independence and Its Consequent
Redundancy

Attribute independence:
Two sets of attributes have no
relationship in a relation, and they
have sets of values that appear in
all possible combinations.
3.6.2 Definition of Multivalued Dependencies

A multivalued dependency (MVD)

on R (A,B,Z), A ->->B , says that if two
tuples of R agree on all the attributes
of A, then their components in B may
be swapped, and the result will be
two tuples that are also in the
relation.
i.e., for each value of A, the values
of B are independent of the values of
Z.
3.6.2 Definition of Multivalued Dependencies

For each pair of tuples t and u of

relation R that agree on all the A’s,
we can find in R is some tuple v that
agrees:
 with both t and u on the A’s
 with t on the B’s, and A B Z

 with u on all t
|| ||
attributes of R v
that are not among || ||

the A’s or B’s. u

Then A →→ B holds.
3.6.2 Definition of Multivalued Dependencies

Note that we can use this rule with t and u

interchanged, to infer the existence of a fourth tuple w that
agrees with u on the B’s and with t on the other attributes.
A B Z
name street city title year
t Carrie 123 Maple Hollywoo Star Wars 197
Fisher St. d 7
w Carrie 5 Locust Ln. Mailbu Star Wars 197
Fisher 7
v Carrie 123 Maple Hollywoo Empire Strikes 198
Fisher St. d Back 0
u Carrie 5 Locust Ln. Mailbu Empire Strikes 198
Fisher Back 0
A multivalued dependency name→→ street city holds.
Carrie 123 Maple Hollywoo Return of Jedi 198
And name →→
Fisher St. title year holds.
d 3
Carrie 5 Locust Ln. Mailbu Return of Jedi 198
Fisher 3
3.6.2 Definition of Multivalued Dependencies

Some cases of multivalued dependency:

When the values of A’s attributes
are fixed, then the values of B’s
attributes can be combined with
the values of all the other attributes
freely, then A →→ B holds.
If A → B holds, then A →→ B holds.
If all the attributes of R are among
A’s and B’s, then A →→ B holds.
3.6.2 Definition of Multivalued Dependencies

Example:
department →→ class ?
class student
department
01 11 S1

01 11 S2

01 11 S3

01 12 S4

01 12 S5
3.6.3 Reasoning About Multivalued Dependencies

Trivial dependencies rule:

 If multivalued dependency A →→ B
holds for some relation, then so
does A →→ C where the C’s are the
B’s plus one or more of the A’s, and
so does A →→ D where the D’s are
those B’s that not among the A’s.

Transitive rule:
 If A →→ B and B →→ C hold for
some relation, then A →→ C holds.
3.6.3 Reasoning About Multivalued Dependencies

Note that multivalued dependencies

do not obey the splitting/combining
rule.
Example: name →→ street city holds,
but name →→ street does not hold.
3.6.3 Reasoning About Multivalued Dependencies

Functional dependencies promotion:

 Every functional dependency is a
multivalued dependency. If A → B,
then A →→ B.
 If X ->Y, then swapping Y ’s
between two tuples that agree on X
doesn’t change the tuples.
 Therefore, the “new” tuples are
surely in the relation, and we know X
->->Y.
3.6.3 Reasoning About Multivalued Dependencies

Complementation rule:
If A →→ B for a relation R, then A
→→ C where C’s are all attributes
of R not among the A’s and B’s.
Example: name →→ street city
holds, then name →→ title year
holds.
3.6.3 Reasoning About Multivalued Dependencies

More trivial MVD’s:

If all the attributes of relation R
are {A1,A2,…,An,B1,B2,…,Bm},
then
A1A2…An →→ B1B2…Bm
3.6.4 Fourth Normal Form

Nontrivial multivalued dependencies:

 A →→ B for a relation R(A,B,Z) is a
nontrivial multivalued dependency if:
 none of the B’s is among the A’s.
A∩B ＝ Φ
 not all the attributes of R are
among the A’s and B’s. A∪B≠U

Fourth normal form (4NF):

 A relation R in 4NF if whenever A
→→ B is a nontrivial multivalued
dependency, {A} is a superkey.
3.6.4 Fourth Normal Form

R in 4NF:
 There is no nontrivial multivalued dependency
in R. (none but trivial multivalued dependency)
 The left side of every nontrivial multivalued
dependency must contain a key.

Example: Star ( name, street, city, title,

year )
There is a nontrivial multivalued
dependency name →→ street city with the
left side not a superkey, then the relation
is not in 4NF. But it is in BCNF.
 If we add an attribute gender?
3.6.4 Fourth Normal Form

 Note that the notions of keys and

superkeys depend on functional
dependencies only, whereas
multivalued dependencies does not
change the definition of “key”.

Note that every functional

dependency is a multivalued
dependency, so every BCNF violation
is also a 4NF violation, and every
relation that is in 4NF is in BCNF.
3.6.5 Decomposition into Fourth Normal Form

The 4NF decomposition algorithm is

quite analogous to the BCNF
decomposition algorithm.
 Find a 4NF-violating multivalued
dependency A1A2...An→B1B2...Bm.
 Decompose the relation R into two
relations:
R1(A1,A2,...An,B1,B2...Bm)
R2(A1,A2,...,An, all the other
attributes of R)
Repeat decomposition process till
all relations are in 4NF.
3.6.5 Decomposition into Fourth Normal Form

Example: Star ( name, street, city, title, year )

1. name →→ street city is a 4NF violation
2. decompose Star into: R1 ( name, street, city )
R2 ( name, title, year )
There is no 4NF violation any more.

name street city

Carrie Fisher 123 Maple St. Hollywood
Carrie Fisher 5 Locust Ln. Mailbu

name title year

Carrie Fisher Star Wars 1977
Carrie Fisher Empire Strikes Back 1980
Carrie Fisher Return of Jedi 1983
3.6.6 Relationships Among Normal Forms

Relations
in 1NF Atomicity
Relations
in 2NF

Relations
in 3NF

Functional dependencies
Relations
in BCNF

Relations
in 4NF Multivalued dependencies
3.6.6 Relationships Among Normal Forms

property 3NF BCNF 4NF

Eliminates redundancy most yes yes

due to functional
dependencies

Eliminates redundancy no no yes

due to multivalued
dependencies

Preserves functional yes maybe maybe

dependencies

Preserves multivalued maybe maybe maybe

dependencies
Exercise

Customer (custid, name, prov, city, phone, company)

Merchandise (merid, factory, type, spec, price, desc)

Salesman (empid, idno, name, gender, phone, deptid)

Department (deptid, name, managerid)

Salesorder (orderno, signdate, empid, custid)

Salesitem (orderno, lineno, merid, unitprice,

quantity)
Exercise

Based on the meaning above, find

the highest normal form of each of
the following relations.
R1(empid, name, custid, custname)
R2(empid, idno, name, gender,
phone, deptid, deptname, ismanager)
R3(orderno, signdate, empid, custid,
merid, unitprice, quantity)
Exercise

R4(empid, name, orderno, signdate,

total)
R5(empid, custid, merid)
R6(empid, orderno, signdate, custid,
total)