# 3.3. Normalization¶

In this chapter we discuss some aspects of how a database is structured - what relation schemas should we use to store our data? While the material in this chapter is deeply rooted in relational database theory, the basic concepts can be understood without the theoretical foundation, and are important for all database practitioners. If you are reading this chapter without having read earlier chapters on the relational model of the database, note we use the terms relation, attribute, and tuple in discussing the objects in our database; these terms closely correspond to the terms table, column, and row in relational database systems.

## 3.3.1. Introduction¶

Normalization is the process of modifying a database structure to meet certain requirements. These requirements are defined by a series of normal forms, which we will define shortly.

A primary goal of normalization is to make it easier to maintain a correct collection of data. Correct data is complete and self-consistent. The database should not contain data contradicting what we understand to be true.

There are a few clues that can indicate a database is susceptible to common kinds of data corruption. A very big clue is when a database exhibits redundancy, that is, when the same facts are recorded multiple times. Another clue is when the database contains NULL in many places. When these issues are present in a relation, it is usually also the case that the relation is doing too many things. Relations work best when they contain data regarding a single thing or concept. It can sometimes be difficult to detect that a relation is doing too much, though, which is why redundancy and excessive NULLs are such useful clues.

### 3.3.1.1. Modification anomalies¶

There are three common types of errors that we can consider to better understand the need for normalization. Each of these modification anomalies arise from one of the data modification operations available to us: insert, update, and delete. We can illustrate each of these with the relation pictured below, which lists information about some classes and teachers at a fictional school. The relation gives the class name, starting time, room number, instructor name, instructor office number, and instructor department. Right away, we should be concerned that there is information in the relation about both classes and instructors.

classes

class_name

time

classroom

instructor

office

department

Algebra I

8:00

C01

Mr. Reyes

B24

Math

Geometry

10:00

C01

Mr. Reyes

B24

Math

World History

9:00

C15

Ms. Tan

A11

Humanities

English Literature

10:00

C09

Ms. Larsen

A05

Humanities

Physics

11:00

C06

Ms. Musa

B22

Science

Chemistry

13:00

C17

Ms. Musa

B22

Science

Music

9:00

C25

Mr. Pal

A03

Humanities

This relation also exhibits redundancy. We are given the facts that Mr. Reyes is in the Math department and his office is in room 124 multiple times, for example. Note that Mr. Reyes appearing multiple times is not itself redundancy, as each appearance is a new fact: Mr. Reyes teaches Algebra I, and Mr. Reyes teaches Geometry. We do not have any NULLs in this example, but we will see shortly how they might appear when we add or remove data.

#### 3.3.1.1.1. Insert anomaly¶

Consider what happens when a new instructor joins the faculty at the school. Mr. Hassan is a new faculty member in the department of Math, but he has not yet been assigned any classes to teach. How should we add Mr. Hassan to the database? There are a few options, but none of them are good - whatever we do, we must provide values for class_name, classroom, and time in our new tuple. We might think that NULL is the best choice for each of these attributes, as otherwise we must create fake class information. Either way, we are making trouble for ourselves later on - our database now contains a tuple that must be handled in a special fashion, different from the other tuples in the relation.

#### 3.3.1.1.2. Delete anomaly¶

Now, consider what happens when Ms. Tan takes a job at another school. If we are incautious, we will delete the tuple for Ms. Tan - removing World History from our list of classes altogether. Similarly, we cannot remove English Literature from the list of classes without removing all information about Ms. Larsen. The only way to avoid these issues with our current database design is to replace the existing values with NULLs. As with the insert anomaly example, this leaves us with tuples that require special handling.

#### 3.3.1.1.3. Update anomaly¶

Update anomalies are a direct consequence of the redundancy in our database. Consider what happens when Mr. Reyes changes offices. If we are incautious, we will update the tuple listing Mr. Reyes as the teacher of Algebra I, but forget to update the tuple for Geometry, leaving our data internally consistent. Mr. Reyes will be listed as having two different offices, without any indication which is correct. To avoid trouble, we must remember to always update all classes for which Mr. Reyes is the instructor.

### 3.3.1.2. Example solution¶

Normalizing the classes relation will prevent each of the situations above. In effect, normalization requires us to structure relations such that the data is expressed in a very simple and consistent form. We typically achieve normalization by decomposing a relation into multiple smaller relations.

Informally, in a normalized relation, some thing or concept is uniquely identified by a primary key composed of one or more attributes and every other attribute represents a single-valued fact about the thing or concept only. For our example, the classes relation describes classes; it has class_name as a primary key, and classroom, time, and instructor as single-valued attributes. (An example of an attribute that is not single-valued would be a list of students in the class. We call such an attribute multi-valued.) However, office and department are not really facts about a class; instead, they are facts about instructors. These extended facts need to be removed to another relation through decomposition of the classes relation:

classes

class_name

time

classroom

instructor

Algebra I

8:00

C01

Mr. Reyes

Geometry

10:00

C01

Mr. Reyes

World History

9:00

C15

Ms. Tan

English Literature

10:00

C09

Ms. Larsen

Physics

11:00

C06

Ms. Musa

Chemistry

13:00

C17

Ms. Musa

Music

9:00

C25

Mr. Pal

instructors

name

office

department

Mr. Reyes

