Database normalization, sometimes referred to as canonical synthesis, is a technique for designing relational database tables to minimize duplication of information and, in so doing, to safeguard the database against certain types of logical or structural problems, namely data anomalies. For example, when multiple instances of a given piece of information occur in a table, the possibility exists that these instances will not be kept consistent when the data within the table is updated, leading to a loss of data integrity. A table that is sufficiently normalized is less vulnerable to problems of this kind, because its structure reflects the basic assumptions for when multiple instances of the same information should be represented by a single instance only. A relational database is a database that conforms to the relational model, and refers to a databases data and schema (the databases structure of how that data is arranged). ... In relational databases, SQL databases, and flat file databases, a table is a set of data elements (values) that is organized using a model of horizontal rows and vertical columns. ... In computer science and telecommunications, the term data integrity has the following meanings: The condition in which data is identically maintained during any operation, such as transfer, storage, and retrieval. ...

Higher degrees of normalization typically involve more tables and create the need for a larger number of joins, which can reduce performance. Accordingly, more highly normalized tables are typically used in database applications involving many isolated transactions (e.g. an Automated teller machine), while less normalized tables tend to be used in database applications that do not need to map complex relationships between data entities and data attributes (e.g. a reporting application, or a full-text search application). A JOIN clause in SQL combines records from two tables in a relational database and results in a new (temporary) table, also called a joined table. Structured Query Language (SQL:2003) specifies two types of joins: inner and outer. ... Computer Performance is characterised by the amount of useful work accomplished by a computer system compared to the time and resources used. ... A database transaction is a unit of interaction with a database management system or similar system that is treated in a coherent and reliable way independent of other transactions. ... Cash machine redirects here. ...

Database theory describes a table's degree of normalization in terms of normal forms of successively higher degrees of strictness. A table in third normal form (3NF), for example, is consequently in second normal form (2NF) as well; but the reverse is not always the case. Database normalization, sometimes referred to as canonical synthesis, is a technique for designing relational database tables to minimize duplication of information and, in so doing, to safeguard the database against certain types of logical or structural problems, namely data anomalies. ...

Although the normal forms are often defined informally in terms of the characteristics of tables, rigorous definitions of the normal forms are concerned with the characteristics of mathematical constructs known as relations. Whenever information is represented relationally, it is meaningful to consider the extent to which the representation is normalized. In mathematics, the concept of a relation is a generalization of 2-place relations, such as the relation of equality, denoted by the sign = in a statement like 5 + 7 = 12, or the relation of order, denoted by the sign < in a statement like 5 < 12. Relations that involve two...

Problems addressed by normalization

An update anomaly. Employee 519 is shown as having different addresses on different records.

An insertion anomaly. Until the new faculty member is assigned to teach at least one course, his details cannot be recorded.

A deletion anomaly. All information about Dr. Giddens is lost when he temporarily ceases to be assigned to any courses.

A table that is not sufficiently normalized can suffer from logical inconsistencies of various types, and from anomalies involving data operations. In such a table: In computing, CRUD is an acronym for Create, Read, Update, and Delete. ...

• The same information can be expressed on multiple records; therefore updates to the table may result in logical inconsistencies. For example, each record in an "Employees' Skills" table might contain an Employee ID, Employee Address, and Skill; thus a change of address for a particular employee will potentially need to be applied to multiple records (one for each of his skills). If the update is not carried through successfully—if, that is, the employee's address is updated on some records but not others—then the table is left in an inconsistent state. Specifically, the table provides conflicting answers to the question of what this particular employee's address is. This phenomenon is known as an update anomaly.
• There are circumstances in which certain facts cannot be recorded at all. For example, each record in a "Faculty and Their Courses" table might contain a Faculty ID, Faculty Name, Faculty Hire Date, and Course Code—thus we can record the details of any faculty member who teaches at least one course, but we cannot record the details of a newly-hired faculty member who has not yet been assigned to teach any courses. This phenomenon (fact/ event) is known as an insertion anomaly.
• There are circumstances in which the deletion of data representing certain facts necessitates the deletion of data representing completely different facts. The "Faculty and Their Courses" table described in the previous example suffers from this type of anomaly, for if a faculty member temporarily ceases to be assigned to any courses, we must delete the last of the records on which that faculty member appears. This phenomenon is known as a deletion anomaly.

