Normalization

Atomicity

An attribute is atomic, if and only if,

• Either, its major uses within a database and associated applications are such that it need not be divided further
• Or, a type exists for that attribute within the database engine such that component parts of the attribute can be treated as distinct and indivisible attributes.

Examples

The attribute courseID, with values like ECE208, ECE250, ECE356, is not atomic in the context of a university database, since there are other departmental prefixes, such as SE, CS and MATH. However, in the context of a departmental database, where the only departmental prefix is ECE, the attribute courseID is atomic, since the division into course prefixes and course codes does not serve a major purpose given the context of the database.

Additionally, a datetime object in the MySQL database engine can be described as atomic. While it is divisible into second, minute, hour, day, month and year, this object type is defined in the MySQL database and is made up of distinct, indivisible attributes. Hence it can be considered atomic.

Simple Functions

A function is a simple function if and only if it is computable without the use of explicit mapping.

Examples

$f(x)=x^2$$\large f(x) = x^2$ is a simple function.

$f(x)$$\large f(x)$ as defined by the table

is not a simple function.

Non-Redundancy

An attribute is non-redundant if and only if it is neither an input to, nor the result of, a simple function.

In contrast, an attribute is redundant if and only if it is either an input to, or the result of, a simple function.

Examples

Consider a section relation defined with attributes as follows:

xxxxxxxxxx
section(course_id, sec_id, semester, year, building, room_number)

The attribute semester is a term code combined with the last two digits of the year. For eg. W21 represents "winter 2021".

Hence, there exists a simple function that can extract the year out of the semester.

This means neither of the attributes semester or year are non-redundant.

Lossless Decomposition

A decomposition of relation $r$$\large r$ into relations $r_1$$\large r_1$ and $r_2$$\large r_2$ is lossless if and only if

In other words, it is a lossless decomposition if and only if joining relations $r_1$$\large r_1$ and $r_2$$\large r_2$ using all the attributes that are common in both results in the relation $r$$\large r$.

More specifically, if relation $r(R)$$\large r(R)$ is has attributes $A_i$$\large A_i$ for $i=1,2,3,...,10$$\large i = 1, 2, 3, ..., 10$:

then, relations $r_1(R_1)$$\large r_1(R_1)$ and $r_2(R_2)$$\large r_2(R_2)$ derived from the lossless decomposition of relation $r(R)$$\large r(R)$ are defined as:

where some attributes are in both $R_1$$\large R_1$ and $R_2$$\large R_2$ (i.e. $A_i,A_j$$\large A_i, A_j$) and some attributes are in only $R_1$$\large R_1$ (i.e. $A_k,A_l$$\large A_k, A_l$) or in only $R_2$$\large R_2$ (i.e. $A_p,A_q$$\large A_p, A_q$). Note that there are no attributes that are not in either of $R_1$$\large R_1$ and $R_2$$\large R_2$.

Functional Dependencies

Given attributes in a relation, a functional dependency is a function that uniquely maps the values of a set of attributes to the values of another set of attributes. The notation for functional dependencies is as follows:

Formal Definition

Consider a relation schema $R$$\large R$, and $\alpha$$\large \alpha$, $\beta$$\large \beta$ as subsets of attributes of $R$$\large R$:

Then, the functional dependency,

holds if and only if, for any relation $r(R)$$\large r(R)$, whenever any two tuples $t_1$$\large t_1$ and $t_2$$\large t_2$ agree on attributes $\alpha$$\large \alpha$, they also agree on attributes $\beta$$\large \beta$. That is,

Examples

Because everyone in Canada has a Social Insurance Number (SIN), there exists a functional dependency such that SIN $\to$$\large \to$ Name. This is because a person's social insurance number functionally determines their name. In other words, if we know the SIN, we know their name.

Properties

Identity

• $\alpha \to \alpha$$\Large \alpha \to \alpha$

Reflexivity

• $\beta \subseteq \alpha ⟹\alpha \to \beta$$\Large \beta \sube \alpha \implies \alpha \to \beta$

Augmentation

• $\alpha \to \beta ⟹\gamma \alpha \to \beta$$\Large \alpha \to \beta \implies \gamma\alpha \to \beta$

Transitivity

• $\alpha \to \beta ,\beta \to \gamma ⟹\alpha \to \gamma$$\Large \alpha \to \beta, \beta \to \gamma \implies \alpha \to \gamma$

Closures

Given a set of functional dependencies $F$$\large F$, the closure of $F$$\large F$, denoted as $F^{+}$$\large F^+$ is defined as the set of all possible functional dependencies logically implied by $F$$\large F$ using the properties of functional dependencies. This also implies $F\subseteq F^{+}$$\large F \sube F^+$

Attribute-Set Closures

Given a relation $r$$\large r$, a set of functional dependencies $F$$\large F$ and a set of attributes $\alpha$$\large \alpha$, the attribute-set closure ${\alpha }^{+}$$\large \alpha^+$ is defined as the set of all attributes that can be logically determined using the attributes in $\alpha$$\large \alpha$.

Extraneous Attributes

Given a set of functional dependencies $F$$\large F$, functional dependency $(\alpha \to \beta )\in F$$\large (\alpha \to \beta) \in F$, an attribute $A\in \alpha$$\large A \in \alpha$ is extraneous in $\alpha \to \beta$$\large \alpha \to \beta$ if and only if,

In other words, $A$$\large A$ is not a necessary attribute in the functional dependency $\alpha \to \beta$$\large \alpha \to \beta$.

Examples

Consider a set of functional dependencies $F$$\large F$:

Here, $B$$\large B$ is an extraneous attribute in $AB\to C$$\large AB \to C$, since we already know that $A\to C$$\large A \to C$. Hence $B$$\large B$ is not needed in that functional dependency.