B24

Math

Ms. Tan

A11

Humanities

Ms. Larsen

A05

Humanities

Ms. Musa

B22

Science

Mr. Pal

A03

Humanities

Note how we have eliminated redundancy through this decomposition. If we need to update office information for an instructor, there is exactly one tuple to update. We also no longer need to worry about modification anomalies. Adding or removing an instructor is completely independent of adding or removing classes; this also removes any need for excessive NULLs in the classes relation 1.

## 3.3.2. Normal forms¶

The concept of normalization originates with the relational model itself. Additional refinements have been added over time, leading to a series of normal forms, which mostly build on earlier normal forms. We will not study every normal form that has been proposed, but focus on the forms which are most useful and most likely to be of value in most applications. The first form we consider is appropriately named the first normal form, abbreviated 1NF. We proceed with the second, third, and fourth normal forms (2NF, 3NF, 4NF) as well as Boyce-Codd normal form (BCNF), which fits in between 3NF and 4NF.

When a database meets the requirement for a normal form, we say that the database is in the form. As commonly defined, most normal forms include a requirement that earlier normal forms are also met. Therefore, any database that is in 4NF is necessarily also in 1NF, 2NF, 3NF, and BCNF; a database in BCNF is also in 3NF and below; and so forth. However, it is also true that higher forms address less frequently occurring situations, so, for example, a database that has been restructured to be in 3NF is very likely to also be in BCNF or even 4NF. 3NF is generally considered the minimum requirement a database must meet to be considered “normalized”.

To explain most of the normal forms, we first need to provide some additional foundation, covered in the next few sections. However, we can explain 1NF immediately. 1NF requires that the domain of an attribute of a relation contains atomic values only. Atomic here simply means that we cannot usefully break the value down into smaller parts. Non-atomic elements include compound values, arrays of values, and relations. For example, a character string containing an author’s name may be atomic 2, but a string identifying a book by author and title is probably compound; a list of authors would be an array; and a table of values giving a book’s publication history (including publisher, year, ISBN, etc. for each publication) would be a relation. To meet the 1NF requirements, compound values should be broken into separate attributes, while arrays and relations should be broken out into their own relations (with a foreign key referencing the original relation).

1NF is often described as simply part of the definition of a relational database, and early relational database systems indeed provided no capabilities that would permit violations of 1NF. Some modern database systems now provide support for compound values, in the form of user-defined types, and array values. While 1NF technically remains a requirement for all higher normal forms, for certain applications these violations of 1NF may be highly useful. Some authors have argued for permitting relation-valued attributes as well.

## 3.3.3. Keys and superkeys¶

This section reiterates some material from Chapter 3.1 in which we defined the term key, but in a bit more detail. We start by defining a more general term, superkey.

A superkey of a relation is some subset of attributes of the relation which uniquely identifies any tuple in the relation. Consider the library relation below (we will be using this example extensively):

library

author

title

year

genre

author_birth

author_death

section

Ralph Ellison

Invisible Man

1952

fiction

1914-03-01

1994-04-16

literature

Jhumpa Lahiri

Unaccustomed Earth

2008

fiction

1967-07-11

literature

J.R.R. Tolkien

The Hobbit

1937

fantasy

1892-01-03

1973-09-02

speculative fiction

Isabel Allende

The House of the Spirits

1982

magical realism

1942-08-02

literature

J.R.R. Tolkien

The Fellowship of the Ring

1954

fantasy

1892-01-03

1973-09-02

speculative fiction

Ursula K. Le Guin

The Dispossessed

1974

science fiction

1929-10-21

2018-01-22

speculative fiction

(The blank entries for author_death in this table represent NULLs. The authors are still living at the time of this writing.)

We assert that the set of attributes {author, title, and year} is a superkey for the library relation.

The definition of superkey applies not just to the current data in the relation, but to any data we might possibly store in the relation. That is, a superkey is not a transitory property of the data, but a constraint we impose on the data. For example, although each publication year listed in the year column above is unique to its book, that cannot be guaranteed for future books we might add to the relation. Therefore the set {year} is not a superkey for library.

A second, and equivalent definition of superkey is as a subset of attributes of the relation that are guaranteed to contain a unique setting of values for any tuple in the relation. For our example, this means there can never be two books in the library relation which share the same author, title, and year. From this second definition and the definition of a relation, we note that every relation has at least one superkey: the set of all attributes of the relation. The set {author, title, year, genre, author_birth, author_death, section} is a superkey for the library relation simply because every tuple in the relation must be unique.

We can further state that any subset of attributes of the relation which is a superset of some superkey of the relation is also a superkey of the relation. For our example, {author, title, year, author_birth} must be a superkey because it is a superset of a known superkey.

A key of a relation is a superkey of the relation from which we cannot subtract any attributes and get a superkey. For the library relation, we assert that {author, title} is a superkey of the relation; furthermore, both author and title are needed. That is, neither {author} nor {title} is a superkey of library. Therefore, {author, title} is a key of library; the set {author, title, year} is a superkey but not a key because we can remove year and still have a superkey 3.

Identifying the keys of a relation is a key step in analyzing whether or not a relation is already normalized with respect to 2NF or higher.

## 3.3.4. Functional dependencies¶

Now we turn to the topic of functional dependencies, which are closely related to superkeys.