Ideally, a relational database table should be designed in such a way as to exclude the possibility of update, insertion, and deletion anomalies. The normal forms of relational database theory provide guidelines for deciding whether a particular design will be vulnerable to such anomalies. It is possible to correct an unnormalized design so as to make it adhere to the demands of the normal forms: this is called normalization. Removal of redundancies of the tables will lead to several tables, with referential integrity restrictions between them. An example of a database that has not enforced referential integrity. ...

Normalization typically involves decomposing an unnormalized table into two or more tables that, were they to be combined (joined), would convey exactly the same information as the original table.

Background to normalization: definitions

• Functional dependency: Attribute B has a functional dependency on attribute A i.e. A → B if, for each value of attribute A, there is exactly one value of attribute B. In our example, Employee Address has a functional dependency on Employee ID, because a particular Employee ID value corresponds to one and only one Employee Address value. (Note that the reverse need not be true: several employees could live at the same address and therefore one Employee Address value could correspond to more than one Employee ID. Employee ID is therefore not functionally dependent on Employee Address.) An attribute may be functionally dependent either on a single attribute or on a combination of attributes. It is not possible to determine the extent to which a design is normalized without understanding what functional dependencies apply to the attributes within its tables; understanding this, in turn, requires knowledge of the problem domain. For example, an Employer may require certain employees to split their time between two locations, such as New York City and London, and therefore want to allow Employees to have more than one Employee Address. In this case, Employee Address would no longer be functionally dependent on Employee ID.
• Trivial functional dependency: A trivial functional dependency is a functional dependency of an attribute on a superset of itself. {Employee ID, Employee Address} → {Employee Address} is trivial, as is {Employee Address} → {Employee Address}.
• Full functional dependency: An attribute is fully functionally dependent on a set of attributes X if it is a) functionally dependent on X, and b) not functionally dependent on any proper subset of X. {Employee Address} has a functional dependency on {Employee ID, Skill}, but not a full functional dependency, for it is also dependent on {Employee ID}.
• Transitive dependency: A transitive dependency is an indirect functional dependency, one in which X→Z only by virtue of X→Y and Y→Z.
• Multivalued dependency: A multivalued dependency is a constraint according to which the presence of certain rows in a table implies the presence of certain other rows: see the Multivalued Dependency article for a rigorous definition.
• Join dependency: A table T is subject to a join dependency if T can always be recreated by joining multiple tables each having a subset of the attributes of T.
• Superkey: A superkey is an attribute or set of attributes that uniquely identifies rows within a table; in other words, two distinct rows are always guaranteed to have distinct superkeys. {Employee ID, Employee Address, Skill} would be a superkey for the "Employees' Skills" table; {Employee ID, Skill} would also be a superkey.
• Candidate key: A candidate key is a minimal superkey, that is, a superkey for which we can say that no proper subset of it is also a superkey. {Employee Id, Skill} would be a candidate key for the "Employees' Skills" table.
• Non-prime attribute: A non-prime attribute is an attribute that does not occur in any candidate key. Employee Address would be a non-prime attribute in the "Employees' Skills" table.
• Primary key: Most DBMSs require a table to be defined as having a single unique key, rather than a number of possible unique keys. A primary key is a key which the database designer has designated for this purpose.

A functional dependency is a constraint between two sets of attributes in a relation from a database. ... A multivalued dependency is a full constraint between two sets of attributes in a relation. ... A superkey is defined in the relational model as a set of attributes of a relation variable (relvar) for which it holds that in all relations assigned to that variable there are no two distinct tuples (rows) that have the same values for the attributes in this set. ... In the relational model a candidate key of a relation variable (relvar) is a set of attributes of that relvar such that (1) at all times it holds in the relation assigned to that variable that there are no two distinct tuples with the same values for these attributes and... A database management system (DBMS) is computer software designed for the purpose of managing databases. ... In database design, a primary key is a value that can be used to identify a unique row in a table. ...

History

Edgar F. Codd first proposed the process of normalization and what came to be known as the 1st normal form: Edgar Frank Ted Codd (August 23, 1923 – April 18, 2003) was a British computer scientist who made seminal contributions to the theory of relational databases. ...

