UNIT 4

DEPENDENCIES AND NORMAL FORMS

Normalization – Introduction, functional dependencies, First, Second, and third normal forms –
dependency preservation, Boyce/Codd normal form.
Higher Normal Forms - Introduction, Multi-valued dependencies and Fourth normal form, Join
dependencies and Fifth normal form

NORMALIZATION

Problems Caused by Redundancy

Storing the same information redundantly, that is, in more than one place within a database, can lead
to several problems:

 Redundant storage: Some information is stored repeatedly.

 Update anomalies: If one copy of such repeated data is updated, an inconsistency is created unless
all copies are similarly updated.

 Insertion anomalies: It may not be possible to store some information unless some other
information is stored as well.

 Deletion anomalies: It may not be possible to delete some information without losing some other
information as well.

FUNCTIONAL DEPENDENCIES

A functional dependency (FD) is a kind of IC that generalizes the concept of a key. Let R be a relation
schema and let X and Y be nonempty sets of attributes in R. We say that an instance r of R satisfies the

FD X ! Y 1 if the following holds for every pair of tuples t1 and t2 in r:

If t1:X = t2:X, then t1:Y = t2:Y .

A primary key constraint is a special case of an FD. The attributes in the key play the role of X, and
the set of all attributes in the relation plays the role of Y. Note, however, that the definition of an FD
does not require that the set X be minimal; the additional minimality condition must be met for X to be
a key. If X ! Y holds, where

Y is the set of all attributes, and there is some subset V of X such that V ! Y holds, then X is a super
key; if V is a strict subset of X, then X is not a key.
REASONING ABOUT FUNCTIONAL DEPENDENCIES