A functional dependency (FD) is a statement about two sets of attributes of a relation. Consider two sets of attributes, which we will label X and Y. We say that X functionally determines Y, or Y is functionally dependent on X, if, whenever two tuples in the relation agree on the values in X, they must also agree on the values in Y. The notation for this is:

$X \rightarrow Y$

As with keys, FDs are constraints that we impose on the data. Another way of thinking about a functional dependency is, if you had a relation such that the relation contains only the attributes that are in X or Y, then X would be a superkey for that relation. That is, X uniquely determines everything in the union of X and Y. (We can now provide another defintiion of superkey as a subset of attributes of a relation that functionally determines the set of all attributes of the relation.)

Another way of thinking about FDs is, if X functionally determines Y, then if we know the values in X, we know or can determine the values in Y, because Y just contains single-valued facts about X. In our library relation, the set {author, title} functionally determines the set {year}, because if we know the author and title of the book, then we should be able to find out what the publication year is; and whatever sources we consult to find the year should all give us the same answer. The dependency is “functional” in this sense; there exists some function between the domain of (author, title) pairs and the domain of publication years that yields the correct answer for every valid input. The function in this case is simply a mapping between domains, not something we can analytically derive.

Here are some more FDs for the library relation:

$\begin{split}\begin{eqnarray*} \text{\{author, title\}} & \rightarrow & \text{\{genre\}} \\ \text{\{author\}} & \rightarrow & \text{\{author_birth, author_death\}} \\ \text{\{genre\}} & \rightarrow & \text{\{section\}} \\ \text{\{author, title\}} & \rightarrow & \text{\{title, year\}} \\ \text{\{title, genre\}} & \rightarrow & \text{\{title\}} \\ \end{eqnarray*}\end{split}$

The first FD tells us that each book is categorized into exactly one genre in our database. The second tells us that an author’s dates of birth and death should be the same every time the author appears in the database. The third tells us that the location in the library in which a book is shelved depends on the genre of the book. The last two FDs are different from the previous ones; in these, there is an overlap between the set on the left-hand side and the set on the right-hand side. We will give special names to these in a moment. For now, the fourth FD tells us that, if we know the author and title of a book, then we know the title and the publication year. The final FD simply tells us that any two tuples having the same title and genre, have the same title!

### 3.3.4.1. Types of functional dependency¶

FDs are categorized into three types: trivial, non-trivial, and completely non-trivial.

A trivial FD is one in which the right-hand side of the FD is a subset of the left-hand side. The last FD in our example above is a trivial FD. A trivial FD conveys no useful information - it tells us “we know what we know” - but they still have some use to us in our normalization procedures. Every trivial FD we can write down for a relation is true, as long as the left-hand side of the FD is a subset of the attributes of the relation.

A non-trivial FD is one in which some part of the right-hand side of the FD is not in the left-hand side. The intersection of the left-hand side and the right-hand side is not empty, but the right-hand side is not a subset of the left-hand side. The fourth FD above is a non-trival FD. These FDs convey some new information. Identifying non-trivial FDs in our relations is a crucial step in normalization.

As you might guess by now, a completely non-trivial FD is one for which there is no overlap between the left-hand side and the right-hand side - the intersection of the two sets is the empty set. The first three FDs above are completely non-trivial.

### 3.3.4.2. Inference rules¶

Many FDs can be inferred or derived from other FDs. We are particularly interested in non-trivial FDs which have a maximal set on the right-hand side, that is, a set which cannot be added to without making the FD false. There is a straightforward algorithm to infer such FDs from a set of FDs, which we discuss in the next section. We need the five inference rules below for the algorithm. The first three inference rules are known as Armstrong’s axioms, and can be used to prove the remaining rules.

We present these without proof, but the intuition behind these should be clear. Let X, Y, and Z be subsets of the attributes of the same relation. Let the union of Y and Z be denoted YZ. Then we have:

Reflexive rule

If Y is a subset of X, then

$X \rightarrow Y$

This is simply a statement that all trivial FDs are true.

Augmentation rule

If

$X \rightarrow Y$

then

$XZ \rightarrow YZ$

also holds.

This rule says we can add the same attributes to both the left-hand and right-hand sides of an FD. Trivially, if we add Z to what we know (left-hand side), then we should be able to determine Z in addition to what we could determine previously (right-hand side).

In our library example, we are given

$\text{\{author\}} \rightarrow \text{\{author_birth, author_death\}}$

therefore, it is also true that

$\text{\{author, genre\}} \rightarrow \text{\{author_birth, author_death, genre\}}$

A special case of this is that we can add the left-hand side to both sides; this leaves the left-hand side unchanged, since the union of any set with itself is just the set:

$X \rightarrow Y$

implies

$X \rightarrow XY$
Transitive rule

If we have both of

$\begin{split}X \rightarrow Y \\ Y \rightarrow Z\end{split}$

then

$X \rightarrow Z$

also holds. That is, if knowing X tells us Y, and from Y we can know Z, then knowing X also tells us Z.

In our library relation we have

$\begin{split}\text{\{author, title\}} \rightarrow \text{\{genre\}} \text{\{genre\}} \rightarrow \text{\{section\}} \\\end{split}$

thus

