Less redundancy thanks to database normalization

Normalization is an approach to database design used in relational databases to avoid redundancy.

The relational database model is the most widely used concept in computerized data management. In relational databases, information is stored as records in tables related by keys. A data record consists of several value ranges that are assigned to specific attributes using table columns.

The following table shows the stored invoice data of a fictitious office equipment supplier. John Public has ordered 10 monitors, 12 mouse pads, and 1 office chair for his company. The order from Jane Doe includes 2 laptops and 2 headsets.

A table in a relational database complies with the first normal form (1NF) when it fulfills the following criteria:

• All data is atomic
• All table columns contain identical values

A data set is considered atomic if each item of information is assigned to a separate data field.

In the below table of billing data, all value ranges that are either non-atomic or don’t contain equivalent data have been highlighted in red.

Both dollars and cents are currently listed in the price column. Decide on one format for currency to create similar value ranges.

A table in line with the second normal form must fulfill all the requirements of the first normal form in addition to the following:

• Each non-key attribute must be fully functional, dependent on the primary key

In the introduction, a relational database is defined as a system of individual tables that are related to each other by means of keys.

Keys are used in relational databases to uniquely identify data records (tuples). A key that allows you to uniquely name the individual lines of a database table is called a super key. Such a key can represent the values of a single column or the combined values of several columns.

In the given example, a possible super key results from the invoice number (“Inv. no.”), customer number (“Cust. no.”), and invoice item number (“Inv. item no.”) attributes, as highlighted in the table below.

A key consisting of invoice number, customer number, and invoice item number with the values {124, 12, 1} makes it possible, for example, to clearly designate the data record that represents Jane Doe’s laptop purchase:

However, not all information in the selected super key is required for a unique identification. A combination of invoice number and invoice item number – that is, a subset of the super key – would suffice to identify individual data records. Such keys with a minimum number of attributes are called key candidates or alternate keys.

As a rule, one key candidate per table is selected to represent the table. Sequential numbering is ideal for this. Such a key is called a primary key and specifies the sequence of the data records.

Like any key candidate, the primary key can be a one-part key or – as in the given example – a composite key. The sample table uses a composite primary key that is comprised of the invoice number and invoice item number.

To convert a database table to the second normal form, you not only need to determine the primary key and all non-key attributes, but also their relationship to one another. Follow these steps:

1. Check whether all non-key attributes are entirely functionally dependent on the primary key. Such dependency only exists if all primary key attributes are necessary to uniquely identify the non-key attribute. This also means that tables with one-part primary keys automatically correspond to the second normal form if all prerequisites for the first normal form are fulfilled.
2. Move all non-key attributes that are not entirely functionally dependent on the full primary key to separate tables.

Taking a close look at the example table, note that the prerequisites for the second normal form are not fulfilled because the date column is only dependent on the invoice number (“Inv. no.”), not on the invoice item number (“Inv. item no.”). The same applies to the first name, last name, street address, city, state, and ZIP code.

To convert the data table to the second normal form, all attributes entirely dependent on the invoice number have been moved to a separate table called “Invoice.”

The table with the balance of the data has been named “Invoice item.”

If a table is to be converted to the third normal form, all prerequisites of the first and second normal form must be fulfilled as well as the following:

• No non-key attribute may be transitively dependent on a key candidate

A transitive dependency occurs when a non-key attribute is dependent on another non-key attribute and so indirectly on its key candidate.

The given database template violates the conditions of the third normal form in several places:

In the “Invoice” table, the first and last name, and the street address, city, state, and ZIP code, depend not only on the primary key (the invoice number), but also on the customer number.

In the “Invoice Item” table, the product and price attributes depend not only on the primary key, derived from the invoice number and invoice item number, but also on the product number. This specific condition also violates the third normal form.

To remove all dependencies between non-key attributes, the relevant attributes have been moved to separate tables, linked to each other by foreign keys. This results in the four normalized tables: “Invoice,” “Customer,” “Invoice item” and “Product.”

The primary key of the “Invoice” table is a sequential invoice number. Each invoice number is assigned a date of invoicing and a customer number.

More detailed information on each customer is stored in the “Customer” table. The “Invoice” and “Customer” tables are linked via the customer number. This is used as the primary key in the “Customer” table and as a foreign key in the “Invoice” table.

The “Invoice item” table is a central table in the sample database, containing information about which products should appear on which invoice, as well as how many of the items were ordered. The sequential primary key on the “Invoice item” table is derived from the invoice number and the invoice item number. The respective products are only listed as product numbers that act as foreign keys, and link the “Invoice item” table with the “Products” table.

