Lesson Objectives: NORMALISATION-I

Normalisation
First Normal Form
Functional dependencies
Closure of a set of functional dependencies

When deciding upon the structure of data to be stored in a file(s), or a database, the two main issues
to be considered are:

1) removing data duplication from the files/database

2) avoiding data confusion, where different versions of the same information is located in different
places in the same file

Data Normalisation is the process of determining the correct structure for data in files or databases
so that the problems mentioned cannot occur
Data is structured by following a series of steps. Each step removes the potential for a particular
problem to occur in the data, e.g. duplication, and each step builds upon the previous steps

First Normal Form

The first of the normal forms that we study, first normal form, imposes a very basic requirement on
relations.

A domain is atomic if elements of the domain are considered to be indivisible units. We say
that a relational schema R is in first normal form (lNF) if the domains of all attributes of R are
atomic.

A set of names is an example of a non atomic value. For example, if the schema of a relation
employee included an attribute children whose domain elements are sets of names, the schema
would not be in first normal form.

Composite attributes, such as an attribute address with component attributes street and city,
also have nonatomic domains.

Integers are assumed to be atomic, so the set of integers is an atomic domain; the set of all sets of
integers is a nonatomic domain. The distinction is that we do not normally consider integers to have
subparts, but we consider-sets of integers to have subparts-namely, the integers making up the set.
But the important issue is not what the domain itself is, but rather how we use domain elemeents in
our database. The domain of all integers would be nonatomic if we considered each integer to be an
ordered list of digits.

Page 163
 As a practical illustration of the above point, consider an organization that assigns employees
identification numbers of the following form: The first two letters specify the department and the
remaining four digits are a unique number within the department for the employee. Examples of
such numbers would be CS0012 and EE1127. Such identification numbers can be divided into
smaller units, and are therefore nonatomic. If a relation schema had an attribute whose domain
consists of identification numbers encoded as above, the schema would not be in first normal form.

First normal form (1NF) sets the very basic rules for an organized database:

• Eliminate duplicative columns from the same table.

• Create separate tables for each group of related data and identify each row with a unique
column or set of columns (the primary key).

Functional Dependencies

Functional dependencies plays key role in designing good database. A functional dependency is a
type of constraint that is a generalization of the notion of key.
Functional dependencies are constraints. on the set of legal relations. They. allow us to express facts
about the enterprise that we are modeling with our database.

If we define the notion of a superkey as follows. Let R be a relation schema. A subset K of R

is a superkey of R if, in any legal relation r(R), for all pairs tl and t2 of tuples in r such that tl ≠ t2,
then t1[K] ≠t2[K_]. That is, no two tuples in any legal relation r(R) may have the same value on
attribute set K.
The notion of functional dependency generalizes the notion of superkey. Consider a relation schema
R, and let α ⊆ Rand β ⊆ R. The functional dependency

C→α

holds on schema R if, in any legal relation r(R), for all pairs of tuples t1 and t2 in r such that t1(α) =
t2 (α) it is also the case that t1(β) = t2(β)

Using the functional-dependency notation, we say that K is a superkey of R if K→ R. That is, K is a

superkey if, whenever t1[K) = t2 [K], it is also the case that t1[R] = t2[R] (that is, t1 = t2).

Functional dependencies allow us to express constraints that we cannot express with superkeys.
Consider the schema

Loan-info-schema = (loan-number, branch-name, customer-name, amount)

which is simplification of the Lending-schema that we saw earlier. The set of functional
dependencies that we expect to hold on this elation schema is

loan-nurnber → amount loan-number → branch-name

We would not, however, expect the functional dependency

loan-number → customer-name

Page 164
to hold, since, in general, a given loan can be made to more than one customer (for example, to both
members of a husband-wife pair).
We shall use functional dependencies in two ways:

1. To test relations to see whether they are legal under a given set of functional dependencies. If a
relation r is legal under a set F of functional dependencies, we say that r satisfies F.

2. To specify constraints on the set of legal relations. We shall thus concern ourselves with only
those relations that satisfy a given set of functional dependencies. If we wish to constrain ourselves
to relations on schema R that satisfy a set F of functional dependencies, we say that F holds on R.

To see which functional dependencies are satisfied. Observe that A → C is satisfied. There
are two tuples that have an A value of a1. These tuples have the same C value-namely, C1. Similarly,
the two tuples with an A value of a2 have the same C value, C2. There are no other pairs of distinct
tuples that have the same A value. The functional dependency C → A is not satisfied, however. To
see that it is not, consider the tuples t1 = (a2, b3, C2, d3) and

A B C D
a1 B1 C1 d1
a1 B2 c1 d2
a2 B2 c2 d2
a2 B2 C2 d3
a3 B3 C2 d4

Sample relation r.

t2= (a3, b3, C2, d4). These two tuples have the same C values, C2, but they have different A values,
a2 and a3, respectively. Thus, we have found a pair of tuples t1 and t2 such that t1( C) = t2 [C], but
t1 [A] ≠ t2 [A].

Many other functional dependencies are satisfied by r, including, for example, the functional
dependency AB → D. Note that we use AB as a shorthand for {A,B}, to conform with standard
practice. Observe that there is no pair of distinct tuples tl and t2 such that tl [AB] = t2 [AB].
Therefore, if t1 [AB] = t2 [AB], it must be that t1 = t2 and, thus, t1 [D] = t2[D]. So, r satisfies AB→
D.

Some functional dependencies are said to be trivial because they are satisfied by all
relations. For example, A → A is satisfied by all relations involving attribute A. Reading the
definition of functional dependency literally, we see that, for all tuples t1 and t2 such that t1(A] = t2
[A], it is the case that h[A] = t2 [A]. Similarly, AB → A is satisfied by all relations involving
attribute A. In general, a functional dependency of the form α → β is trivial if
β⊆α