$\text{\{author, title\}} \rightarrow \text{\{section\}}$
Splitting rule (or decomposition, or projective, rule)

If

$X \rightarrow YZ$

holds, then so do

$\begin{split}X \rightarrow Y \\ X \rightarrow Z\end{split}$

Plainly stated, if knowing the values for X tells us the values for Y and Z, then knowing the values for X tells us the values for Y, and likewise for Z. In our library example, we have

$\text{\{author\}} \rightarrow \text{\{author_birth, author_death\}}$

therefore, it is also true that

$\begin{split}\text{\{author\}} \rightarrow \text{\{author_birth\}} \\ \text{\{author\}} \rightarrow \text{\{author_death\}}\end{split}$

Note that we can “split” the right-hand side only. For example, given $$\text{\{author, title\}} \rightarrow \text{\{year\}}$$, it is not true that $$\text{\{author\}} \rightarrow \text{\{year\}}$$.

Combining rule (or union, or additive, rule)

This is the splitting rule in reverse. If we have both of

$\begin{split}X \rightarrow Y \\ X \rightarrow Z\end{split}$

then

$X \rightarrow YZ$

also holds. In our library example, we have

$\begin{split}\text{\{author, title\}} \rightarrow \text{\{year\}} \\ \text{\{author, title\}} \rightarrow \text{\{genre\}}\end{split}$

thus

$\text{\{author, title\}} \rightarrow \text{\{year, genre\}}$

While any FDs that can be inferred from a given collection of FDs on a relation can be inferred using the above rules, there is unfortunately no way of deciding that some collection of FDs is, in fact, complete - that is, that the collection of FDs lets us infer every possible true FD on the relation. FDs come from the minds of the database designer and others involved in analysis and design, a process which requires some “trial and error”, i.e., iterative improvement.

### 3.3.4.3. Closure¶

As mentioned, we are going to be particularly interested in non-trivial FDs which have a maximal set on the right-hand side. The closure of a subset X of relation R given some collection of FDs is the union of all sets {a} such that a is an attribute of R and we can infer $$X \rightarrow {a}$$. Informally, the closure of X is the set of attributes which are functionally determined by X. The closure of X is denoted X+.

We are interested in closure for a couple of reasons. First, note from this definition that the closure of a superkey of a relation is the set of all attributes of the relation. We can use this fact to test whether or not some set of attributes is a superkey; further, we could in theory find all superkeys of a relation by examining the closure of every subset of attributes (in practice this can become too much work fairly quickly as the number of attributes increases). Second, closure will be useful in the decomposition step of our normalization algorithms.

The closure of a set of attributes can be determined using the following algorithm.

Closure algorithm

Given a collection F of FDs and a set of attributes X:

1. Let C = X. Trivially, $$X \rightarrow C$$.

2. While there exists some functional dependency $$Y \rightarrow Z$$ in F such that Y is a subset of C and Z contains some attributes not in C, add the attributes in Z to C to create C'. Then,

$\begin{split}\begin{eqnarray*} & & C \rightarrow Y ~~\text{(reflexive rule)} \\ & & C \rightarrow Z ~~\text{(transitive rule)} \\ & & X \rightarrow Z ~~\text{(transitive rule)} \\ & & X \rightarrow C' ~~\text{(combining rule)} \\ \end{eqnarray*}\end{split}$

Let C = C'.

3. When no more FDs meet the criteria above, C = X+.

We previously asserted that the set {author, title} is a superkey for our example library relation, so the closure {author, title}+ should be the set of all attributes of library. We now show that this follows from our inference rules, and from the FDs given previously:

$\begin{split}\begin{eqnarray*} \text{\{author, title\}} & \rightarrow & \text{\{year\}} \\ \text{\{author, title\}} & \rightarrow & \text{\{genre\}} \\ \text{\{author\}} & \rightarrow & \text{\{author_birth, author_death\}} \\ \text{\{genre\}} & \rightarrow & \text{\{section\}} \\ \text{\{author, title\}} & \rightarrow & \text{\{title, year\}} \\ \text{\{title, genre\}} & \rightarrow & \text{\{title\}} \\ \end{eqnarray*}\end{split}$
1. Let C = {author, title}.

2. We have $$\text{\{author, title\}} \rightarrow \text{\{year\}}$$, and {author, title} is a subset of C, so add year to C: C = {author, title, year}.

3. Similarly, $$\text{\{author, title\}} \rightarrow \text{\{genre\}}$$, so let C = {author, title, year, genre}.

4. We have $$\text{\{author\}} \rightarrow \text{\{author_birth, author_death\}}$$, and {author} is a subset of C. Let C = {author, title, year, genre, author_birth, author_death}.

5. We have $$\text{\{genre\}} \rightarrow \text{\{section\}}$$, and {genre} is a subset if C. Let C = {author, title, year, genre, author_birth, author_death, section}.

6. The algorithm completes at this point because the right-hand sides of all of the unused FDs are already subsets of C; and in any case, C already has all attributes of library.

Thus, {author, title}+ = {author, title, year, genre, author_birth, author_death, section}.

## 3.3.5. Second, third, and Boyce-Codd normal forms¶

We are now ready to discuss the normal forms up to Boyce-Codd normal form (BCNF). In this section we will provide definitions of the normal forms, with examples.

### 3.3.5.1. Second normal form¶