There is, in fact, a very simple elimination^[1] procedure which we shall call normalization. Through decomposition non-simple domains are replaced by "domains whose elements are atomic (non-decomposable) values."

—Edgar F. Codd, A Relational Model of Data for Large Shared Data Banks^[2]

In his paper, Edgar F. Codd used the term "non-simple" domains to describe a heterogeneous data structure, but later researchers would refer to such a structure as an abstract data type. In his biography Edgar F. Codd also cited that the inspiration for his work was his eager assistant Tom Ward who used to challenge Edgar to rounds of database normalization similar to a chess match between master and apprentice. Tom Ward has been often quoted in industry magazines as stating that he has always enjoyed database normalization even more than sudoku.^{[citation needed]} In computing, an abstract data type (ADT) is a specification of a set of data and the set of operations that can be performed on the data. ...

Normal forms

The normal forms (abbrev. NF) of relational database theory provide criteria for determining a table's degree of vulnerability to logical inconsistencies and anomalies. The higher the normal form applicable to a table, the less vulnerable it is to such inconsistencies and anomalies. Each table has a "highest normal form" (HNF): by definition, a table always meets the requirements of its HNF and of all normal forms lower than its HNF; also by definition, a table fails to meet the requirements of any normal form higher than its HNF.

The normal forms are applicable to individual tables; to say that an entire database is in normal form n is to say that all of its tables are in normal form n.

Newcomers to database design sometimes suppose that normalization proceeds in an iterative fashion, i.e. a 1NF design is first normalized to 2NF, then to 3NF, and so on. This is not an accurate description of how normalization typically works. A sensibly designed table is likely to be in 3NF on the first attempt; furthermore, if it is 3NF, it is overwhelmingly likely to have an HNF of 5NF. Achieving the "higher" normal forms (above 3NF) does not usually require an extra expenditure of effort on the part of the designer, because 3NF tables usually need no modification to meet the requirements of these higher normal forms.

Edgar F. Codd originally defined the first three normal forms (1NF, 2NF, and 3NF). These normal forms have been summarized as requiring that all non-key attributes be dependent on "the key, the whole key and nothing but the key". The fourth and fifth normal forms (4NF and 5NF) deal specifically with the representation of many-to-many and one-to-many relationships among attributes. Sixth normal form (6NF) incorporates considerations relevant to temporal databases. Edgar Frank Ted Codd (August 23, 1923 – April 18, 2003) was a British computer scientist who made seminal contributions to the theory of relational databases. ... A temporal database is a database management system with built-in time aspects, e. ...

First normal form

Main article: First normal form

A table is in first normal form (1NF) if and only if it faithfully represents a relation.^[3] Given that database tables embody a relation-like form, the defining characteristic of one in first normal form is that it does not allow duplicate rows or nulls. Simply put, a table with a unique key (which, by definition, prevents duplicate rows) and without any nullable columns is in 1NF. First normal form (1NF or Minimal Form) is a normal form used in database normalization. ... ↔ ⇔ ≡ logical symbols representing iff. ...

Note that the restriction on nullable columns as a 1NF requirement, as espoused by Chris Date, et. al., is controversial. This particular requirement for 1NF is a direct contradiction to Dr. Codd's vision of the relational database, in which he stated that "null values" must be supported in a fully relational DBMS in order to represent "missing information and inapplicable information in a systematic way, independent of data type."^[4] By redefining 1NF to exclude nullable columns in 1NF, no level of normalization can ever be achieved unless all nullable columns are completely eliminated from the entire database. This is in line with Date's and Darwen's vision of the perfect relational database, but can introduce additional complexities in SQL databases to the point of impracticality.^[5]

One requirement of a relation is that every table contain exactly one value for each attribute. This is sometimes expressed as "no repeating groups"^[6]. While that statement itself is axiomatic, experts disagree about what qualifies as a "repeating group", in particular whether a value may be a relation value; thus the precise definition of 1NF is the subject of some controversy. Notwithstanding, this theoretical uncertainty applies to relations, not tables. Table manifestations are intrinsically free of variable repeating groups because they are structurally constrained to the same number of columns in all rows.

See the first normal form article for a fuller discussion of the nuances of 1NF. First normal form (1NF or Minimal Form) is a normal form used in database normalization. ...

Second normal form

Main article: Second normal form