50
The discussion up to this point has highlighted the need for techniques that allow us to
carefully examine and further re ne relations obtained through ER design (or, for that matter,
through other approaches to conceptual design.
Given a set of FDs over a relation schema R, there are typically several additional
FDs that hold over R whenever all of the given FDs hold.
Closure of a Set of FDs

The set of all FDs implied by a given set F of FDs is called the closure of F and is

denoted as F +. An important question is how we can infer, or compute, the closure of a given
set F of FDs. The answer is simple and elegant. The following three rules, called Armstrong's
Axioms, can be applied repeatedly to infer all FDs implied by a set F of FDs. We use X, Y, and
Z to denote sets of attributes over a relation schema
R:

Reflexivity: If X Y, then X ! Y.

Augmentation: If X ! Y, then XZ ! YZ for any Z. Transitivity: If X

! Y and Y ! Z, then X ! Z.

Armstrong's Axioms are sound in that they generate only FDs in F + when applied to a set F of
FDs. They are complete in that repeated application of these rules will

generate all FDs in the closure F +. (We will not prove these claims.) It is convenient to use
some additional rules while reasoning about F+.

Union: If X ! Y and X ! Z, then X ! YZ. Decomposition: If X ! YZ,

then X ! Y and X ! Z.

These additional rules are not essential; their soundness can be proved using Arm-strong's
Axioms.

51
Normalization:
It is a process for evaluating and correcting table structures to minimize data
redundancies, there by reducing the likelihood of data anomalies.

Normalization works through a series of stages called normal forms. The first three stages
are described as first normal form (1NF), second normal form (2NF) and third normal form
(3NF).

From a structural point of view, 2NF is better than 1NF and 3NF is better than 2NF.

Denormalization:
Produces a lower normal form, which is a 3NF will be converted to a 2NF through
denormalization. A successful design must also consider end-user demand for fast
performance. Therefore, you will occasionally be expected to denormalize some portions of
database design in order to meet performance requirements.

The need for normalization

In following example:

52
We see in that example, the structure of data set does not conform to the requirements of
table nor does it handle data very well.

Consider the following deficiencies:

1. The project number (PROJ_NUM) is apparently intended to be primary key or at least a

part of a PK, but it contains nulls.
2. The table entries invite data inconsistencies. For example the JOB_CLASS value "Elect.
Engineer" might be entered as "Elect. Eng."
3. The table displays data redundancies. Those data redundancies yield the following
anomalies:
a. Update anomalies. Modifying the JOB_CLASS for employee number 105
requires (potentially) many alterations, one for each EMP_NUM=105.
b. Insertion anomalies. Just to complete a row definition, a new employee must be
assigned to a project. If the employee is not assigned, a phantom project must be
created to complete the employee data entry.

53
 c. Deletion anomalies. Suppose that only one employee is associated with a given
project, if that employee leaves the company and the employee data are deleted ,
the project information will also be deleted .to prevent the loss of the project
information ,a fictitious employee must be created just to save the project
information.

The Normalization Process:

We will learn how to use normalization to produce a set of normalized tables to store the
data that will be used to generate the required information. The objective of normalization is
to ensure that each table conforms to the concept of well-formed relations, that is, tables that
have the following characteristics:

 Each table represents a single subject. For example, a course Table will contain only
data that directly pertains to courses. Similarly, a student table will contain only
student data.
 No data item will be unnecessarily stored in more than one table (in short, tables have
minimum controlled redundancy). The reason for this requirement is to ensure that the
data are update in only one place.
 All nonprime attributes in a table are dependent on the primary key. The reason for
this requirement is to ensure that the data are uniquely identifiable by a primary key
value.
 Each table is void of insertion, update or deletion anomalies. This is to ensure the
integrity and consistency of the data.
Conversion to First Normal Form (1NF)

Step 1: Eliminate the Repeating Groups

Start by presenting the data in tabular format, where each cell has a single value and there
are no repeating groups. A repeating group derives its name from the fact that a group of
multiple entries of the same type can exist for any single key attributes occurrence. To
eliminate the repeating groups, eliminate the nulls by making sure that each repeating group
attribute contains an appropriate data value.

54
Step 2: Identify the primary key:

Even causal observers will not that PROJ-NUM is not an adequate primary key because the
project number does not uniquely identify all of the remaining entity (row) attributes. To
maintain a proper primary key that will uniquely identify any attribute value, the new ke y
must be compost of a combination of a PROJ_NUM and EMP_NUM

Step 3: Identify All Dependencies:

The identification of the PK in Step 2 means that you have already identified the following
dependency:

 PROJ_NUM, EMP_NUM  PROJ_NAME, EMP_NAME, JOB_CLASS,

CHG_HOUR, HOURS

55
  PROJ_NUM  PROJ_NAME
 EMP_NUM  EMP-NAME, JOB-CLASS, CHG-HOUR
 JOB_CLASS  CHG_HOUR

Partial dependency a dependency based only a part of a composite primary key.

Transitive dependency is a dependency of one nonprime attribute on another nonprime

attribute.

The term first normal form (1NF) describes the tabular format in which:

 All of the key attributes are defined.

 There are no repeating groups in the table. in other words, each row/column intersection
contains one and only one value, not a set of values.
 All attributes are dependent on the primary key.
The problem with the 1NF table structure is that it contains partial dependencies. While
partial dependencies are sometimes used for performance reasons, they should be used with
caution.

56
Conversion to Second Normal Form (2NF)

Converting to 2NF is done only when the 1NF has a composite primary key. if the 1NF has a
single attribute primary key, then the table is automatically in 2NF. The 1NF-to-2NF
conversion is simple starting with:

Step 1: Write Each Key Component on a Separate Line

Write each key component on a separate line; then write the original (composite) key on the
last line.

 PROJ_NUM
 EMP_NUM
 PROJ_NUM EMP_NUM
Each component will become the key in a new table. In other words, the original table is now
divided in to three tables:

 (PROJECT, EMPLOYEE, and ASSIGNMENT).

Step 2: Assign Corresponding Dependent Attributes

Use dependency diagram to determine those attributes that are dependent on other
attributes.

 PROJECT (PROJ_NUM, PROJ_NAME)

 EMPLOYEE (EMP_NUM, EMP_NAME, JOB_CLASS, CHG_HOUR)
 ASSIGNMENT (PROJ_NUM, EMP_NUM, ASSIGN_HOURS)

57
A table is in second normal form (2NF) when:

 it is in 1NF, And
 It includes no partial dependencies; that is, no attribute is dependent on only portion of
the primary key. Note that is still possible for a table in 2NF to exhibit transitive
dependency; that is, one or more attributes may be functionally dependent on non key
attributes.
Conversion to Third Normal (3NF):

Step 1: Identify the Dependent Attributes

For every transitive dependency, write its determinant as PK for a new table.

 JOB_CLASS
Step 2: Identify the Dependent Attributes

Identify the attributes that are dependent on each determinant identified in Step 1 and identify
the dependency.

58
  JOB_CLASS CHG_HOUR
Name the table to reflect its contents and function. In this case, JOB seems appropriate.

Step 3: Remove the Dependent Attributes from Transitive Dependencies

Eliminate all dependent attributes in the transitive relationship(s) from each of the tables that
have such a transitive relationship.

 EMP_NUM  EMP_NAME, JOB_CLASS

Note that the JOB_CLASS remains in the EMPLOYEE table to save as FK.

After the 3NF conversion has been completed, your database contains four tables:

A table is in 3NF when:

 It is in 2NF
 It contains no transitive dependencies

Dependency-Preserving Decomposition into 3NF

Returning to the problem of obtaining a lossless-join, dependency- preserving decom-position

into 3NF relations, let R be a relation with a set F of FDs that is a minimal cover, and let R1;
R2; : : : ; Rn be a lossless-join decomposition of R. For 1 i n, suppose that each Ri is in 3NF and
let Fi denote the projection of F onto the attributes of Ri. Do the following:

59
 Identify the set N of dependencies in F that are not preserved, that is, not included
in the closure of the union of Fis.
For each FD X ! A in N , create a relation schema XA and add it to the decom-position of
R.

Obviously, every dependency in F is preserved if we replace R by the Ris plus the schemas of
the form XA added in this step. The Ris are given to be in 3NF. We can show that each of the
schemas XA is in 3NF as follows: Since X ! A is in the minimal cover F, Y ! A does not hold
for any Y that is a strict subset of X. Therefore, X is a key for XA.

As an optimization, if the set N contains several FDs with the same left side, say, X !
A1; X ! A2 ; : : : ; X ! An , we can replace them with a single equivalent FD X ! A1 : : :

An. Therefore, we produce one relation schema XA1 : : : An, instead of several
schemas XA1; : : : ; XAn, which is generally preferable.

Comparing this decomposition with the one that we obtained earlier in this section, we find
that they are quite close, with the only difference being that one of them has CDJPQV instead
of CJP and CJDQV. In general, however, there could be significant differences. Database
designers typically use a conceptual design methodology (e.g., ER design) to arrive at an initial
database design. Given this, the approach of repeated decompositions to rectify instances of
redundancy is likely to be the most natural use of FDs and normalization techniques. However,
a designer can also consider the alternative designs suggested by the synthesis approach.

Boyce–Codd normal form (BCNF ) is a normal form used in database normalization. It is a

slightly stronger version of the third normal form (3NF). BCNF was developed in 1975
by Raymond F. Boyce and Edgar F. Codd to address certain types of anomalies not dealt with
by 3NF as originally defined.[1]

If a relational schema is in BCNF then all redundancy based on functional dependency has
been removed, although other types of redundancy may still exist. A relational schema Ris in
Boyce–Codd normal form if and only if for every one of its dependencies X → Y, at least one
of the following conditions hold:[2]

 X → Y is a trivial functional dependency (Y ⊆ X)

 X is a superkey for schema R

Only in rare cases does a 3NF table not meet the requirements of BCNF. A 3NF table that
does not have multiple overlapping candidate keys is guaranteed to be in BCNF.[3]Depending

60
on what its functional dependencies are, a 3NF table with two or more overlapping candidate
keys may or may not be in BCNF.

An example of a 3NF table that does not meet BCNF is:

Today's Court Bookings

Court Start Time End Time Rate Type

1 09:30 10:30 SAVER

1 11:00 12:00 SAVER

1 14:00 15:30 STANDARD

2 10:00 11:30 PREMIUM-B

2 11:30 13:30 PREMIUM-B

2 15:00 16:30 PREMIUM-A

 Each row in the table represents a court booking at a tennis club. That club has one hard
court (Court 1) and one grass court (Court 2)
 A booking is defined by its Court and the period for which the Court is reserved
 Additionally, each booking has a Rate Type associated with it. There are four distinct rate
types:
 SAVER, for Court 1 bookings made by members
 STANDARD, for Court 1 bookings made by non-members
 PREMIUM-A, for Court 2 bookings made by members
 PREMIUM-B, for Court 2 bookings made by non-members
The table's superkeys are:

 S1 = {Court, Start Time}

 S2 = {Court, End Time}
 S3 = {Rate Type, Start Time}
 S4 = {Rate Type, End Time}
 S5 = {Court, Start Time, End Time}

61
 S6 = {Rate Type, Start Time, End Time}
 S7 = {Court, Rate Type, Start Time}
 S8 = {Court, Rate Type, End Time}
 ST = {Court, Rate Type, Start Time, End Time}, the trivial superkey
Note that even though in the above table Start Time and End Time attributes have no
duplicate values for each of them, we still have to admit that in some other days two different
bookings on court 1 and court 2 could start at the same time or end at the same time. This is
the reason why {Start Time} and {End Time} cannot be considered as the table's superkeys.

However, only S1 , S2, S3 and S4 are candidate keys (that is, minimal superkeys for that
relation) because e.g. S1 ⊂ S5, so S5 cannot be a candidate key.

Recall that 2NF prohibits partial functional dependencies of non-prime attributes (i.e., an
attribute that does not occur in ANY candidate key. See candidate keys), and
that 3NFprohibits transitive functional dependencies of non-prime attributes on candidate
keys.

In Today's Court Bookings table, there are no non-prime attributes: that is, all attributes
belong to some candidate key. Therefore the table adheres to both 2NF and 3NF.

The table does not adhere to BCNF. This is because of the dependency Rate Type → Court in
which the determining attribute Rate Type - on which Court depends - (1.) is neither a
candidate key nor a superset of a candidate key and (2.) Court Type is no subset of Rate
Type.

Dependency Rate Type → Court is respected since a Rate Type should only ever apply to a
single Court.

The design can be amended so that it meets BCNF:

Rate Types

Rate Type Court Member Flag

SAVER 1 Yes

STANDARD 1 No

62
PREMIUM-A 2 Yes

PREMIUM-B 2 No

Today's Bookings

Member Flag Court Start Time End Time

Yes 1 09:30 10:30

Yes 1 11:00 12:00

No 1 14:00 15:30

No 2 10:00 11:30

No 2 11:30 13:30

Yes 2 15:00 16:30

The candidate keys for the Rate Types table are {Rate Type} and {Court, Member Flag}; the
candidate keys for the Today's Bookings table are {Court, Start Time} and {Court, End
Time}. Both tables are in BCNF. When {Rate Type} is a key in the Rate Types table, having
one Rate Type associated with two different Courts is impossible, so by using {Rate Type} as
a key in the Rate Types table, the anomaly affecting the original table has been eliminated.