A relation is in second normal form (2NF) if it is in 1NF and there are no non-key attributes which are functionally dependent on a proper subset of the key. A non-key attribute is an attribute which is not part of any key.

From this definition, we can see that library is not in 2NF. The key of library is {author, title}. However, we have the FD

$\text{\{author\}} \rightarrow \text{\{author_birth, author_death\}}$

in which the left-hand side only contains author. We say that the above FD violates second normal form.

Note that any relations (in 1NF) for which the key has a single attribute is automatically in 2NF.

### 3.3.5.2. Third normal form¶

A relation is in third normal form (3NF) if it is in 2NF and there are no non-key attributes which are functionally dependent on other non-key attributes.

Considering the library relation again, the dependency

$\text{\{genre\}} \rightarrow \text{\{section\}}$

violates 3NF because neither genre nor section are part of any key.

### 3.3.5.3. Boyce-Codd normal form¶

Boyce-Codd 4 normal form is a slightly stronger version of third normal form; any relation in BCNF is also in 3NF. However, most relations in 3NF are also in BCNF. BCNF has a simple and general definition which encompasses the definitions of 2NF and 3NF:

Definition of BCNF

A relation is in BCNF if it is in 1NF and if, for every non-trivial functional dependency of the form $$X \rightarrow Y$$ on the relation, X is a superkey of the relation.

It may not be obvious from this definition that relations in BCNF are also in 2NF and 3NF. We will demonstrate that this is true for 2NF; a similar argument holds for 3NF. Recall that 2NF requires we have no non-key attributes functionally dependent on a proper subset of the key. By the definition of key, a proper subset of the key cannot be a key or superkey; therefore, an FD forbidden by 2NF must have a left-hand side that is not a superkey. On the other hand, non-key attributes cannot be part of the key at all. The right-hand side of an FD forbidden by 2NF can have no intersection with the left-hand side, so the FD is completely non-trivial. Thus any FDs that would violate 2NF also meet the criteria for violating BCNF.

The difference between 3NF and BCNF is simply that 3NF permits FDs for which the right-hand side is a subset of a key. This situation is fairly uncommon, which is why most relations in 3NF are also in BCNF. We will explore this difference further in a later section.

## 3.3.6. Decomposition¶

We say that a database is normalized with respect to some normal form if all relations in the database are in the normal form. To normalize a database, we must decompose relations which have some violating FD. Decomposition of a relation involves creating two new relations, each of which has a subset of the attributes of the original relation. The original relation can then be discarded.

In this section we discuss the BCNF decomposition algorithm and provide an example walkthrough of normalization. We close the section by exploring why some problematic relations may be better left in 3NF.

### 3.3.6.1. Decomposition algorithm¶

There is a simple approach to decomposition that both eliminates a violation of a normal form, and that allows for exact recovery of the original relation in all cases. The algorithm below is expressed in terms of BCNF, but works equally well for 2NF and 3NF:

Decomposition algorithm

Given some relation R, and a functional dependency $$X \rightarrow Y$$ on R that violates BCNF:

1. (Optional, but strongly recommended) Add to Y any attributes that are functionally determined by X and that are not already in Y; i.e., let Y = X+. (It is easy to show that $$X \rightarrow X^{+}$$ violates BCNF given the original violation, so we are merely substituting one violating FD for another.)

2. Let Z be the set of attributes of R that are not in X or Y. (This set must be non-empty because, by definition, X is not a superkey.)

3. Create relations R1 and R2 such that R1 has the attributes in the union of X and Y, and R2 has the attributes in the union of X and Z. In relational algebra terms, we use projection to create the new relations:

$\begin{split}R1 = \pi_{XY}(R) \\ R2 = \pi_{XZ}(R)\end{split}$
4. Discard R.

### 3.3.6.2. Worked example¶

We now apply this algorithm to a database initially composed of just the library relation. To start, we previously noted that the FD

$\text{\{author\}} \rightarrow \text{\{author_birth, author_death\}}$

violates 2NF and thus BCNF. To apply the decomposition algorithm to this violation:

1. Let Y be the closure of {author}, which is {author, author_birth, author_death}.

2. Let Z then be {title, year, genre, section}.

3. The union of X and Y is just Y because we did the optional closure in step 1. The union of X and Z is {author, title, year, genre, section}. Projecting on to these attribute sets yields the following relations, which we rename to authors and library2:

authors

author

author_birth

author_death

Ralph Ellison

1914-03-01

1994-04-16

Jhumpa Lahiri

1967-07-11

J.R.R. Tolkien

1892-01-03

1973-09-02

Isabel Allende

1942-08-02

Ursula K. Le Guin

1929-10-21

2018-01-22

library2

author

title

year

genre

section

Ralph Ellison

Invisible Man

1952

fiction

literature

Jhumpa Lahiri

Unaccustomed Earth

2008

fiction

literature

J.R.R. Tolkien

The Hobbit

1937

fantasy

speculative fiction

Isabel Allende

The House of the Spirits

1982

magical realism

literature

J.R.R. Tolkien

The Fellowship of the Ring

1954

fantasy

speculative fiction

Ursula K. Le Guin

The Dispossessed

1974

science fiction

speculative fiction

1. Discard library.

