Database Design

Normalization
 Database Design
1. Requirements Analysis: in this step, we must point out
2. Conceptual Database Design: develop a high-level description of the data to be
stored in the database, along with the constraints that are known to hold on this data.
3. Logical Database Design: convert the conceptual database design into a database
schema within the data model of the chosen DBMS.
4. Schema Refinement: the schemas developed in step 3 are analyzed for potential
problems, then are normalized.
5. Physical Database Design: potential workloads and access patterns are simulated
to identify potential weaknesses in the conceptual database. This will often cause the
creation of additional indices and/or clustering relations.
6. Security Design: Different user groups are identified and their different roles are
analyzed so that access patterns to the data can be defined. 2
 Normalization
Normalization is a technique for producing a set of relations with
desirable properties, given the data requirements of the enterprise
being modeled.
The process of normalization was first developed by Codd in 1972.
Normalization is often performed as a series of tests on a relation to
determine whether it satisfies or violates the requirements of a given
normal form.
Codd initially defined three normal forms called first (1NF), second
(2NF), and third (3NF). Boyce and Codd together introduced a
stronger definition of 3NF called Boyce-Codd Normal Form (BCNF) in
1974. 3
 Normalization
Attributes may be added to a relational schema based largely on the
common sense of the database designer, or by mapping the relational
schema from an ERD.
A formal method is often required to help the database designer identify
the optimal grouping of attributes for each relation schema.
The process of normalization is a formal method that identifies relations
based on their primary or candidate keys and the functional
dependencies among their attributes.
Normalization is a series of tests, which can be applied to individual
relations so that a relational schema can be normalized to a specific
form to prevent the possible occurrence of update anomalies.
4
 Why Normalization?
The major aim of relational database design is to group attributes into
relations to minimize data redundancy and thereby reduce the file
storage space required by the implemented base relations, and to avoid
any anomaly.
In the following relation schema, anomalies may appear during any data
manipulation processes: modification, deletion, addition

5
 The Need of Normalization
staffbranch

staff# sname position salary branch# baddress

SL21 Kristy manager 30000 B005 22 Deer Road

SG37 Debi assistant 12000 B003 162 Main Street

SG14 Alan supervisor 18000 B003 163 Main Street

SA9 Traci assistant 12000 B007 375 Fox Avenue

SG5 David manager 24000 B003 163 Main Street

SL41 Anna assistant 10000 B005 22 Deer Road

In the “staffbranch” relation, it is hard to avoid anomalies during data

manipulation processes
6
 The Need of Normalization
Staff Branch

staff# sname position salary branch# branch# baddress

SL21 Kristy manager 30000 B005 B005 22 Deer Road

SG37 Debi assistant 12000 B003 B003 163 Main Street

SG14 Alan supervisor 18000 B003
B007 375 Fox Avenue
SA9 Traci assistant 12000 B007
SG5 David manager 24000 B003
SL41 Anna assistant 10000 B005

In the two separated relations “Staff” and “Branch” above, the

redundancy is removed, and all anomalies can be avoided.

7
 Normalization
The examples of three types of update anomalies suffered by the
staffbranch relation demonstrate that its decomposition into the Staff
and Branch relations avoids such anomalies.
Two important properties associated with the decomposition of a larger
relation into a set of smaller relations must be considered:
• The lossless-join property ensures that any instance of the original relation can
be identified from corresponding instances of the smaller relations.
• The dependency preservation property ensures that a constraint on the original
relation can be maintained by simply enforcing some constraint on each of the
smaller relations. In other words, the smaller relations do not need to be joined
together to check if a constraint on the original relation is violated.
8
 The Lossless-join Property
SP S1 S2
s# p# qty s# qty p# qty
S1 P1 10 Decomposition S1 10 P1 10
S2 P2 50 S2 50 P2 50
S3 P3 10 S3 10 P3 10

S1  S2
s# p# qty
S1 P1 10
These are extraneous tuples which did not
S1 P3 10 appear in the original relation. However, now we
S2 P2 50 can’t tell which are valid and which aren’t. Once
the decomposition occurs the original SP relation
S3 P1 10
is lost.
S3 P3 10
9
 Preservation of Functional Dependencies
Example
R = (A, B, C)
F = {AB → C, C → A}
If R is decomposed into two relations RR = {(B, C), (A, C)}
Clearly C → A can be enforced on schema (A, C).
How can AB → C be enforced without joining the two relation schemas
in K?
Answer, it can’t, therefore the functional dependencies are not preserved
in K. 10
 Functional Dependency