To distinguish between the concepts of a relation satisfying a dependency and a dependency

holding on a schema, we return to the banking example. If we consider the customer relation (on
Customer-schema) in Figure 7.3, we see that customer-street→ customer-city is satisfied. However,
we believe that, in the real world, two cities
Customer-name Customer-street Customer-city

Page 165
Jones Main Harrison
Smith North Rye
Hayes Main Harrison
Curry North Rye
Lindsay Park Pittsfield
Tufl1et Putnam Stamford
Williams Nassau Princeton
Adams Spring Pittsfield
Johnson Alma Palo Alto
Glenn Sand Hill Woodside
Brooks Senator Brooklyn
Green Walnut Stamford

The customer relation

L-17 Downtown 1000

L-23 Redwood 2000
L-15 Perryridge 1500
L-14 Downtown 1500
L-93 Mianus 500
L-11 Round Hill 900
L-29 Pownal 1200
L-16 North Town 1300
L-18 Downtown 2000
L-25 Perryridge 2500
L-10 Brighton 2200

The loan relation.

can have streets with the same name. Thus, it is possible, at some time, to have an instance of the
customer relation in which customer-street → customer-city is not satisfied. So, we would not
include customer-street → customer-city in the set of functional dependencies that hold on
Customer-schema.

In the loan relation (on Loan-schema) , we see that the dependency loan-number → amount
is satisfied. In contrast to the case of customer-city and customerstreet in Customer-schema, we do
believe that the real-world enterprise that we are modeling requires each loan to have only one
amount. Therefore, we want to require that loan-number → amount be satisfied by the loan relation
at all times. In other words, we require that the constraint loan-number → amount hold on Loan-
schema.

In the branch relation , we see that branch-name → assets is satisfied, as is assets → branch-
name. We want to require that branch-name → assets hold on Branch-schema. However, we do not
wish to require that assets → branch-name hold, since it is possible to have several branches that
have the same asset value.

Page 166
 In what follows, we assume that, when we design a relational database, we first list those
functional dependencies that must always hold. In the banking example, our list of dependencies
includes the following:

Branch-name branch-city assets

Downtown Brooklyn 9000000
Redwood Palo Alto 2100000
Perryridge Horseneck 1700000
Mianus Horseneck 400000
Round Hill Horseneck 8000000
Pownal Bennington 300000
North Town Rye 3700000
Brighton Brooklyn 7100000

. On Branch-schema:
branch-name → branch-city
branch-name → assets

. On Customer-schema:
customer-name → customer-city
customer-name → customer-street

. On Loan-schema:
loan-number → amount
loan-nll1nber → branch-name

. On Borrower-schema:

No functional dependencies

. On Account-schema:
account-number → branch-name
account-number → balance

. On Depositor-schema:
No functional dependencies

Closure of a Set of Functional Dependencies

It is not sufficient to consider the given set of functional dependencies. Rather, we need to
consider all functional dependencies that hold. We shall see that, given a set F of functional
dependencies, we can prove that certain other functional dependencies hold. We say that such
functional dependencies are "logically implied" by F.

Page 167
 More formally, given a relational schema R, a functional dependency f on R is logically
implied by a set of functional dependencies F on R if every relation instance r(R) that satisfies F also
satisfies f
.
Suppose we are given a relation schema R = (A, B, C, G, H, I) and the set of functional dependencies
A→B
A→C
CG → H
CG → I
B→H

The functional dependency

A→H
is logically implied. That is, we can show that, whenever our given set of functional dependencies
holds on a relation, A → H must also hold on the relation. Suppose that tl and t2 are tuples such that

t1(A] = t2[A]

Since we are given that A → B, it follows from the definition of functional dependency
that

t1(B] = t2[B]

Then, since we are given that B → H, it follows from the definition of functional
dependency that

t1(H] = t2[H]

Therefore, we have shown that, whenever tl and t2 are tuples such that tl [A] = t2 [A],
it must be that tl [H] = t2[H]. But that is exactly the-definition of A → H.

Let F be a set of functional dependencies. The closure of F, denoted by F+, is the set of all
functional dependencies logically implied by F. Given F, we can compute F+ directly from the
formal definition of functional dependency. If F were large, this process would be lengthy and
difficult. Such a computation of F+ requires arguments of the type just used to show that A → H is
in the closure of our example set of dependencies.

Axioms, or rules of inference, provide a simpler technique for reasoning about functional
dependencies. In the rules that follow, we use Greek letters (α, β, γ . . . ) for sets of attributes, and
uppercase Roman letters from the beginning of the alphabet for individual attributes. We use αβ to
denote α U β.

We can use the following three rules to find logically implied functional dependencies. By
applying these rules repeatedly, we can find all of F+ given F. This collection of rules is called
Armstrong's axioms in honor of the person who first proposed it.

. Reflexivity rule. If α is a set of attributes and β ⊆ α then a → β holds.

. Augmentation rule. If α → β holds and γ is a set of attributes, then γα → γβ holds.

Page 168
 → I holds.
. Transitivity rule. If α → β holds and β
Another way of finding that AG → I holds is as follows. We use the
→ γ holds, then α → γ holds.
augmentation rule on A → C to
Armstrong's axioms are sound, infer AG → CG. Applying the transitivity rule to this dependency and CG
→ I, we infer AG → I.
because they do not generate any
incorrect functional
dependencies. They are complete, because,
for a given set F of functional dependencies,
they allow
us to generate all F+. The bibliographical
notes provide references for proofs of
soundness and
completeness.
Although Armstrong's axioms are
complete, it is tiresome to use them
directly for the
computation of F+. To simplify matters
further, we list additional rules. It is possible
to use
Armstrong's axioms to prove that these
rules are correct