Note that we can recover the original relation by applying a natural join operation to authors and library2.

We must now look at our new relations, and determine if they are now normalized. A first step is determining keys and FDs for the new relations. There is a formal process to compute the superkeys and FDs of the new relation from the FDs on the old relation 5. However, in practice it is usually possible for a database designer to identify the FDs and keys of the new relations given their knowledge of the data, without all of the computations implied above.

For our example, in authors we can quickly determine that the only useful non-trivial FD is

$\text{\{author\}} \rightarrow \text{\{author_birth, author_death\}}$

From this we can also see that the closure of {author} includes all attributes in authors, and thus {author} is a key. There are no violating FDs remaining in this relation, so it is normalized with respect to BCNF.

Now consider the relation library2. Note that the FD above does not apply, because author_birth and author_death are not attributes in library2. From our knowledge of the FDs in the library relation, we can determine that these FDs hold in library2:

$\begin{split}\begin{eqnarray*} \text{\{author, title\}} & \rightarrow & \text{\{year, genre, section\}} \\ \text{\{genre\}} & \rightarrow & \text{\{section\}} \\ \end{eqnarray*}\end{split}$

and that the key is {author, title}.

The second FD above violates BCNF (and 3NF). Decomposing on this FD, we have X = {genre}, Y = {section}, and Z = {title, author, year, genre}. Decomposition results in the following relations, which we rename to books and genres:

books

author

title

year

genre

Ralph Ellison

Invisible Man

1952

fiction

Jhumpa Lahiri

Unaccustomed Earth

2008

fiction

J.R.R. Tolkien

The Hobbit

1937

fantasy

Isabel Allende

The House of the Spirits

1982

magical realism

J.R.R. Tolkien

The Fellowship of the Ring

1954

fantasy

Ursula K. Le Guin

The Dispossessed

1974

science fiction

genres

genre

section

fiction

literature

fantasy

speculative fiction

magical realism

literature

science fiction

speculative fiction

We discard library2, leaving us with just three relations: authors, books, and genres. All three relations are now in BCNF, so no further normalization (with respect to BCNF or lower) is possible. We can recover the library2 relation by a natural join of books and genres; or we can recover the original library relation by a natural join of all three relations.

Note that the normalized database has a clear separation of concerns in the different relations; one relation is just about authors, another about books, and a third with specialized information about the layout of a library. Redundancy has been reduced, and modification anomalies are much less likely.

### 3.3.6.3. Decomposition properties¶

There are two desirable properties for a normalization decomposition, which we discuss in this section.

#### 3.3.6.3.1. Exact recovery¶

This first property we have mentioned, which is that the original relation must be recoverable by joining the decomposition products. This means that the joined relation must have all of the tuples of the original, and no extra tuples. This property is non-negotiable; a join of the relations must give true answers. In fact, the BCNF decomposition algorithm as presented fulfills this condition; an arbitrary decomposition would not necessarily do so.

We omit a full proof of the correctness of the decomposition algorithm. An intuitive understanding begins with a consideration of the meaning of functional dependency. The existence of some functional dependency $$X \rightarrow Y$$ tells us that the Y attributes must remain in lockstep with the X attributes. Any distinct value of X can be associated with exactly one setting of Y values; so X uniquely identifies Y. Therefore, if we have a relation that lets us look up the values for Y for each distinct value of X, we can use just the X attributes in the original relation as representative of both X and Y. The decomposition algorithm creates exactly this situation; projection onto the attributes involved in the functional dependency creates the “lookup” relation (authors in our first decomposition example); the X attributes (author) remain as a foreign key and the Y attributes (author_birth, author_death) can be removed. A join of the relations on the shared foreign key restores the Y values to the correct tuples.

#### 3.3.6.3.2. Dependency preservation¶

A second desirable property for a decomposition is not always met with BCNF decomposition. This second property requires that all constraints implied by the original functional dependencies are preserved in the database after decomposition. It turns out that we can guarantee this property by normalizing to 3NF, but not BCNF. This is best illustrated with an example.

Consider the relation below, regarding the Hugo and Nebula awards for literary and other works in the science fiction genre. These two awards are given each year in multiple categories, such as “Best Novel”, “Best Short Story” and so forth. Typically only one work in a given format in a given year wins a given award (we will assume that rule is always enforced for example purposes). Therefore, if we are given the award, year, and format, we can unambiguously determine the award winning work. The relation below gives some representative data:

scifi_awards

award

year

format

author

title

Hugo

1975

novel

Ursula K. Le Guin

The Dispossessed

Hugo

1975

short story

Larry Niven

The Hole Man

Hugo

1974

novel

Arthur C. Clarke

Rendezvous With Rama

Nebula

1975

novel

Joe Haldeman

The Forever War

Nebula

1974

novel

Ursula K. Le Guin

The Dispossessed

There are two important functional dependencies. The first, reflecting the rule that only one work in each format can win a particular award in a given year, is

$\text{\{award, year, format\}} \rightarrow \text{\{author, title\}}$

The first constraint does not violate 3NF or BCNF, because the left-hand side is a key for the relation.

The second FD acknowledges that each work is in a particular format; a work may be a novel or a short story, but not both:

$\text{\{author, title\}} \rightarrow \text{\{format\}}$