Finally, the “Products” table contains detailed information on the respective products, such as the product description and price. The primary key is the product serial number.

Boyce Codd normal form is a tightening of the third normal form. For 3NF:

• No non-key attribute may be transitively dependent on a key candidate

In Boyce Codd normal form, however:

• No attribute may be transitively dependent on a key candidate unless it is a trivial dependency

Boyce Codd normal form is only relevant for database tables with several compound key candidates in which the keys overlap, i.e. if one and the same attribute is a subset of two key candidates.

Database tables complying with the third normal form without multiple key candidates automatically then represent Boyce Codd normal form.

The table below shows two key candidates, each composed of two attributes.

• Vendor number and product number
• Vendor and product number

Both keys make it possible to identify each individual data record. The only non-key attribute is the number. Since the number attribute is not transitively dependent on any of the key candidates, the table is 3NF compliant.

On the other hand, it is not compliant with Boyce Codd normal form, because there is a dependency between the vendor number (“V no.”) and vendor (“Vendor”) attributes. The vendor number attribute is transitively dependent on the key candidate that combines the vendor and product number; conversely, the vendor attribute results from the key candidate that combines the vendor number (“V no.”) and product number (“Prod. no.”).

Transitive dependencies can be avoided by dividing the output table into “Number” and “Vendors” tables, which eliminates overlapping key candidates.

Boyce Codd normal form prevents redundancies by identifying key attributes listed multiple times by overlapping key candidates. In the above example, conversion to 3.5NF prevents duplicate values in the vendor column.

A database table complies with the fourth normal form if the requirements of Boyce Codd normal form are fulfilled in addition to the following:

• There are no multivalued dependencies unless they are trivial

A multivalued dependency always exists if two unrelated attributes are dependent on the same attribute, as illustrated in the example below:

The following table shows which products have been ordered per customer and to which ZIP code they must be delivered.

For example, the customer with the customer number 234 ordered articles 1-0023-D and 2-0023-D, which are to be delivered to his address at ZIP code 12345. For customer 567, articles 1-0023-D, 3-0023-D, 4-0023-D, and 5-0023-D will be delivered to the ZIP code 56789.

The data records can only be identified with a super key resulting from all three attributes – customer number, product number, and ZIP code. Since there is no non-key attribute, the database is 3NF compliant. Furthermore, as there are no non-trivial transitive dependencies, it is also 3.5NF compliant. However, there are multivalued dependencies: both the product number attribute and the ZIP code attribute are dependent on the customer number attribute, but are not related to each other.

The disadvantage of such a database design is that every time a new product is added to the customer’s record, the ZIP code must also be added, which results in redundant data.

These redundancies can be eliminated by converting the table to 4NF. To do this, you have to divide the table in such a way that there are no or only trivial multivalued dependencies. This is possible because the product number and ZIP code are in no way related.

A database table is compliant with the fifth normal form if it satisfies the conditions of the fourth normal form in addition to the following:

• The table cannot be split further without losing information

Below is an example demonstrating such a case in which a company operates a TYPO3-based website and a Magento web shop. Three employees are responsible for the software projects: Mary Smith, George Miller, and Joe Davis, each with different qualifications.

The table shows which employee’s qualification applies to which software project’s requirements.

Mary Smith uses her knowledge of PHP and SQL on the Magento project and uses SQL and JavaScript for the TYPO3 website. George Miller also works with PHP for Magento and in JavaScript for TYPO3. Joe Davis is only involved in the TYPO3 project, working as the sole programmer with PHP. The table also shows that Magento requires knowledge of PHP and SQL, while the TYPO3 project requires knowledge of PHP, SQL, and JavaScript.

The table has only one key composed of all three attributes, meaning that it at least complies with 3NF and the Boyce Codd normal forms. Since there are no dependencies between all three attributes, the table also complies with the fourth normal form.

To check whether the table is also 5NF compliant, divide the output table “Employee qualification for project deployment” into the three tables: “Project deployment,” “Employee qualification,” and “Project requirements.”

The “Project deployment” table shows which employee is involved in which software project.

The “Employee qualification” table shows which employee is proficient in which programming or database language.

The “Project requirements” table indicates which programming qualification is required for which project.

At first glance, the database section appears much clearer after being decompartmentalized. But do the tables created during normalization have the same informational content as the initial table?

A joined database query across all three tables holds the answer. The result is surprising.