All four of the normal forms, 1NF, 2NF, 3NF, BCNF, are based on
functional dependencies among the attributes of a relation.
A functional dependency describes the relationship between attributes
in a relation.
For example, if A and B are attributes or sets of attributes of relation R, B is
functionally dependent on A (denoted A → B), if each value of A is associated
with exactly one value of B.

A functional dependency is a property of the semantics of the

attributes in a relation, that indicate how attributes relate to one
another.
A functional dependency specifies a constraint between the
11
attributes.
 Functional Dependency
Consider a relation with attributes A and B:
If attribute B is functionally dependent on attribute A (denoted A → B),
then if we know the value of A, we will find only one value of B in all of
the tuples that have a given value of A, at any moment in time.
Note: for a given value of B there may be several different values of A.
B is functionally
A B
dependent on A

The determinant of a functional dependency is the attribute or group of

attributes on the left-hand side of the arrow in the functional
dependency. The consequent of a FD is the attribute or group of
12
attributes on the right-hand side of the arrow.
 Functional Dependency
Revisit the Staff relation: staff# sname position salary branch#

The functional dependency staff# → position holds on this relation

instance since there is a 1:1 relationship from staff# to position (for
each staff member there is only one position).
Here, the reverse functional dependency position → staff# does not
hold, since the relationship between position and staff# is 1:M (there
are several staff numbers associated with a given position).
For the purposes of normalization we are interested in identifying
functional dependencies between attributes of a relation that have a
1:1 relationship.
13
 Functional Dependency
A functional dependency is a property of a relational schema (its
intension) and not a property of a particular instance of the schema
(extension).
When identifying fds between attributes in a relation it is important to
distinguish clearly between the values held by an attribute at a given
point in time and the set of all possible values that an attributes may
hold at different times.
This represents the types of integrity constraints that we need to
identify. Such constraints indicate the limitations on the values that a
relation can legitimately assume. In other words, they identify the legal
instances which are possible.
14
 Functional Dependency
Let’s identify the functional dependencies that hold in the relation
staffbranch. staff# sname position salary branch# baddress

In order to identify the time invariant fds, we need to clearly

understand the semantics of the various attributes in the relation
staff# → sname, position, salary, branch#, baddress
branch# → baddress
baddress → branch#
branch#, position → salary
baddress, position → salary
15
 Functional Dependency
There is another way to present the 5 fds above as follows.
staffbranch

staff# sname position salary branch# baddress

16
 Trivial Functional Dependency