The criteria for second normal form (2NF) are: Second normal form (2NF) is a normal form used in database normalization. ...

• The table must be in 1NF.
• None of the non-prime attributes of the table are functionally dependent on a part (proper subset) of a candidate key; in other words, all functional dependencies of non-prime attributes on candidate keys are full functional dependencies.^[7] For example, in an "Employees' Skills" table whose attributes are Employee ID, Employee Address, and Skill, the combination of Employee ID and Skill uniquely identifies records within the table. Given that Employee Address depends on only one of those attributes – namely, Employee ID – the table is not in 2NF.
• Note that if none of a 1NF table's candidate keys are composite – i.e. every candidate key consists of just one attribute – then we can say immediately that the table is in 2NF.

Third normal form

Main article: Third normal form

The criteria for third normal form (3NF) are: The third normal form (3NF) is a normal form used in database normalization to check if all the non-key attributes of a relation depend only on the candidate keys of the relation. ...

• The table must be in 2NF.
• Every non-prime attribute of the table must be non-transitively dependent on each candidate key.^[7] A violation of 3NF would mean that at least one non-prime attribute is only indirectly dependent (transitively dependent) on a candidate key. For example, consider a "Departments" table whose attributes are Department ID, Department Name, Manager ID, and Manager Hire Date; and suppose that each manager can manage one or more departments. {Department ID} is a candidate key. Although Manager Hire Date is functionally dependent on the candidate key {Department ID}, this is only because Manager Hire Date depends on Manager ID, which in turn depends on Department ID. This transitive dependency means the table is not in 3NF.

Boyce-Codd normal form

Main article: Boyce-Codd normal form

A table is in Boyce-Codd normal form (BCNF) if and only if, for every one of its non-trivial functional dependencies X → Y, X is a superkey—that is, X is either a candidate key or a superset thereof.^[8] Boyce-Codd normal form (or BCNF) is a normal form used in database normalization. ...

Fourth normal form

Main article: Fourth normal form

A table is in fourth normal form (4NF) if and only if, for every one of its non-trivial multivalued dependencies X →→ Y, X is a superkey—that is, X is either a candidate key or a superset thereof.^[9] Database normalization is a series of steps followed to obtain a database design that allows for consistent storage and efficient access of data in a relational database. ... A multivalued dependency is a full constraint between two sets of attributes in a relation. ...

Fifth normal form

Main article: Fifth normal form

The criteria for fifth normal form (5NF and also PJ/NF) are: This article or section is in need of attention from an expert on the subject. ...

• The table must be in 4NF.
• There must be no non-trivial join dependencies that do not follow from the key constraints. A 4NF table is said to be in the 5NF if and only if every join dependency in it is implied by the candidate keys.

↔ ⇔ ≡ logical symbols representing iff. ...

Domain/key normal form

Main article: Domain/key normal form

Domain/key normal form (or DKNF) requires that a table not be subject to any constraints other than domain constraints and key constraints. Domain/key normal form (or DKNF) a normal form used in database normalization which requires that the database contains no constraints other than domain constraints and key constraints. ...

Sixth normal form