. Union rule. If α →β holds and α → γ

holds, then α → βγ
. Decomposition rule. If α → βγ holds,
then α →β holds and α → γ holds.
. Pseudotransitivity rule. If α → β holds
and γβ → δ holds, then αγ → δ holds.

Let us apply our rules to the example

of schema R = (A, B, C, G, H, I) and the set F of
functional dependencies {A → B, A → C, CG
→ H, CG → I, B → H}. We list several
members of
F+ here:

A → H. Since A → B and B → H
hold, we apply the transitivity rule.
Observe that it was
much easier to use Armstrong's axioms to
show that A → H holds than it was to
argue directly from
the definitions, as we did earlier in this
section.

. CG → HI. Since CG → and CG → I, the

union rule implies that CG → HI.
. AG →I. Since A → C and CG → I, the
pseudotransitivity rule implies that A G Page 169
Lesson objectives: NORMALISATIONII
Decomposition
Properties of decomposition
Lossless join decomposition
2NF

DECOMPOSITION

The bad design of a database suggests that we should decompose a relation schema that
has many attributes into several schemas with fewer attributes. Careless decomposition,
however, may lead to another form of bad design.
Consider an alternative design in which we decompose Lending-schema into the
following two schemas:

Branch-customer-schema = (branch-name, branch-city, assets, customer-name)

Customer-loan-schema = (customer-name, loan-number, amount)

Using the lending relation of Figure 7.1, we construct our new relations branch-customer
(Branch-customer) and customer-loan (Customer-loan-schema):

branch-customer = Пbranch-name, branch-city, assets, customer-name (lending)

customer-loan = Пcustomer-name, loan-number, amount (lending)

Of course, there are cases in which we need to reconstruct the loan relation. For example,
suppose that we wish to find all branches that have loans with amounts less than $1000.
No relation in our alternative database contains these data. We need to reconstruct the
lending relation. It appears that we can do so by writing

branch-customer _ customer-loan

Branch name Branch city Assets Customer name

Downtown Brooklyn 9000000 Jones
Redwood Palo Alto 2100000 Smith
Perryridge Horseneck 1700000 Hayes
Downtown Brooklyn . 9000000 Jackson
Mianus Horseneck 400000 Jones
Round Hill Horseneck 8000000 Turner
Pownal Bennington 300000 Williams
North Town Rye 3700000 Hayes
Downtown Brooklyn 9000000 Johnson

Page 170
Perryridge Horseneck 1700000 Glenn
Brighton Brooklyn . 7100000 Brooks

the relation branch customer

Customer name Loan number amount

Jones L-17 1000
Smith L-23 2000
Hayes L-15 1500
Jackson L-14 1500
Jones L-93 500
Turner L-11 900
Williams L-29 1200
Hayes L-16 1300
Johnson L-18 2000
Glenn L-25 2500
Brooks L-10 2200

The relation customer-loan.