A functional dependency is trivial if and only if the consequent is a
subset of the determinant. Here, it is impossible for it not to be satisfied.
Example: Using the relation Staff, the trivial dependencies include:
{ staff#, sname} → sname
{ staff#, sname} → staff#
Although trivial fds are valid, they offer no additional information about
integrity constraints for the relation. As far as normalization is
concerned, trivial fds are ignored.

17
 Characteristics of Functional Dependency
In summary, the main characteristics of functional dependencies that
are useful in normalization are:
1. There exists a 1:1 relationship between attribute(s) in the
determinant and attribute(s) in the consequent.
2. The functional dependency is time invariant, i.e., it holds in all
possible instances of the relation.
3. The functional dependencies are nontrivial. Trivial fds are ignored.

18
 Inference Rules for Functional Dependency
IR1: reflexive rule – if Y  X, then X → Y
IR2: augmentation rule – if X → Y, then XZ → YZ
IR3: transitive rule – if X → Y and Y → Z, then X → Z
IR4: projection rule – if X → YZ, then X → Y and X → Z
IR5: additive rule – if X → Y and X → Z, then X → YZ
IR6: pseudo-transitive rule – if X → Y and YZ → W, then XZ → W
The first three of these rules (IR1-IR3) are known as Armstrong’s Axioms
and constitute a necessary and sufficient set of inference rules for
generating the closure of a set of functional dependencies.
19
 Example Proof using Inference Rules
Given R = (A, B, C, D, E, F, G, H, I, J) and F = {AB → E, AG → J, BE → I, E → G, GI → H}
does F ⊨ AB → GH?
Proof:
Practice Problem
1. AB → E, given in F
2. AB → B, projective rule IR4
Using the same set F,
3. AB → BE, additive rule IR5 from steps 1 and 2
Prove that F ⊨ BE → H
4. BE → I, given in F
5. AB → I, transitive rule IR3 from steps 3 and 4
6. E → G, given in F
7. AB → G, transitive rule IR3 from steps 1 and 6
8. AB → GI, additive rule IR5 from steps 5 and 7
9. GI → H, given in F
10. AB → H, transitive rule IR3 from steps 8 and 9
11. AB → GH, additive rule IR5 from steps 7 and 10 – proven! 20
 Closures
The notation: F ⊨ X → Y denotes that the functional dependency X → Y is
implied by the set of fds F.
Formally, F+  {X → Y | F ⊨ X → Y }
A set of inference rules is required to infer the set of fds in F+.
For example, if I tell you that Kristi is older than Debi and that Debi is older than Traci,
you are able to infer that Kristi is older than Traci. How did you make this inference?
Without thinking about it or maybe knowing about it, you utilized a transitivity rule to
allow you to make this inference.

21
 Determining Closures
Another way of looking at the closure of a set of fds F is: F+ is the smallest
set containing F such that Armstrong’s Axioms cannot be applied to the set
to yield an fd not in the set.
F+ is finite, but exponential in size in terms of the number of attributes of R.
For example, given R = (A,B,C) and F = {AB → C, C → B}, F+ will contain 29 fds
(including trivial fds).

Thus, to determine if a fd X → Y holds on a relation schema R given F,

what we really need to determine is does F ⊨ X → Y, or more correctly is
X→Y in F+? However, we want to do this without generating all of F+ and
checking to see if X → Y is in that set.

22
 Algorithm Closure
The technique for this is to generate not F+ but rather X+, where X is any
determinant from a fd in F. An algorithm for generating X+ is shown below.
X+ is called the closure of X under F (or with respect to F).
Algorithm Closure {returns X+ under F}
input: set of attributes X, and a set of fds F
output: X+ under F
Closure (X, F)
{
X +  X;
Algorithm Closure
repeat
oldX+  X+;
for every fd W→ Z in F do
if W  X+ then X+  X+  Z;
until (oldX+ = X+); 23
}
 Example Using Algorithm Closure
Given F = {A → D, AB → E, BI → E, CD → I, E → C}, Find (AE)+
pass 1
X+ = {A, E}
using A → D, A  X+, so add D to X+, X+ = {A, E, D}
using AB → E, no change
using BI → E, no change
using CD → I, no change
using E → C, E  X+, so add C to X+, X+ = {A, E, D, C}
changes occurred to X+ so another pass is required
pass 2
X+ = {A, E, D, C}
using A → D, yes, but no change
using AB → E, no change
using BI → E, no change
using CD → I, CD  X+, so add I to X+, X+ = {A, E, D, C, I}
using E → C, yes, but no changes 24
changes occurred to X+ so another pass is required
 Example Using Algorithm Closure
pass 3
X+ = {A, E, D, C, I}
using A → D, yes, but no changes
using AB → E, no
using BI → E, no
using CD → I, yes, but no changes
using E → C, yes, but no changes
no changes occurred to X+ so algorithm terminates

(AE)+ = {A, E, C, D, I}

This means that the following fds are in F+: AE → AECDI

25
 Algorithm Member
Once the closure of a set of attributes X has been generated, it becomes a
simple test to tell whether or not a certain functional dependency with a
determinant of X is included in F+.

Algorithm Member {determines membership in F+}

input: a set of fds F, and a single fd X → Y
output: true if F ⊨ X → Y, false otherwise
Member (F, X → Y)
Algorithm Member {
if Y  Closure(X,F)
then return true;
else return false;
}

26
 Covers and Equivalence of FD Sets
A set of fds F is covered by a set of fds G (alternatively stated as G
covers F) if every fd in F is also in G+.
• That is to say, F is covered if every fd in F can be inferred from G.
Two sets of fds F and G are equivalent if F+ = G+.
• That is to say, every fd in G can be inferred from F, and every fd in F
can be inferred from G.
• Thus F  G if F covers G, and G covers F.
To determine if G covers F, calculate X+ with respect to G for each
X→Y in F. If Y  X+ for each X, then G covers F.

27
 Why Covers?
• Algorithm Member has a run time which is dependent on the size of
the set of fds used as input to the algorithm. Thus, the smaller the
set of fds used, the faster the execution of the algorithm.
• Fewer fds require less storage space and thus a corresponding
lower overhead for maintenance whenever database updates occur.
There are many different types of covers ranging from non-redundant
covers to optimal covers.
Essentially the idea is to ultimately produce a set of fds G which is
equivalent to the original set F, yet has as few total fds as possible.

28
 Non-redundant Covers
A set of fds is non-redundant if there is no proper subset G of F with G  F.
If such a G exists, F is redundant.
F is a non-redundant cover for G if F is a cover for G and F is non-
redundant.
Algorithm Non-redundant {produces a non-redundant cover}
input: a set of fds G
output: a non-redundant cover for G
NonRedundant (G)
{
Algorithm Non-redundant F  G;
for each fd X → Y  G do
if Member(F – {X → Y}, X → Y)
then F  F – {X → Y};
return (F); 29
}
 Example Using Algorithm NonRedundant
Let G = {A → B, B → A, B → C, A → C}, find a non-redundant cover for G.
FG
Member({B → A, B → C, A → C}, A → B)
Closure(A, {B → A, B → C, A → C})
A+ = {A, C}, therefore A → B is not redundant
Member({A → B, B → C, A → C}, B → A)
Closure(B, {A → B, B → C, A → C})
B+ = {B, C}, therefore B → A is not redundant
Member({A → B, B → A, A → C}, B → C)
Closure(B, {A → B, B → A, A → C})
B+ = {B, A, C}, therefore B → C is redundant F = F – {B → C}
Member({A → B, B → A}, A → C)
Closure(A, {A → B, B → A})
A+ = {A, B}, therefore A → C is not redundant
Return F = {A → B, B → A, A → C}
30
 Example Using Algorithm NonRedundant
If G = {A → B, A → C, B → A, B → C}, the same set as before but given in a different
order. A different cover will be produced!
FG
Member({A → C, B → A, B → C}, A → B)
Closure(A, {A → C, B → A, B → C})
A+ = {A, C}, therefore A → B is not redundant
Member({A → B, B → A, B → C}, A → C)
Closure(A, {A → B, B → A, B → C})
A+ = {A, B, C}, therefore A → C is redundant F = F – {A → C}
Member({A → B, B → C}, B → A)
Closure(B, {A → B, B → C})
B+ = {B, C}, therefore B → A is not redundant
Member({A → B, B → A}, B → C)
Closure(B, {A → B, B → A})
B+ = {B, A}, therefore B → C is not redundant
Return F = {A → B, B → A, B → C} 31
 Non-redundant Covers
The previous example illustrates that a given set of functional
dependencies can contain more than one non-redundant cover.
It is also possible that there can be non-redundant covers for a set of
fds G that are not contained in G.
For example, if
G = {A → B, B → A, B → C, A → C}
then F = {A → B, B → A, AB → C} is a non-redundant cover for G
however, F contains fds that are not in G.

32
 Extraneous Attributes
If F is a non-redundant set of fds, there are no “extra” fds in F and thus
F cannot be made smaller by removing fds. If fds are removed from F
then a new set G would be produced where G ≢ F.
However, it may still be possible to reduce the overall size of F by
removing attributes from fds in F.
If F is a set of fds over relation schema R and X → Y  F, then the
attribute A is extraneous in X → Y wrt F if:
1. X = AZ, X  Z and {F – {X → Y}}  {Z → Y}  F, or
2. Y = AW, Y  W and {F – {X → Y}}  {X → W}  F
In other words, an attribute A is extraneous in X → Y if A can be
removed from either the determinant or consequent without changing
F+. 33
 Extraneous Attributes
Example:
Let F = {A → BC, B → C, AB → D}
attribute C is extraneous in the consequent of A → BC since
A+ = {A, B, C, D} when F = F – {A → C}
similarly, B is extraneous in the determinant of AB → D since
AB+ = {A, B, C, D} when F = F – {AB → D}

34
 Left and Right Reduced Sets of FDs
Let F be a set of fds over schema R and let X → Y  F.
X → Y is left-reduced if X contains no extraneous attribute A.
• A left-reduced functional dependency is also called a full functional
dependency.
X → Y is right-reduced if Y contains no extraneous attribute A.
X → Y is reduced if it is left-reduced, right-reduced, and Y is not
empty.

35
 Algorithm Left-Reduce

Algorithm Left-Reduce {returns left-reduced version of F}

input: set of fds G
output: a left-reduced cover for G
Left-Reduce (G)
{
F  G;
Algorithm Left-Reduce
for each fd X→ Y in G do
for each attribute A in X do
if Member(F, (X - A) → Y)
then remove A from X in X→ Y in F
return(F);
}
36
 Algorithm Right-Reduce

Algorithm Right-Reduce {returns right-reduced version of F}

input: set of fds G
output: a right-reduced cover for G
Right-Reduce (G)
{
Algorithm F  G;
Right-Reduce for each fd X→ Y in G do
for each attribute A in Y do
if Member(F – {X→ Y}  {X → (Y- A)}, X → A)
then remove A from Y in X→ Y in F
return(F);
}
37
 Algorithm Reduce

Algorithm Reduce {returns reduced version of F}

input: set of fds G If G contained a
output: a reduced cover for G redundant fd, X→ Y,
Reduce (G) every attribute in Y
Algorithm Reduce { would be extraneous
and thus reduce to X →
F  Right-Reduce( Left-Reduce(G)); null, so these need to be
remove all fds of the form X→ null from F removed.
return(F);
}

38
 Algorithm Reduce
The order in which the reduction is done by algorithm Reduce is
important. The set of fds must be left-reduced first and then right-
reduced. The example below illustrates what may happen if this order
is violated.
Example:
Let G = {B → A , D → A , BA → D}
G is right-reduced but not left-reduced. If we left-reduce
G to produce F = {B → A , D → A , B → D}
We have F is left-reduced but not right-reduced!
B → A is extraneous on right side since B → D → A
39
 Minimum Cover
A set of functional dependencies F is minimal if
1. Every fd has a single attribute for its consequent.
2. F is non-redundant.
3. No fd X → A can be replaced with one of the form Y → A where
Y→X and still be an equivalent set, i.e., F is left-reduced.
Example:
G = {A → BCE, AB → DE, BI → J}
a minimum cover for G is:
F = {A → B, A → C, A → D, A → E, BI → J}

40
 Algorithm Mincover

Algorithm MinCover {returns minimum cover for F}

input: set of fds F
output: a minimum cover for F
MinCover (F)
{
G  F;
Algorithm MinCover
replace each fd X → A1A2...An in G
by n fds X → A1, X → A2,..., X → An
LeftReduce(G);
NonRedundant(G);
return(G);
}
41
 Keys of a Relational Schema
If R is a relational schema with attributes A1,A2, ..., An and a set of
functional dependencies F where X ⊆ {A1,A2,...,An} then X is a key of R
if:
• X → {A1,A2,... An}  F+, and
• no proper subset Y ⊆ X gives Y → {A1,A2,...An}  F+.
Basically, this definition means that you must attempt to generate the
closure of all possible subsets of the schema of R and determine which
sets produce all of the attributes in the schema.

43
 Determining Keys - example
Find all keys for R = (C, T, H, R, S, G) with
F = {C → T, HR → C, HT → R, CS → G, HS → R}
Step 1: Generate (Ai)+ for 1  i  n  6
  =
6!
=
720
=6
1
  1!( 6 − 1)! 120
C+ = {CT}, T+ = {T}, H+ = {H}
R+ = {R}, S+ = {S}, G+ = {G}
 6 6! 720
no single attribute is a key for R 
 
 = =
 2  2!(6 − 2)! 48 = 15
Step 2: Generate (AiAj) for 1  i  n, 1  j  n
+

(CT)+ = {C,T}, (CH)+ = {CHTR}, (CR)+ = {CRT}

(CS)+ = {CSGT}, (CG)+ = {CGT}, (TH)+ = {THRC}
(TR)+ = {TR}, (TS)+ = {TS}, (TG)+ = {TG}
(HR)+ = {HRCT}, (HS)+ = {HSRCTG}, (HG)+ = {HG}
(RS)+ = {RS}, (RG)+ = {RG}, (SG)+ = {SG}
The attribute set (HS) is a key for R
44
 Determining Keys - example
Step 3: Generate (AiAjAk)+ for 1  i  n, 1  j  n, 1  k  n
(CTH)+ = {CTHR}, (CTR)+ = {CTR}
(CTS)+ = {CTSG}, (CTG)+ = {CTG}  6
  =
6! 720
= = 20
+
(CHR) = {CHRT}, +
(CHS) = {CHSTRG} 3
  3!( 6 − 3 )! 36

(CHG)+ = {CHGTR}, (CRS)+ = {CRSTG}

(CRG)+ = {CRGT}, (CSG)+ = {CSGT}
(THR)+ = {THRC}, (THS)+ = {THSRCG}
(THG)+ = {THGRC}, (TRS)+ = {TRS}
(TRG)+ = {TRG}, (TSG)+ = {TSG}
(HRS)+ = {HRSCTG}, (HRG)+ = {HRGCT}
(HSG)+ = {HSGRCT}, (RSG)+ = {RSG}

Super keys are shown in red.

45
 Determining Keys - example
Step 4: Generate (AiAjAkAr)+ for 1  i  n, 1  j  n, 1  k  n, 1  r  n
6 6! 720
(CTHR)+ = {CTHR}, (CTHS)+ = {CTHSRG}   =
4 4!( 6 − 4 )!
=
48
= 15
 
(CTHG)+ = {CTHGR}, (CHRS)+ = {CHRSTG}
(CHRG)+ = {CHRGT}, (CRSG)+ = {CRSGT}
(THRS)+ = {THRSCG}, (THRG)+ = {THRGC}
(TRSG)+ = {TRSG}, (HRSG)+ = {HRSGCT}
(CTRS)+ = {CTRS}, (CTSG)+ = {CTSG}
(CSHG)+ = {CSHGTR}, (THSG)+ = {THSGRC}
(CTRG)+ = {CTRG}

Super keys are shown in red.

46
 Determining Keys - example
Step 5: Generate (AiAjAkArAs)+ for 1  i  n, 1  j  n, 1  k  n, 1  r  n,
1sn
 6 6! 720
  = = =6
(CTHRS)+ = {CTHSRG}  5  5!( 6 − 5)! 120
(CTHRG)+ = {CTHGR}
(CTHSG)+ = {CTHSGR}
(CHRSG)+ = {CHRSGT}
(CTRSG)+ = {CTRSG}
(THRSG)+ = {THRSGC}

Super keys are shown in red

47
 Determining Keys - example
Step 6: Generate (AiAjAkArAsAt)+ for 1  i  n, 1  j  n, 1  k  n, 1  r
 n, 1  s  n, 1  t  n
 6 6! 720
  = = =1
 6  6!(6 − 6)! 720
(CTHRSG)+ = {CTHSRG}

Super keys are shown in red.

In general, for 6 attributes we have:

 6  6  6  6  6  6
  +   +   +   +   +   = 6 + 15 + 20 + 15 + 1 = 63 cases
1   2   3   4   5   6 

48
 Normalization based on Keys
• Normalization is a formal technique for analyzing relations based on
the candidate keys and functional dependencies.
• The technique involves a series of rules that can be used to test
individual relations so that a database can be normalized to any
degree.
• When a requirement is not met, the relation violating the requirement
is decomposed into a set of relations that individually meet the
requirements of normalization.
• Normalization is often executed as a series of steps. Each step
corresponds to a specific normal form that has known properties.

49
Different Normal Forms
N1NF
1NF
2NF
3NF
BCNF
4NF
5NF

Higher Normal Forms

50
 Normalization
• In relational model, only the first normal form (1NF) is critical in
creating relations. All the subsequent normal forms are optional.
• To avoid the update anomalies, it is normally recommended that the
database designer proceed to at least 3NF.
• In fact, some 1NF relations are also in 2NF and some 2NF relations
are also in 3NF, and so on.
• As we proceed, we’ll look at the requirements for each normal form
and a decomposition technique to achieve relation schemas in each
of normal form.

51
 First Normal Form (1NF)
• A relation in which every attribute value is atomic is in 1NF.
• We have only considered 1NF relations for the most part in this
course.
• When dealing with multi-valued attributes at the conceptual level,
recall that in the conversion into the relational model created a
separate table for the multi-valued attribute.

52
 Some Additional Terminologies
• A key is a superkey such that the removal of any attribute from the
key will cause it to no longer be a superkey. In other words, the key
is minimal in the number of attributes.
• The candidate key for a relation is one of minimal superkeys of the
relation schema.
• The primary key for a relation is a selected candidate key. All of the
remaining candidate keys (if any) become secondary keys.
• A prime attribute is any attribute of the schema of a relation R that is
a member of any candidate key of R.
• A non-prime attribute is any attribute of R which is not a member of
any candidate key.
53
 Full Functional Dependency
• Second normal form (2NF) is based on the concept of a full
functional dependency.
• A functional dependency X → Y is a full functional dependency if the
removal of any attribute A from X causes the fd to no longer hold.
• for any attribute AX, X - {A} → Y
• A functional dependency X → Y is a partial functional dependency if
some attribute A can be removed from X and the fd still holds.
• for some attribute AX, X - {A} → Y

54
 Second Normal Form (2NF)
• A relation scheme R is in 2NF with respect to a set of functional
dependencies F if every non-prime attribute is fully dependent on
every key of R.
• Another way of stating this is: there does not exist a non-prime
attribute which is partially dependent on any key of R. In other
words, no non-prime attribute is dependent on only a portion of the
key of R.

55
 2NF Identification
A relation scheme R is in 2NF if it satisfies one of those conditions:
• It has single-attribute keys (simple keys)
• It doesn’t have any non-prime attribute
• All non-prime attribute are fully functional dependent on the keys.

56
 2NF Normalization
• Remove each non-prime attribute that is functional dependent on a
proper subset of a candidate key and form a new relation with a new
key is the proper subset.
• All remaining attributes form a new relation with the key is the
original one.

58
 2NF Normalization - Example
Given R = (A, D, P, G),
F = {AD → PG, A → G}
Then R is not in 2NF because G is partially dependent on the key AD
since AD → G yet A → G.
Decompose R into:
R1 = (A, D, P) R2 = (A, G)
K1 = {AD} K2 = {A}
F1 = {AD → P} F2 = {A → G}

59
 Transitive Dependency
Third Normal Form (3NF) is based on the concept of a transitive
dependency.
• Given a relation scheme R with a set of functional dependencies F
and subset X  R and an attribute A R. A is said to be transitively
dependent on X if there exists Y  R with X → Y, Y → X and Y → A
and A  XY.
• An alternative definition for a transitive dependency is: a functional
dependency X → Y in a relation scheme R is a transitive
dependency if there is a set of attributes Z  R where Z is NOT a
subset of any key of R and yet both X → Z and Z → Y hold in F.

61
 Third Normal Form (3NF)
Definition: A relation scheme R is in 3NF with respect to a set of
functional dependencies F, if whenever X → A holds, either:
(1) X is a superkey of R or
(2) A is a prime attribute.

Alternative definition: A relation scheme R is in 3NF with respect to a

set of functional dependencies F if it satisfies:
• It is in 2NF
• No non-prime attribute is transitively dependent on any key of R.

62
 3NF Normalization
Method 1:
Input a relation R and a functional dependencies set F hold for R.
• Find a minimal cover, G, of the set of functional dependencies F.
• For each functional dependency X→A in G, form (X, A) as the
schema of one of the relations in the decomposition.
• If non of the resulting relation schemas from step 2 contains a
candidate key for R, add another relation whose schema is a
candidate key of R

63
 3NF Normalization
Method 2:
Input a relation R and a functional dependencies set F hold for R.
• Remove each non-prime attribute that is transitive dependent on a
key of R and form a new relation with the key is the transitive
attributes.
• Remaining attributes form a new relation with the key is the original
one.

64
 3NF - Example
Let R = (A, B, C, D)
and F = {AB → CD, C → D, D → C}
then R is not in 3NF since C → D holds and C is not a superkey of R.
Alternatively, R is not in 3NF since AB → C and C → D and thus D is a
non-prime attribute which is transitively dependent on the key AB.

65
 Boyce-Codd Normal Form (BCNF)
Boyce-Codd Normal Form (BCNF) is a more stringent form of 3NF.
Definition: A relation scheme R is in Boyce-Codd Normal Form with
respect to a set of functional dependencies F if whenever X → A holds
and A ⊈ X, then X is a super-key of R.

Example: Let R = (A, B, C)

F = {AB → C, C → A}
Keys = {AB}, {BC}
R is in 3NF, but not in BCNF since C → A holds and C is not a super-
key of R.
75
 BCNF versus 3NF
• Notice that the only difference in the definitions of 3NF and BCNF is
that BCNF drops the allowance for A in X → A to be prime.
• An interesting side note to BCNF is that Boyce and Codd originally
intended this normal form to be a simpler form of 3NF. In other
words, it was supposed to be between 2NF and 3NF. However, it
was quickly proven to be a more strict definition of 3NF and thus it
wound up being between 3NF and 4NF.
• In practice, most relational schemes that are in 3NF are also in
BCNF. Only if X → A holds in the schema where X is not a superkey
and A is prime, will the schema be in 3NF but not in BCNF.

76