A table is in sixth normal form (6NF) if and only if it satisfies no non-trivial join dependencies at all,^[10] meaning that the fifth normal form is also satisfied. The sixth normal form was only defined when extending the relational model to take into account the temporal dimension. Most SQL technologies, as of 2005, do not take into account this work, and most temporal extensions to SQL are not relational. See work by Date, Darwen and Lorentzos^[11] for a relational temporal extension, Zimyani^[12] for further discussion on Temporal Aggregation in SQL, or TSQL2 for a non-relational approach. This article is about the concept of time. ... 2-dimensional renderings (ie. ... Christopher J. Date is an independent author, lecturer, researcher, and consultant, specializing in relational database technology. ... Hugh Darwen, employee of IBM UK from 1967 to 2004, has been involved in the history of the relational model since the beginning. ... Nikos Lorentzos is a Greek professor of Informatics. ...

Denormalization

Main article: Denormalization

Databases intended for Online Transaction Processing (OLTP) are typically more normalized than databases intended for Online Analytical Processing (OLAP). OLTP Applications are characterized by a high volume of small transactions such as updating a sales record at a super market checkout counter. The expectation is that each transaction will leave the database in a consistent state. By contrast, databases intended for OLAP operations are primarily "read mostly" databases. OLAP applications tend to extract historical data that has accumulated over a long period of time. For such databases, redundant or "denormalized" data may facilitate Business Intelligence applications. Specifically, dimensional tables in a star schema often contain denormalized data. The denormalized or redundant data must be carefully controlled during ETL processing, and users should not be permitted to see the data until it is in a consistent state. The normalized alternative to the star schema is the snowflake schema. It has never been proven that this denormalization itself provides any increase in performance, or if the concurrent removal of data constraints is what increases the performance. The need for denormalization has waned as computers and RDBMS software have become more powerful. Denormalization is the process of attempting to optimize the performance of a database by adding redundant data. ... Online Transaction Processing (or OLTP) is a class of program that facilitates and manages transaction-oriented applications, typically for data entry and retrieval transaction processing. ... Online Analytical Processing, or OLAP (IPA: ), is an approach to quickly provide answers to analytical queries that are multidimensional in nature. ... The term business intelligence (BI) dates to 1958. ... A dimension table is a data warehousing concept. ... The star schema (sometimes referenced as star join schema) is the simplest data warehouse schema, consisting of a single fact table with a compound primary key, with one segment for each dimension and with additional columns of additive, numeric facts. ... ETL also means Express Toll Lanes, see Express Toll Lanes. ... The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ...

Denormalization is also used to improve performance on smaller computers as in computerized cash-registers and mobile devices, since these may use the data for look-up only (e.g. price lookups). Denormalization may also be used when no RDBMS exists for a platform (such as Palm), or no changes are to be made to the data and a swift response is crucial.

Non-first normal form (NF²)

In recognition that denormalization can be deliberate and useful, the non-first normal form is a definition of database designs which do not conform to the first normal form, by allowing "sets and sets of sets to be attribute domains" (Schek 1982). This extension is a (non-optimal) way of implementing hierarchies in relations. Some theoreticians have dubbed this practitioner developed method, "First Ab-normal Form", Codd defined a relational database as using relations, so any table not in 1NF could not be considered to be relational.

Consider the following table:

Assume a person has several favorite colors. Obviously, favorite colors consist of a set of colors modeled by the given table.

To transform this NF² table into a 1NF an "unnest" operator is required which extends the relational algebra of the higher normal forms. The reverse operator is called "nest" which is not always the mathematical inverse of "unnest", although "unnest" is the mathematical inverse to "nest". Another constraint required is for the operators to be bijective, which is covered by the Partitioned Normal Form (PNF). A bijective function. ...

Further reading

• Litt's Tips: Normalization
• Date, C. J. (1999), An Introduction to Database Systems (8th ed.). Addison-Wesley Longman. ISBN 0-321-19784-4.
• Kent, W. (1983) A Simple Guide to Five Normal Forms in Relational Database Theory, Communications of the ACM, vol. 26, pp. 120-125
• Date, C.J., & Darwen, H., & Pascal, F. Database Debunkings
• H.-J. Schek, P. Pistor Data Structures for an Integrated Data Base Management and Information Retrieval System

Notes and References

E.F. Codds work was the base of Christopher Langtons work in the field of artificial life. ... Communications of the ACM (CACM) is the flagship monthly magazine of the Association for Computing Machinery. ... Christopher J. Date is an independent author, lecturer, researcher, and consultant, specializing in relational database technology. ...

See also

• Aspect (computer science)
• Cross-cutting concern
• Refactoring
• Business rules

In computer science, an aspect is a part of a program that cross-cuts its core concerns, therefore violating its separation of concerns. ... In computer science, cross-cutting concerns, or crosscutting concerns, are aspects of a program which affect (crosscut) other concerns. ... Refactoring is the process of rewriting a computer program or other material to improve its structure or readability, while explicitly keeping its meaning or behavior. ... Business rules describe the operations, definitions and constraints that apply to an organization in achieving its goals. ...

External links

• Database Normalization Basics by Mike Chapple (About.com)
• Database Normalization Intro, Part 2
• An Introduction to Database Normalization by Mike Hillyer.
• Normalization by ITS, University of Texas.
• Rules of Data Normalization by Data Model.org
• A tutorial on the first 3 normal forms by Fred Coulson
• Free PDF poster available by Marc Rettig
• Description of the database normalization basics by Microsoft