The result of computing branch-customer [><I customer-loan. When we compare this

relation and the lending relation with which we started, we notice a difference: Although
every tuple that appears in the lending relation appears in branch-customer [><I
customer-loan, there are tuples in branch-customer [><I customer-loan that are not in
lending. In our example, branch-customer [><I customer-loan has the following
additional tuples

(Downtown, Brooklyn, 9000000, Jones, L-93, 500)

(Perryridge, Horseneck, 1700000, Hayes, L-16, 1300)
(Mianus, Horseneck, 400000, Jones, L-17, 1000)
(North Town, 3700000, Hayes, L-15, 1500)

Consider the query "Find all bank branches that have made a loan in an amount less than
$1000." . we see that the only branches with loan amounts less than $1000 are Mianus
and Round Hill However, when we apply the expression

П branch-name ((J amount < 1000 (branch-customer [><I customer-loan))

we obtain three branch names: Mianus, Round Hill, and Downtown.

A closer examination of this example shows why. If a customer happens to have several
loans from different branches, we cannot tell which loan belongs to which branch. Thus,
when we join branch-customer and customer-loan, we obtain not only the tuples we had
originally in lending, but also several additional tuples. Although we have more tuples in
branch-customer [><I customer-loan, we actually have less information. We are no
longer able, in general, to represent in the database information about which customers
are borrowers from which branch. Because of this loss of in

Page 171
formation, we call the decomposition of Lending-schema into Branch-customer-schema
and customer-loan-schema a lossy decomposition, or a lossy-join decomposition.
Decomposition that is not a lossy-join decomposition is a lossless-join decomposing.

Customer Laon
Branch name Branch city Assets
name number Amount
Downtown Brooklyn 9000000 Jones L-17 1000
Downtown Brooklyn 9000000 Jones L-93 500
Redwood Palo Alto 2100000 Smith L-23 2000
Perryridge Horseneck 1700000 Hayes L-15 1500
Perryridge Horseneck 1700000 Hayes L-16 1300
Downtown Brooklyn 9000000 Jackson L-14 1500
Mianus Horseneck 400000 Jones L-17 1000
Mianus Horseneck 400000 Jones L-93 500
Round Hill Horseneck 8000000 Turner L-11 900
Pownal Bennington 300000 Williams L-29 1200
North Town Rye 3700000 Hayes L-15 1500
North Town Rye 3700000 Hayes L-16 1300
Downtown Brooklyn 9000000 Johnson L-18 2000
Perryridge Horseneck 1700000 Glenn L-25 2500
Brighton Brooklyn 7100000 Brooks L-10 2200

The relation branch-customer [><I customer-loan.

It should be clear from our example that a lossy-join decomposition is, in general, a bad
database design.
Why is the decomposition lossy? There is one attribute in common between Branch
customer-schema and Customer-loan-schema:

Branch-customer-schema n Customer-loan-schema = {customer-name}

The only way that we can represent a relationship between, for example, loan-number
and branch-name is through customer-name. This representation is not adequate because
a customer may have several loans, yet these loans are not necessarily obtained from the
same branch.

Let us consider another alternative design, in which we decompose Lending-schema into

the following two schemas:

Branch-schema = (branch-name, branch-city, assets)

Loan-info-schema = (branch-name, customer-name, loan-number, amount)

There is one attribute in common between these two schemas:

Branch-loan-schema n Customer-loan-schema = {branch-name}

Page 172
Thus, the only way that we can represent a relationship' between, for example, customer-
name and assets is through branch-name. The difference between this example and the
preceding one is that the assets of a branch are the same, regardless of the customer to
which we are referring; whereas the lending branch associated with a certain loan amount
does depend on the customer to which we are referring. For a given branch-name, there
is exactly one assets value and exactly one branch-city;

Where as a similar statement cannot be made for customer-name. That is, the functional
dependency

branch-name → assets branch-city

holds, but customer-name does not functionally determine loan-number.

The notion of loss less joins is central to much of relational-database design. Therefore,
we restate the preceding examples more concisely and more formally. Let. R be a relation
schema. A set of relation schemas {R1, R2,..., Rn} is a decomposition of R if

R = Rl U R2 U ... U Rn

That is, {R1, R2,..., Rn} is a decomposition of R if, for i = 1,2,..., n, each Riis a
subset of R, and every attribute in R appears in at least one Ri.

Let r be a relation on schema R, and let Ti = П Ri (T) for i = 1,2,..n. That is, {r1, r2,
r3……rn} is the database that results from decomposing R into {R1, R2" . . , Rn}.
It is always the case that

r⊆ r1 [><I r2 [><I … [><I rn

To see that this assertion is true, consider a tuple t in relation r. When we compute the
relations r1, r2, r3, ... rn , the tuple t gives rise to one tuple ti in each ri, i = 1,2, . . . , n.
These n tuples combine to regenerate t when we compute r1, [><Ir2…[><I rn. The details
'are left for you to complete as an exercise. Therefore, every tuple in r appears in r1,
[><Ir2…[><I rn.

In general, r ≠ r1 [><I r2 [><I…. [><I rn. As an illustration, consider our earlier

example, in which

• n = 2.
• R. = Lending-schema.
• R 1 = Branch-customer-schema.
• R2 = Customer-Loan-schema.
• r = the relation shown in Figure 7.1.
• r1 = the relation shown in Figure 7.2
• r2 = the relation shown in Figure 7.10.
• r1 [><I r2 = the relation shown in Figure 7.11.

Page 173
To have a lossless-join decomposition, we need to impose constraints on the set of
possible relations. We found that the decomposition of Lending-schema into Branch-
schema and Loan-info-schema is lossless because the functional dependency

branch-name → branch:...city assets

hold on branch schema.

We shall show how to test whether decomposition is lossless-join decomposition in the

next few sections. A major part of this chapter deals with the questions of how to specify
constraints on the database, and how to obtain lossless-join decompositions that avoid the
pitfalls represented by the examples of bad database designs that we have seen in this
section.

DESIRABLE PROPERTIES OF DECOMPOSITION

We can use a given set of functional dependencies in designing a relational database in

which most of the undesirable properties do not occur. When we design such systems, it
may become necessary to decompose a relation into several smaller relations.

In this section, we outline the desirable properties of a decomposition of a relational

schema. In later sections, we outline specific ways of decomposing a relational schema to
get the properties we desire. We illustrate our concepts with the Lending schema

Lending-schema = (branch-name, branch-city, assets, customer-name,

loan-number, amount)

The set F of functional dependencies that we require to hold on Lending-schema are

branch-name -+ branch-city assets

loan-number -+ amount branch-name

Lending-schema is an example of a bad database design. Assume that we decompose it

to the following three relations:

Branch-schema = (branch-name, branch-city, assets)

Loan-schema = (loan-number, branch-name, amount)
Borrower-schema = (customer-name, loan-number)

We claim that this decomposition has several desirable properties, which we discuss next.

LOSSLESS-JOIN DECOMPOSITION

When we decompose a relation into a number of smaller relations, it is crucial that the
decomposition be lossless. We must first present a criterion for determining whether a
decomposition is lossy.

Page 174
Let R be a relation schema, and let F be a set of functional dependencies on R. Let R1
and R2 form a decomposition of R. This decomposition is a lossless-join decomposition
of R if at least one of the following functional dependencies is in F+:

R1 ∩ R2 → Rl .
R1 ∩ R2 → R2

In other words, if R1 ∩ R2 forms a superkey of either R1 or R2, the decomposition of R

is a lossless-join decomposition. We can use attribute closure to efficiently test for
superkeys, as we have seen earlier.

We now demonstrate that our decomposition of Lending-schema is a lossless-join

decomposition by showing a sequence of steps that generate the decomposition. We
begin by decomposing Lending-schema into two schemas:

Branch-schema = (branch-name, branch-city, assets)

Loan-info-schema = (branch-name, customer-name, loan-number, amount)

Since branch-name → branch-city assets, the augmentation rule for functional depen-
dencies implies that

branch-name → branch-name branch-city assets

Since Branch-schema n Loan-info-schema = {branch-name}, it follows that our initial

decomposition is a lossless-join decomposition. .
Next, we decompose Loan-info-schema into

Loan-schema = (loan-number, branch-name, amount)

Borrower-schema = (customer-name, loan-number)

This step results in a lossless-join decomposition, since loan-number is a common at-

tribute and loan-number → amount branch-name.

For the general case of decomposition of a relation into multiple parts at once, the test for
lossless join decomposition is more complicated. See the bibliographical notes for
references on the topic.

While the test for binary decomposition is clearly a sufficient condition for
lossless join, it is a necessary condition only if all constraints are functional
dependencies. We shall see other types of constraints later (in particular, a type of
constraint called multivalued dependencies), that can ensure that a decomposition is
lossless join even if no functional dependencies are present.

SECOND NORMAL FORM

The general requirements of 2NF are:

• Remove subsets of data that apply to multiple rows of a table and place them in
separate rows.

Page 175
 • Create relationships between these new tables and their predecessors through the
use of foreign keys.

These rules can be summarized in a simple statement: 2NF attempts to reduce the
amount of redundant data in a table by extracting it, placing it in new table(s) and
creating relationships between those tables.

Let's look at an example. Imagine an online store that maintains customer information in
a database. Their Customers table might look something like this:

CustNum FirstName LastName Address City State ZIP

1 John Doe 12 Main Street Sea Cliff NY 11579

2 Alan Johnson 82 Evergreen Sea Cliff NY 11579

Tr
3 Beth Thompson 1912 NE 1st Miami FL 33157
St
4 Jacob Smith 142 Irish Way South Bend IN 46637
5 Sue Ryan 412 NE 1st St Miami FL 33157

A brief look at this table reveals a small amount of redundant data. We're storing the
"Sea Cliff, NY 11579" and "Miami, FL 33157" entries twice each. Now, that might not
seem like too much added storage in our simple example, but imagine the wasted space if
we had thousands of rows in our table. Additionally, if the ZIP code for Sea Cliff were to
change, we'd need to make that change in many places throughout the database.

In a 2NF-compliant database structure, this redundant information is extracted and stored

in a separate table. Our new table (let's call it ZIPs) might look like this:

ZIP City State

11579 Sea Cliff NY
33157 Miami FL
46637 South Bend IN

If we want to be super-efficient, we can even fill this table in advance -- the post office
provides a directory of all valid ZIP codes and their city/state relationships. Surely,
you've encountered a situation where this type of database was utilized. Someone taking
an order might have asked you for your ZIP code first and then knew the city and state
you were calling from. This type of arrangement reduces operator error and increases
efficiency.

Page 176
Now that we've removed the duplicative data from the Customers table, we've satisfied
the first rule of second normal form. We still need to use a foreign key to tie the two
tables together. We'll use the ZIP code (the primary key from the ZIPs table) to create
that relationship. Here's our new Customers table:

CustNum FirstName LastName Address ZIP

1 John Doe 12 Main Street 11579
2 Alan Johnson 82 Evergreen Tr 11579
3 Beth Thompson 1912 NE 1st St 33157
4 Jacob Smith 142 Irish Way 46637
5 Sue Ryan 412 NE 1st St 33157

We've now minimized the amount of redundant information stored within the database
and our structure is in second normal form.

POINTS TO PONDER

• The bad design of a database suggests that we should decompose a relation

schema that has many attributes into several schemas with fewer attributes.

• when we decompose a relation into a number of smaller relations, it is crucial that

the decomposition be lossless

• 2NF attempts to reduce the amount of redundant data in a table by extracting it,
placing it in new table(s) and creating relationships between those tables.

• We can use a given set of functional dependencies in designing a relational

database in which most of the undesirable properties do not occur

• When we decompose a relation into a number of smaller relations, it is crucial that

the decomposition be lossless

• 2NF remove subsets of data that apply to multiple rows of a table and place them
in separate rows.

Page 177
NORMALISATION-III
Comparison of BCNF & 3NF
4NF

BOYCE-CODD NORMAL FORM

Using functional dependencies, we can define several normal forms that represent
"good" database designs.

Definition

One of the more desirable normal forms that we can obtain is Boyce-Codd normal form
(BCNF). A relation schema R is in BCNF with respect to a set F of functional dependencies if,
for all functional dependencies in F+ of the form α →β, where α ⊆ R and β ⊆ R, at least one
of the following holds:

. α → β is a trivial functional dependency (that is, β ⊆ α). .

α is a superkey for schema R.

A database design is in BCNF if each member of the set of relation schemas that constitutes the
design is in BCNF. .

As an illustration, consider the following relation schemas and their respective

functional dependencies: .

. Customer-schema = (customer-name, customer-street, customer-city)

customer-name -t customer-street customer-city

. Branch-schema = (branch_name, assets, branch-city)

branch-name -t assets branch-city

. Loan-info-schema = (branch-name, customer-name, loan-number, amount)

loan-number -t amount branch-name

We claim that Customer-schema is in BCNF. We note that a candidate key for the,
schema is cust9mer-name. The only nontrivial functional dependencies that hold on Customer-
schema have customer-name on the left side of the arrow. Since customer-name is a candidate
key, functional dependencies with customer-name on the left side do not violate the definition

Page 178
of BCNF. Similarly, it can be shown easily that the relation schema Branch-schema is in
BCNF.

The schema Loan-info-schema, however, is not in BCNF. First, note that loan-number
is not a superkey for Loan-info-schema, since we could have a pair of tuples representing a
single loan made to two people-:-for example, .
(Dowhtown, John Bell, L-44, 1000)
(Downtown, Jane Bell, L-44, 1000)

Because we did not list functional dependencies that rule out the preceding case, loan-number
is not a candidate key. However, the functional dependency loan-nurnber → amount is
nontriviaL Therefore, Loan-info-schema does not satisfy the definition of BCNF.

We claim that Loan-info-schema is not in a desirable form, since it suffers from the
problem of repetition of information. We observe that, if there are several customer names
associated with a loan, in a relation on Loan-info-schema, then we are forced to repeat the
branch name and the amount once for each customer. We can eliminate this redundancy by
redesigning our database such that all schemas are in BCNF. One approach to this problem is
to take the existing non-BCNF design as a starting point, and to decompose those schemas that
are not in BCNF. Consider the decomposition of Loan-info-schema into two schemas:
Loan-schema = (loan-number, branch-name, amount)
Borrower-schema = (customer-name, loan-number)

This decomposition is a lossless-join decomposition.

To determine whether these schemas are in BCNF, we need to determine what

functional dependencies apply to them. In this example, it is easy to see that

loan-number → amount branch-name

applies to the Loan-schema, and that only trivial functional dependencies apply to Borrower-
schema. Although loan-number is not a superkey for Loan-info-schema, it is a candidate key
for Loan-schema. Thus, both schemas of our decomposition are in SCNF.

It is now possible to avoid redundancy in the case where there are several customers
associated with a loan. There is exactly one tuple for each loan in the relation on Loan-schema,
and one tuple for each customer of each loan in the relation on Borrower-schema. Thus, we do
not have to repeat the branch name and the amount once for each customer associated with a
loan.
Often testing of a relation to see if it satisfies BCNF can be simplified:

. To check if a nontrivial dependency α → β causes a violation of SCNF, com

put α+ (the attribute closure of α), and verify that it includes all attributes of
R; that is, it is a superkey of R.

. To check if a relation schema R is in SCNF, it suffices to check only the depen dencies in the
given set F for violation 'of BCNF, rather than check all dependencies in F+ .

Page 179
We can show that if none of the dependencies in F causes a violation of SCNF, then none of
the dependencies in F+ will cause a violation of SCNF either.

Unfortunately, the latter procedure does not work when a relation is decomposed. That
is it does not suffice to use F when we test a relation Ri in a decomposition of R, for violation
of BCNF. For example" consider relation schema R (A, B, C, D, E), with functional
dependencies F containing A → Band BC → D. Suppose this were decomposed into R1(A, B)
and R2(A, C, D, E). Now, neither of the dependencies in F contains only attributes from (A, C,
D, E) so we might be misled into thinking R2 satisfies BCNF. In fact, there is a dependency AC
→ D in F+ (which can be inferred using the pseudotransitivity rule from the two dependencies
in F), which shows that R2 is not in BCNF. Thus, we may need a dependency that is in F+, but
is not in F, to show that a decomposed relation is not in BCNF.

An alternative BCNF test is sometimes easier than computing every dependency in F+. To
check if a relation Ri in a decomposition of R is in BCNF, we apply this test:

. For every subset a of attributes in R.i, check that a+ (the attribute closure of a
under F) either includes no attribute of Ri - a, or includes all attributes of Ri.

If the condition is violated by some set of attributes a in Ri, consider the following functional
dependency, which can be shown to be present in F+:

α → (α+ - α)∩ Ri. .

The above dependency shows that Ri violates BCNF, and is a "witness" for the violation. The
BCNF decomposition algorithm, which we shall see in Section 7.6.2, makes use of the witness.

Third Normal Form

As we saw earlier, there are relational schemas where a BCNF decomposition cannot
be dependency preserving. For such schemas, we have two alternatives if we wish to check if
an update violates any functional dependencies:

. Pay the extra cost of computing joins to test for violations.

. Use an alternative decomposition, third normal form (3NF), which we present below, which
makes testing of updates cheaper. Unlike BCNF, 3NF decompositions may contain some
redundancy in the decomposed schema.

We shall see that it is always possible to find a lossless-join, dependency-preserving

decomposition that is in 3NF. Which of the two alternatives to choose is a design decision to
be made by the database designer on the basis of the application requirements.

DEFINITION

BCNF requires that all nontrivial dependencies be of the form α → β, where α is a

super key. 3NF relaxes this constraint slightly by allowing nontrivial functional dependencies
whose left side is not a superkey.

Page 180
 A relation schema R is in third normal form (3NF) with respect to a set F of functional
dependencies if, for all functional dependencies in F+ of the form α → β, where α ⊆ R and β
⊆ R, at least one of the following holds:

. α → β os a trivial functional dependency.

. α is a superkey for R.
. Each attribute A in β - α is contained in a candidate key for R.

Note that the third condition above does not say that a single candidate key should contain all
the attributes in β - α; each attribute A in β - α may be contained in a
different candidate key.

The first two alternatives are the same as the two alternatives in the definition of
BCNF. The third alternative of the 3NF definition seems rather unintuitive, and it is not
obvious why it is useful. It represents, in some sense, a minimal relaxation of the BCNF
conditions that helps ensure that every schema has a dependency-preserving decomposition
into 3NF. Its purpose will become more clear later, when we study
decomposition into 3NF.

Observe that any schema that satisfies BCNF also satisfies 3NF, since each of its
functional dependencies would satisfy one of the first two alternatives. BCNF is therefore a
more restrictive constraint than is 3NF.
The definition of 3NF allows certain functional dependencies that are not allowed in BCNF. A
dependency α → β that satisfies only the third alternative of the 3NF definition is not allowed
in BCNF, but is allowed in 3NF.

Let us return to our Banker-schema example (Section 7.6). We have shown that this
relation schema does not have a dependency-preserving, lossless-join decomposition into
BCNF. This schema, however, turns out to be in 3NF. To see that it is, we note that {customer-
name, branch-name} is a candidate key for Banker-schema, so the only attribute not contained
in a candidate key for Banker-schema is banker-name. The only nontrivial functional
dependencies of the form

α → banker-name
include {customer-name, branch-name} as part of Q. Since {customer-name, branch-name} is
a candidate key, these dependencies do not violate the definition of 3NF.
As an optimization when testing for 3NF, we can consider only functional dependencies in the
given set F, rather than in F+. Also, we can decompose the dependencies in F so that their.
right-hand side consists of only single attributes, and use the resultant set in place of F.

Given a dependency α → β, we can use the same attribute-closure-based technique that

we used for BCNF to check if α is a superkey. If α is not a superkey, we have to verify
whether each
attribute in β is contained in a candidate key of R; this test is rather more expensive,
since it involves finding candidate keys. In fact, testing for 3NF has been .shown to be NP-
hard; thus, it is very unlikely that there is a polynomial time complexity algorithm for the task.

Page 181
COMPARISON OF BCNF AND 3NF

Of the two normal forms for relational-database schemas, 3NF and BCNF, there are
advantages to 3NF in that we know that it is always possible to obtain a 3NF design without
sacrificing a lossless join or dependency preservation. Nevertheless, there are disadvantages to
3NF: If we do not eliminate all transitive relations schema dependencies, we may have to use
null values to represent some of the possible meaningful relationships among data items, and
there is the problem of repetition of information.

As an illustration of the null value problem, consider again the Banker-schema and its
associated functional dependencies. Since banker-name → branch-name, we may want to
represent relationships between values for banker-name and values for branch-name in our
database. If we are to do so, however, either there must be a corresponding value for customer-
name, or we must use a null value for the attribute customer-name`1.

Customer-name bank-name branch-name

Jones Johnson Perryridge

Smith Johnson Perryridge
Hayes Johnson Perryridge
Jackson Johnson Perryridge
Curry Johnson Perryridge
Turner Johnson Perryridge
An instance of Banker-schema.

As an illustration of the repetition of information problem, consider the instance of

Banker-schema. Notice that the information indicating that Johnson is working at the
Perryridge branch is repeated.
Recall that our goals of database design with functional dependencies are:
1. BCNF
2. Lossless join
3. Dependency preservation

Since it is not always possible to satisfy all three, we may be forced to choose between
BCNF and dependency preservation with 3NF.
It is worth noting that SQL does not provide a way of specifying functional dependencies,
except for the special case of declaring superkeys by using the primary key or unique
constraints. It is possible, although a little complicated, to write assertions that enforce a
functional dependency, unfortunately testing the assertions would be very expensive in most
database systems. Thus even if we had a dependency-preserving decomposition, if we use
standard SQL we would not be able to efficiently test a functional dependency whose left-hand
side is not a key.

Although testing functional dependencies may involve a join if the decomposition is not
dependency preserving, we can reduce the cost by using materialized views, which many
database systems support. Given a BCNF decomposition that is not dependency preserving, we
consider each dependency in a minimum cover Fc that is not preserved in the decomposition.
For each such dependency α → β, we define a materialized view that computes a join of all

Page 182
relations in the decomposition, and projects the result on αβ. The functional dependency can
be easily tested on the materialized view, by means of a constraint unique (α). On the negative
side, there is a space and time overhead due to the materialized view, but on the positive side,
the application programmer need not worry about writing code to keep redundant data
consistent on updates; it is the job of the database system to maintain the materialized view,
that is, keep up up to date when the database is updated
Thus, in case we are not able to get a dependency-preserving BCNF decomposition, it is
generally preferable to opt for BCNF, and use techniques such as materialized views to reduce
the cost of checking functional dependencies.

FOURTH NORMAL FORM

Some relation schemas, even though they are in BCNF, do not seem to be sufficiently
normalized, in the sense that they still suffer from the problem of repetition of information.
Consider again our banking example. Assume that, in an alternative design for the bank
database schema, we have the schema

BC-schema = (loan-number, customer-name, customer-street, customer-city)

The astute reader will recognize this schema as a non-BCNF schema because of the functional
dependency

customer-name → customer-street customer-city

that we asserted earlier, and because customer-name is not a key for BC-schema. However,
assume that our bank is attracting wealthy customers who have several addresses (say, a winter
home and a summer home). Then, we no longer wish to enforce the functional dependency
customer-name → customer-street customer-city. If we remove this functional
dependency, we find BC-schema to be in BCNF with respect to our modified set of functional
dependencies. Yet, even though BC-schema is now in BCNF, we still have the problem of
repetition of information that we had earlier.

To deal with this problem, we must define a new form of constraint, called a mul-
tivalued dependency. As we did for functional dependencies, we shall use multivalued
dependencies to define a normal form for relation schemas. This normal form, called fourth
normal form (4NF), is more restrictive than BCNF. We shall see that every 4NF schema is also
in BCNF, but there are BCNF schemas that are not in 4NF.

MULTIVALUED DEPENDENCIES

Functional dependencies rule out certain tuples from being in a relation. If A → B, then
we cannot have two tuples with the same A value but different B values. Multivalued
dependencies, on the other hand, do not rule out the existence of certain tuples. Instead, they
require that other tuples of a certain form be present in the relation. For this reason, functional
dependencies sometimes are referred to as equality generating dependencies, and multivalued
dependencies are referred to as tuple generating dependencies.
Let R be a relation schema and let α ⊆ R and β ⊆ R. The multivalued dependency

Page 183
 α ⊆→→β

holds on R if, in any legal relation r(R), for all pairs of tuples t1 and t2 in r such that t1[α] =
t2[α], there exist tuples t3 and t4 in r such that

tr[α] = t2[α] = t3[α] = t4[α]

t3 [β] = td{β]
t3[R - β] = t2[R - β]
t4 [β] .= t2 [β]
t4[R - β] = t1(R - β]

α β R- α - β
T1 A1 …..ai ai +1 ….aj Aj +1 …an
T2 A1 …..ai bi + 1 … bj Bj +1 ….bn
T3 A1 …..ai Ai+1 …. aj Bj +1 ….bn
T4 A1 …..ai Bi +1 ….bj Aj +1 … an

Tabular representation of α →→ β

This definition. is less complicated than it appears to be. Figure'7.16 gives a tabular
picture of t1, t2, t3 and t4. Intuitively, the multivalued dependency α →→ β says that the
relationship between α and α is independent of the relationship between α and R - β. If the
multivalued dependency α →→ β is satisfied by all relations on schema R, then α →→ β is a
trivial multivalued dependency on schema R. Thus α →→ β is trivial if β ⊆ α or β U α = R.

To illustrate the difference between functional and multivalued dependencies, we

consider the BC-schema again, and the relation bc (BC-schema). We must repeat the loan
number once for each address a customer has, and we must repeat the address for each loan a
customer has. This repetition is unnecessary, since the relationship between a customer and his
address is independent of the relationship between that customer and a loan. If a customer (say,
Smith) has a loan (say, loan number L-23), we want that loan to
be associated with all Smith's addresses. Thus, the relation of Figure 7.18 is illegal. To
make this relation legal, we need to add the tuples (L-23, Smith, Main, Manchester) and (L-27,
Smith, North, Rye) to the bc relation

Comparing the preceding example with our definition of multivalued dependency, we see that
we want the multivalued dependency

customer-name →→ customer-street customer-city

to hold. (The multivalued dependency customer-name →→ loan-number will do as well. We

shall soon see that they are equivalent.)
As with functional dependencies, we shall use multivalued dependencies in two ways:

[Link] test relations to determine whether they are legal under a given set of functional and
multivalued dependencies

Page 184
2. To specify constraints on the set of legal relations; we shall thus concern ourselves with only
those relations that satisfy a given set of functional and multivalued dependencies

Loan-number Customer-name Customer-street Customer-city

L-23 Smith North Rye
L-23 Smith Main Manchester
L-93 Curry Lake Horseneck

Relation bc: An example of redundancy in a BCNF relation.

Loan-number Customer-name Customer-street customercity

L-23 Smith North Rye
L-27 Smith Main Manchester

An illegal bc relation.

Note that, if a relation r fails to satisfy a given multivalued dependency, we can construct a
relation r’ that does satisfy the multivalued dependency by adding tuples to r.
Let D denote a set of functional and multivalued dependencies. The closure D+ of D is
the set of all functional and multivalued dependencies logically implied by o. As we did for
functional dependencies, we can compute D+ from 0, using the formal definitions of functional
dependencies and multivalued dependencies. We can manage with such reasoning for very
simple multivalued dependencies. Luckily, multivalued dependencies that occur in practice
appear to be quite simple. For complex dependencies, it is better to reason about sets of
dependencies by using a system of inference rules.
From the definition of multivalued dependency, we can derive the following rule:
. If α → β, then α →→ β.
In other words, every functional dependency is also a multivalued dependency.

DEFINITION OF FOURTH NORMAL FORM

Consider again our BC-schema example in which the multivalued dependency

customer-name →→ customer-street customer-city holds, but no nontrivial functional de-
pendencies hold. We saw in the opening paragraphs of Section 7.8 that, although BCschema is
in BCNF, the design is not ideal, since we must repeat a customer's address information lor
each loan. We shall see that we can use the given multivalued dependency to improve the
database design, by decomposing BC-schema into a fourth normal form decomposition.

A relation schema R is in fourth normal form (4NF) with respect to a set 0 of functional
and multivalued dependencies if, for all multivalued dependencies in D+ of the form α →→ β,
where α ⊆ R and β ⊆ R, at least one of the following holds

. α →→ β is a trivial multivalued dependency.

. α is a superkey for schema R.

Page 185
A database design is in 4NF if each member of the set of relation schemas that constitutes the
design is in 4NE

Note that the definition of 4NF differs from the definition of BCNF in only the use of
multivalued dependencies instead of functional dependencies. Every 4NF schema is in
BCNF. To see this fact, we note that, if a schema R is not in BCNF, then there is

result := {R}; done := false;

compute D+; Given schema Ri, let Di denote the restriction of D+ to Ri while (not done) do
if (there is a schema Ri in result that is not in 4NF W.r.t.- Di)
then begin
let α →→ β a nontrivial multivalued dependency that holds on Ri such that α → Ri is not in
Di, and α ∩ β = φ;
result := (result - Ri) U (Ri - β U (α , β);
end
else done := true;

4NF decomposition algorithm.

a nontrivial functional dependency α → β holding on R, where a is not a superkey.

Since α → β implies α →→ β , R cannot be in 4NF.

Let R be a relation schema, and let R1, R2,. . . , Rn be a decomposition of R. To check

if each relation schema Ri in the decomposition is in 4NF, we need to find what multivalued
dependencies hold on each Ri. Recall that, for a set F of functional dependencies, the
restriction Fi of F to Ri is all functional dependencies in F+ that include only attributes of Ri.
Now consider a set D of both functional and multivalued dependencies. The restriction of D to
Ri is the set Di consisting of
1. All functional dependencies in D+ that include only attributes of Ri
2. All multivalued dependencies of the form
α →→ β ∩ Ri
where α ⊆ Ri and α →→ β is in D+ .

POINTS TO PONDER

• A relation schema R is in BCNF with respect to a set F of functional dependencies if,

for all functional dependencies in F+ of the form α →β

• third normal form (3NF), which we present below, which makes testing of updates
cheaper

• Multivalued dependencies do not rule out the existence of certain tuples Instead, they
require that other tuples of a certain form be present in the relation.

• Every 4NF schema is also in BCNF, but there are BCNF schemas that are not in 4NF.

Page 186
Page 187