Multivalued Dependencies

Suppose that we have a relation with attributes course, teacher, and book, which we denote as
CTB. The meaning of a tuple is that teacher T can teach course C, and book
B is a recommended text for the course. There are no FDs; the key is CTB.
However, the recommended texts for a course are independent of the instructor.

63
The instance shown in Figure 15.13 illustrates this situation.

course teache book

r
Physics1 Mechani
Green
01 cs
Physics1
01 Green Optics
Physics1 Mechani
01 Brown c s
Physics1
01 Brown Optics
Mechani
Math301 Green c s
Math301 Green Vectors
Math301 Green Geometr
y

BCNF Relation with Redundancy That Is Revealed by MVDs

There are three points to note here:

The relation schema CTB is in BCNF; thus we would not consider decomposing
it further if we looked only at the FDs that hold over CTB.

There is redundancy. The fact that Green can teach Physics101 is recorded once per
recommended text for the course. Similarly, the fact that Optics is a text for Physics101 is
recorded once per potential teacher.

The redundancy can be eliminated by decomposing CTB into CT and CB.

This table suggests another way to think about MVDs: If X !! Y

holds over R, then Y
Z ( X=x(R)) = Y ( X=x(R)) Z ( X=x(R)) in every legal instance of R, for any value x that appears
in the X column of R. In other words, consider groups of tuples in R with the same X-value, for
each X-value. In each such group consider the projection onto the attributes YZ. This projection
must be equal to the cross-product of the projections onto Y and Z. That is, for a given X-value,