This relation falls into the narrow category of relations that are in 3NF but not in BCNF. As in this example, this occurs when the relation contains sets of attributes A, B, and C, with $$AB \rightarrow C$$ and $$C \rightarrow B$$. The second FD violates BCNF, because {author, title} is not a key for this relation (as demonstrated in the example data above). However, the FD does not violate 3NF, because the right-hand side ({format}) is part of a key for the relation.

If we decompose as usual on the BCNF violation, the immediate decomposition products must join together to return the original relation, which has correct data, so that is not a problem. However, after decomposition, we have relations with attributes {author, title, format} and {award, year, author, title}. The first FD above, which enforced the constraint of an award going to only one work in each format each year, no longer applies to either relation. The new relations cannot prevent us storing data such as the following:

scifi_awards_1

author

title

format

Ursula K. Le Guin

The Dispossessed

novel

Roger Zelazny

Doorways in the Sand

novel

scifi_awards_2

award

year

author

title

Hugo

1975

Ursula K. Le Guin

The Dispossessed

Hugo

1975

Roger Zelazny

Doorways in the Sand

Since the Hugo award is given to multiple works in a given year (just for different categories of work), the data in the second relation could be valid - but only if the two works listed happen to be in different categories. However, as the first relation shows, they are in the same category (the second relation, as it happens, contains false data). Only if we join these two relations can we see that we have violated our constraint.

In this particular case, it would be preferable to leave the original relation in 3NF and preserve the constraint with a primary key composed of {award, year, format}. The redundancy involved is small, given that works can appear at most twice in the relation (since we only have the two awards). If you encounter such a situation, however, you must determine the best way forward for your particular case. If you leave the relation in 3NF, then you must manage the modification anomalies implied implied by the BCNF violation (in the application software, or some other mechanism). If you move the relation to BCNF, then you must enforce the lost constraint in some other fashion.

## 3.3.7. Multivalued dependencies and fourth normal form¶

Relations that violate BCNF frequently occur in normal data collection activities. For example, a web server keeping activity logs might record user information along with information about the pages the user visits on the website. Redundancy is apparent in the user information appearing identically in multiple log entries.

In contrast, fourth normal form (4NF) violations are unlikely to occur in data gathering. Instead, 4NF addresses problems that occur when an attempt is made to store data that includes multiple independent one-to-many relationships in a single relation. Redundancy in this setting is more subtle and harder to identify.

For an example, we will consider some of the many awards given for literary merit. Some awards are given to authors (Nobel Prize in Literature, Neustadt International Prize for Literature) without reference to a specific work. Others (Pulitzer Prize, Nebula Award) are given in recognition of specific works. An author can win multiple awards of either type. If we are incautious in our design, we might come up with a relation like the following:

authors_and_awards

author

author_award

book_award

Louise Glück

Nobel Prize

Pulitzer Prize

Louise Glück

Nobel Prize

National Book Award

John Steinbeck

Nobel Prize

Pulitzer Prize

Alice Munro

Nobel Prize

Giller Prize

Alice Munro

International Booker Prize

Giller Prize

Alice Munro

Nobel Prize

National Book Critics Circle Award

Alice Munro

International Booker Prize

National Book Critics Circle Award

This is just an illustration; we would probably want to include other attributes to our relation such as the year each award was won, or the book for which a book award was won, but these extra attributes distract from the central concern we are trying to address.

At a casual glance it appears that there are many redundancies in this relation. For example, we have two tuples showing that Louise Glück won a Nobel Prize, and the same for Alice Munro. We show Alice Munro winning the Giller Prize in two different tuples 6. For this relation, however, there are no non-trivial functional dependencies whatsoever. The only key for the relation is the set {author, author_award, book_award}, so each tuple is unique. Therefore the relation is in BCNF.

The pattern here is indicative of something called a multivalued dependency (MVD). The formal definition of an MVD is rather opaque, and we will not state it here. Informally, we have subsets of attributes A, B, and C, such that, for a given A, every distinct value of B must be paired with every distinct value of C associated with the value of A. When this is true we state that A multidetermines B, and write

$A \twoheadrightarrow B$

The situation is also symmetric; when A multidetermines B it also multidetermines C. Thus we may write

$A \twoheadrightarrow B|C$

In our example, considering Alice Munro and her Nobel Prize, what book awards did she win? The answer must include both the Giller Prize and the National Book Critics Circle Award. The same answer applies when we consider her International Booker Prize. We might instead consider Alice Munro and her Giller prize and ask what author awards she won; this time the answer would include her Nobel Prize and her International Booker Prize. Thus, for this relation the MVD

$\text{\{author\}} \twoheadrightarrow \text{\author_award\}} | \text{\{book_award\}}$

holds.

The definition of fourth normal form looks much like the definition of BCNF, substitution MVD for FD:

Definition of 4NF

A relation is in 4NF if, for every non-trivial multivalued dependency of the form $$X \twoheadrightarrow Y$$ on the relation, X is a superkey of the relation.

Clearly in our example relation, the set {author} is not a superkey, so the relation is not in 4NF. The solution to a 4NF violation happens to be identical to the solution for a BCNF violation. Given an MVD $$X \twoheadrightarrow Y$$ that violates 4NF, we decompose into two relations, one with the attributes in XY, and the other with the attributes in XZ, where Z is everything not in X or Y (Z is also multidetermined by X as discussed above). The decomposition eliminates the pairing of independent concepts. For our example, the decomposition yields:

author_awards

author

author_award

Louise Glück

Nobel Prize

John Steinbeck

Nobel Prize

Alice Munro

Nobel Prize

Alice Munro

International Booker Prize

author_book_awards

author

book_award

Louise Glück

Pulitzer Prize

Louise Glück

National Book Award

John Steinbeck

Pulitzer Prize

Alice Munro

Giller Prize

Alice Munro

National Book Critics Circle Award

The formal definition of MVD is sufficiently general that every FD qualifies as an MVD. Therefore, a relation in 4NF is also in BCNF.

## 3.3.8. Trade-offs¶

As we have seen, the process of normalization leads to increased numbers of (generally smaller) relations. Despite this proliferation of relations, normalization actually simplifies application software due to eliminating modification anomalies and related issues. Smaller relations may also provide modest space savings, and performing queries on the relations in isolation will be faster. However, when a query requires data collected into many different relations, performance can suffer. Particularly when large volumes of data are involved, join operations become expensive for relational database systems.

As a result, there are occasions when it is desirable to create a de-normalized database, in which data is held in one or more large relations representing the result of joining together numerous relations. Such a decision should not be made lightly and without consideration for the impact of modification anomalies. One popular approach creates not one, but two databases containing the same data. In this approach, one database is fully normalized and is used to process data updates. The other, de-normalized database is used solely for read-only queries, and may be updated (or re-created) only periodically (perhaps daily or hourly). Users of the de-normalized database receive slightly out-of-date answers, but faster.

## 3.3.9. Normalization in database design¶

Databases can be created using a number of approaches. The approach taken depends greatly on the circumstances which have led to the need for a database.

In some cases, data have been previously collected and stored in some fashion, but not organized into something we would consider a database. Many scientific, industrial, and business processes produce large amounts of data in the form of sensor readings, application logs, reports, and form responses. This data may exist in electronic form or on paper. There may be little structure to the data; it may exist in a flat form in which there is only one type of record which stores every piece of information relevant to some event. Creating a database to more efficiently work with such data may be best accomplished using a top-down approach, in which relations are systematically decomposed. Data modeling (Part 2) may be used as part of this process, to document, communicate, and reason about the evolving database.

In contrast, when creating a new software application, a bottom-up approach may be preferred. The application developers and other interested parties work to identify the data attributes that need to be collected and stored. Multiple relations emerge naturally, corresponding to different parts of the application. Data modeling should almost always occur early in this process.

Data modeling is very effective at producing relations that accurately represent independent concepts and the relationships between them. However, some relations may still require normalization. Normalization provides a different perspective on database design. As with data modeling, our understanding of the real world and our data informs our choices. However, while data modeling focuses on mapping concepts in the real world to relations, normalization works to produce a database structure that is more resistant to data errors. Data modeling ensures our database accurately captures the data we need, while normalization ensures our database can be used effectively. The two activities are thus complementary. Whether or not normalization is applied formally, an understanding of normalization and its trade-offs is important for any database designer.

Notes

1

We may need to use NULLs when information is truly unknown or absent; for example, we would set the instructor attribute NULL for classes which have no instructor assigned at the current time. Similarly, we might set the office attribute NULL for new instructors who do not yet have an office. Neither of these cases requires special handling in our software, so we consider these NULLs acceptable. While it is possible to design a database that avoids even these NULLs, it would complicate the database (with more relations) for little gain.

2

It is common practice in some countries where English is the primary language to break a name into first (or given), middle, and last name (or surname). However, this naming scheme is by no means universal, even for English speakers. Unless there is a compelling need to break a name into components for your application, we recommend a single name attribute. For more on this topic, see https://www.w3.org/International/questions/qa-personal-names.

3

We reiterate that a superkey is a constraint we impose on the data. When designing a database, we of course hope to create a structure that accommodates true facts from the world, but a) we sometimes fail due to incomplete information about the world, and b) we sometimes compromise on a simpler design that accommodates most facts from the world. For our simple_books relation, we are unaware of any books by the same author with the same title in the same year, so we are comfortable asserting that {author, title, year} is a valid superkey (but we could be wrong). On the other hand, this design intentionally fails to capture any number of the complexities of books in the real world. For one example, authors occasionally re-publish a book with small changes, under the same title, years after the original publication. Is this the same “book” (in which case year really stands for “year of first publication”), or a different book (in which case {author, title} is not a superkey)? For another example, we are completely ignoring the fact that some books have multiple authors, and some have no known authors. Databases about books can be very complex!

4

Named after Raymond F. Boyce and Edgar F. Codd, who published a paper in 1974 defining this normal form. However, a 1971 paper by Ian Heath gave a prior description.

5

Given R and R1 and a collection of FDs on R1, for every subset X of the attributes of R1, compute the closure, X+ in R. For every attribute a of R1 that is in the closure of X, by the splitting rule, $$X \rightarrow \{a\}$$ is an FD for R1. If X+ contains every attribute of R1, then X is a superkey of R1.

6

As it happens, Alice Munro won two Giller Prizes, in different years; if we included an attribute for year, we would have to double the number of entries for Alice Munro!

You have attempted of activities on this page