Canonical Covers

Given a set of functional dependencies $F$$\large F$, the canonical cover of $F$$\large F$, is a minimal set of functional dependencies $F_c$$\large F_c$ such that

• there exists no functional dependency $f\in F_c$$\large f \in F_c$ such that $f$$\large f$ is implied by the set of functional dependencies $F_c-f$$\large F_c - f$
• there exists functional dependency with extraneous attributes.

Examples

Consider a set of functional dependencies $F$$\large F$:

We know that,

Hence, $A\to C$$\large A \to C$ is a redundant functional dependency, which means $F$$\large F$ is not a canonical cover. However, $F_c$$\large F_c$ defined as,

is a canonical cover.

Keys

Super Keys

Consider the set of all attributes $R$$\large R$ in relation $r$$\large r$, and set of attributes $\alpha \subseteq R$$\large \alpha \sube R$. Then, $\alpha$$\large \alpha$ is a super key of $r$$\large r$ if and only if ${\alpha }^{+}\supseteq R$$\large \alpha^+ \supe R$.

In other words, in order for $\alpha$$\large \alpha$ to be a super key, all the attributes in $r$$\large r$ must be logically determinable by the attributes in $\alpha$$\large \alpha$.

Candidate Keys

If $\alpha$$\large \alpha$ is a super key of $r$$\large r$, and there exists no $\beta \subset \alpha$$\large \beta \sub \alpha$ that is also a super key, then $\alpha$$\large \alpha$ is a candidate key of $r$$\large r$.

In other words, $\alpha$$\large \alpha$ is a candidate key if and only if removing any attribute from $\alpha$$\large \alpha$ will result in it losing its super key status.

Determining Candidate Key Attributes

Consider the set of all attributes $R$$\large R$ in relation $r$$\large r$ and a canonical cover $F_c$$\large F_c$. We can make the following statements about candidate keys for $r$$\large r$.

Required Present

Any attribute that does not appear on the right-hand side of any functional dependency $f\in F_c$$\large f \in F_c$ must be present in every candidate key of $r$$\large r$.

Required Absent 1

Any attribute that does not appear on the left-hand side of any functional dependency $f\in F_c$$\large f \in F_c$ but appears on the right-hand side of at least one functional dependency $f\in F_c$$\large f \in F_c$ must be absent in every candidate key of $r$$\large r$.

Required Absent 2

Any attribute that appears on the right-hand side of any functional dependency $f\in F_c$$\large f \in F_c$ where all the attributes on the left-hand side are required, must be absent in every candidate key of $r$$\large r$.

Maybe Present

Any attribute that appears on the left-hand side of some functional dependency $f\in F_c$$\large f \in F_c$ and the right hand-side of some other functional dependency $f\in F_c$$\large f \in F_c$ must be absent in at least one candidate key of $r$$\large r$.

First Normal Form

Given a relation $r$$\large r$ with the set of all attributes $R$$\large R$, $r$$\large r$ is in first normal form if and only if every attribute in $R$$\large R$ is atomic. In other words, if any of the attributes can be divided into multiple attributes for major uses within the context of the database and is not a type that is supported as multiple values in the database engine, the relation $r$$\large r$ is not in first normal form.

Third Normal Form

Given a relation $r$$\large r$ with the set of all attributes $R$$\large R$ and a set of functional dependencies $F$$\large F$, $r$$\large r$ is in third normal form if and only if, for every functional dependency $\alpha \to \beta$$\large \alpha \to \beta$ in $F$$\large F$, at least one of the following is true:

• $\beta \subseteq \alpha$$\Large \beta \sube \alpha$
• $\alpha$$\Large \alpha$ is a super key for $R$$\Large R$
• ${\mathrm{\forall }}_{B\in \beta -\alpha }B$$\Large \forall_{B \in \beta - \alpha} \:\: B$ is an attribute that exists in some candidate key.

Intuitively, third normal form is just enforcing a table to describe a single entity. By requiring every functional dependency to either have $\alpha$$\large \alpha$ as a super key or have every attribute in $\beta$$\large \beta$ in at least one candidate key, it is enforcing that every attribute in this relation is a part of the same entity and cannot be neatly broken down into multiple entities.

Third Normal Form Decomposition

The steps for decomposing relation $r$$r$ to multiple relations that are in third normal form are as follows:

• For each functional dependency $(\alpha \to \beta )\in F$$\large (\alpha \to \beta) \in F$, create relation $(\alpha ,\beta )$$\large (\alpha, \beta)$ and add it to the schema
• If any attributes are left out, add them in a relation with a candidate key
• Optimize the relations to get rid of relations that are redundant

Boyce-Codd Normal Form

Given a relation $r$$\large r$ with the set of all attributes $R$$\large R$ and a set of functional dependencies $F$$\large F$, $r$$\large r$ is in Boyce-Codd normal form if and only if, for every functional dependency $\alpha \to \beta$$\large \alpha \to \beta$ in $F$$\large F$, at least one of the following is true:

• $\beta \subseteq \alpha$$\Large \beta \sube \alpha$
• $\alpha$$\Large \alpha$ is a super key for $R$$\large R$

Boyce-Codd Normal Form Decomposition

The steps for decomposing relation $r$$r$ to multiple relations that are in Boyce-Codd normal form are as follows:

• For each functional dependency $(\alpha \to \beta )\in F$$\large (\alpha \to \beta) \in F$ that is not BCNF compliant, create relations $R_1=\alpha \cup \beta$$\large R_1 = \alpha \cup \beta$ and $R_2=R-\beta$$\large R_2 = R - \beta$
• Repeat the previous step recursively for $R_1$$\large R_1$ and $R_2$$\large R_2$.