64
the Y-values and Z-values are independent. (From this de nition it is easy to see that X !! Y must
hold whenever X ! Y holds. If the FD X ! Y holds, there is exactly one Y-value for a given X-
value, and the conditions in the MVD de nition hold trivially. The converse does not hold, as
Figure 15.14 illustrates.)
Returning to our CTB example, the constraint that course texts are independent of instructors
can be expressed as C !! T. In terms of the de nition of MVDs, this constraint can be read as
follows:
\If (there is a tuple showing that) C is taught by teacher T,
and (there is a tuple showing that) C has book B as text,
then (there is a tuple showing that) C is taught by T and has text B.
Given a set of FDs and MVDs, in general we can infer that several additional FDs and MVDs
hold. A sound and complete set of inference rules consists of the three Armstrong Axioms plus
ve additional rules. Three of the additional rules involve only MVDs:

MVD Complementation: If X !! Y, then X !! R − XY . MVD Augmentation: If

X !! Y and W Z, then WX !! YZ. MVD Transitivity: If X !! Y and Y !! Z, then X
!! (Z − Y ).

As an example of the use of these rules, since we have C !! T over CTB, MVD
complementation allows us to infer that C !! CT B − CT as well, that is, C !! B. The remaining
two rules relate FDs and MVDs:

Replication: If X ! Y, then X !! Y.

Coalescence: If X !! Y and there is a W such that W \ Y is empty, W ! Z, and Y

Z, then X ! Z.

Observe that replication states that every FD is also an MVD.

Fourth Normal Form

Fourth normal form is a direct generalization of BCNF. Let R be a relation schema, X and Y be
nonempty subsets of the attributes of R, and F be a set of dependencies that includes both FDs
and MVDs. R is said to be in fourth normal form (4NF) if for every MVD X !! Y that holds
over R, one of the following statements is true:
Y X or XY = R, or

65
 X is a Superkey.
In reading this definition, it is important to understand that the de nition of a key has not
changed the key must uniquely determine all attributes through FDs alone. X !! Y is a trivial
MVD if Y X R or XY = R; such MVDs always hold.

The relation CTB is not in 4NF because C !! T is a nontrivial MVD and C is not a key. We can
eliminate the resulting redundancy by decomposing CTB into CT and CB; each of these
relations is then in 4NF.
To use MVD information fully, we must understand the theory of MVDs. However, the
following result due to Date and Fagin identifies conditions detected using only FD
information!|under which we can safely ignore MVD information. That is, using MVD
information in addition to the FD information will not reveal any redundancy. Therefore, if
these conditions hold, we do not even need to identify all MVDs.
If a relation schema is in BCNF, and at least one of its keys consists of a single
attribute, it is also in 4NF.
An important assumption is implicit in any application of the preceding result: The set
of FDs identified thus far is indeed the set of all FDs that hold over the relation. This
assumption is important because the result relies on the relation being in BCNF, which
in turn depends on the set of FDs that hold over the relation.

Figure shows three tuples from an instance of ABCD that satisfies the given MVD B

!! C. From the definition of an MVD, given tuples t1 and t2, it follows

B C A D
b c1 a1 d1 | tuple t1
b c2 a2 d2 | tuple t2

b c1 a2 d2 | tuple t3

Three Tuples from a Legal Instance of ABCD

that tuple t3 must also be included in the instance

Consider tuples t2 and t3. From the given FD A ! BCD and the fact
that these tuples have the same A-value, we can

66
deduce that c1 = c 2. Thus, we see that the FD B ! C must hold over ABCD whenever
the FD A ! BCD and the MVD B !! C hold. If B ! C holds, the relation ABCD is not in
BCNF (unless additional FDs hold that make B a key)!

Join Dependencies
A join dependency is a further generalization of MVDs. A join dependency (JD)
./ fR1; : : : ; R ng is said to hold over a relation R if R1; : : : ; Rn

is a lossless-join decomposition of R.
An MVD X !! Y over a relation R can be expressed as the join dependency ./ fXY, X(R−Y)g.
As an example, in the CTB relation, the MVD C !! T can be expressed as the join dependency ./
fCT, CBg.
Unlike FDs and MVDs, there is no set of sound and complete inference rules for JDs.

Fifth Normal Form

A relation schema R is said to be in fth normal form (5NF) if for every JD ./ fR1; :
: : ; Rng that holds over
R, one of the following statements is true:

Ri = R for some i, or

The JD is implied by the set of those FDs over R in which the left side is a key
for R.

The second condition deserves some explanation, since we have not presented inference rules
for FDs and JDs taken together. Intuitively, we must be able to show

that the decomposition of R into fR1; : : : ; Rng is lossless-join whenever the key
dependencies (FDs in which the left side is a key for R) hold. ./ fR1; : : : ; Rng is a
trivial JD if Ri = R for some i; such a JD always holds.

The following result, also due to Date and Fagin, identifies conditions again, detected
using only FD information under which we can safely ignore JD information.

If a relation schema is in 3NF and each of its keys consists of a single attribute,
it is also in 5NF.
The conditions identified in this result are sufficient for a relation to be in 5NF, but not
necessary. The result can be very useful in practice because it allows us to conclude

67
that a relation is in 5NF without ever identifying the MVDs and JDs that may hold over
the relation.

68