Advanced Normalization
Transparencies
Objectives
How inference rules can identify a set of all
functional dependencies for a relation.
How Inference rules called Armstrong’s axioms
can identify a minimal set of useful functional
dependencies from the set of all functional
dependencies for a relation.
2
Objectives
Normal forms that go beyond Third Normal
Form (3NF), which includes Boyce-Codd
Normal Form (BCNF), Fourth Normal Form
(4NF), and Fifth Normal Form (5NF).
How to identify Boyce–Codd Normal Form
(BCNF).
How to represent attributes shown on a report
as BCNF relations using normalization.
3
Objectives
Concept of multi-valued dependencies and
Fourth Normal Form (4NF).
The problems associated with relations that
break the rules of 4NF.
How to create 4NF relations from a relation,
which breaks the rules of to 4NF.
4
Objectives
Concept of join dependency and Fifth Normal
Form (5NF).
The problems associated with relations that
break the rules of 5NF.
How to create 5NF relations from a relation,
which breaks the rules of 5NF.
5
More on Functional Dependencies
The complete set of functional dependencies
for a given relation can be very large.
Important to find an approach that can reduce
the set to a manageable size.
6
Inference Rules for Functional Dependencies
Need to identify a set of functional
dependencies (represented as X) for a relation
that is smaller than the complete set of
functional dependencies (represented as Y) for
that relation and has the property that every
functional dependency in Y is implied by the
functional dependencies in X.
7
Inference Rules for Functional Dependencies
The set of all functional dependencies that are
implied by a given set of functional
dependencies X is called the closure of X,
written X+ .
A set of inference rules, called Armstrong’s
axioms, specifies how new functional
dependencies can be inferred from given ones.
8
Inference Rules for Functional Dependencies
Let A, B, and C be subsets of the attributes of
the relation R. Armstrong’s axioms are as
follows:
(1) Reflexivity
If B is a subset of A, then A → B
(2) Augmentation
If A → B, then A,C → B,C
(3) Transitivity
If A → B and B → C, then A → C
9
Inference Rules for Functional Dependencies
Further rules can be derived from the first
three rules that simplify the practical task of
computing X+. Let D be another subset of the
attributes of relation R, then:
(4) Self-determination
A→A
(5) Decomposition
If A → B,C, then A → B and A → C
10
Inference Rules for Functional Dependencies
(6) Union
If A → B and A → C, then A → B,C
(7) Composition
If A → B and C → D then A,C → B,D
11
Minimal Sets of Functional Dependencies
A set of functional dependencies Y is covered
by a set of functional dependencies X, if every
functional dependency in Y is also in X+; that
is, every dependency in Y can be inferred from
X.
A set of functional dependencies X is minimal if
it satisfies the following conditions:
– Every dependency in X has a single attribute
on its right-hand side.
12
Minimal Sets of Functional Dependencies
– We cannot replace any dependency A → B in
X with dependency C → B, where C is a
proper subset of A, and still have a set of
dependencies that is equivalent to X.
– We cannot remove any dependency from X
and still have a set of dependencies that is
equivalent to X.
13
Boyce–Codd Normal Form (BCNF)
Based on functional dependencies that take
into account all candidate keys in a relation,
however BCNF also has additional constraints
compared with the general definition of 3NF.
Boyce–Codd normal form (BCNF)
– A relation is in BCNF if and only if every
determinant is a candidate key.
14
Boyce–Codd Normal Form (BCNF)
Difference between 3NF and BCNF is that for a
functional dependency A → B, 3NF allows this
dependency in a relation if B is a primary-key
attribute and A is not a candidate key.
Whereas, BCNF insists that for this
dependency to remain in a relation, A must be
a candidate key.
Every relation in BCNF is also in 3NF.
However, a relation in 3NF is not necessarily in
BCNF.
15
Boyce–Codd Normal Form (BCNF)
Violation of BCNF is quite rare.
The potential to violate BCNF may occur in a
relation that:
– contains two (or more) composite candidate
keys;
– the candidate keys overlap, that is have at
least one attribute in common.
16
Review of Normalization (UNF to BCNF)
17
Review of Normalization (UNF to BCNF)
18
Review of Normalization (UNF to BCNF)
19
Review of Normalization (UNF to BCNF)
20
Fourth Normal Form (4NF)
Although BCNF removes anomalies due to
functional dependencies, another type of
dependency called a multi-valued dependency
(MVD) can also cause data redundancy.
Possible existence of multi-valued dependencies
in a relation is due to 1NF and can result in
data redundancy.
21
Fourth Normal Form (4NF)
Multi-valued Dependency (MVD)
– Dependency between attributes (for
example, A, B, and C) in a relation, such
that for each value of A there is a set of
values for B and a set of values for C.
However, the set of values for B and C are
independent of each other.
22
Fourth Normal Form (4NF)
MVD between attributes A, B, and C in a
relation using the following notation:
A −>> B
A −>> C
23
Fourth Normal Form (4NF)
A multi-valued dependency can be further
defined as being trivial or nontrivial.
A MVD A −>> B in relation R is defined as
being trivial if (a) B is a subset of A or (b) A
B = R.
A MVD is defined as being nontrivial if
neither (a) nor (b) are satisfied.
A trivial MVD does not specify a constraint
on a relation, while a nontrivial MVD does
specify a constraint.
24
Fourth Normal Form (4NF)
Defined as a relation that is in Boyce-Codd
Normal Form and contains no nontrivial multi-
valued dependencies.
25
4NF - Example
26
Fifth Normal Form (5NF)
A relation decompose into two relations must
have the lossless-join property, which ensures
that no spurious tuples are generated when
relations are reunited through a natural join
operation.
However, there are requirements to decompose
a relation into more than two relations.
Although rare, these cases are managed by join
dependency and fifth normal form (5NF).
27
Fifth Normal Form (5NF)
Defined as a relation that has no join
dependency.
28
5NF - Example
29
5NF - Example
30
