Week 9. Functional Dependencies and Normalisation 2

Prime / Non-prime attributes

Prime attribute (Databases)

A Prime attribute is a member of some Candidate Key (Databases).

Link to original

Nonprime attribute (Databases)

A Nonprime is an attribute that is not a Prime attribute (Databases).

Link to original

Normal Forms

Normalisation (Databases)

Normalisation is the process of analysing relation schemas based on FDs and candidate keys to minimise redundancy and insertion, deletion and update anomalies. It is also the process of decomposing unsatisfactory relations by breaking up their attributes into smaller relations.

Link to original

Normal Form (Databases)

A normal form is a condition using keys and FDs of a relation to certify whether a relation schema is in a particular normal form.

Link to original

Normalisation is carried out in practice so that the resulting database designs are of high quality and meet desirable properties. Practical utility of normal forms become questionable when the constraints on which they are based are hard to understand or detect.

We do not need to normalise to greatest extent, usually just up to 3NF of BCNF.

First Normal Form

First Normal Form (Databases)

First Normal Form disallows composite attributes, multi-valued attributes and nested relations (attributes whose values for an individual tuple are non-atomic).

Link to original

Example 1

To normalise: we remove the attribute that causes the problem and place it in a separate relation together with the primary key.

Example 2

Nested relations, as with composite attributes, are disallowed under 1NF. The relation EMP_PROJ is not in 1NF. Primary keys: SSN and Pnumber within nested relation.

To normalise: remove nested relation and place in separate relation together with the primary key, as in (c).

Second Normal Form

Full Functional Dependency (Databases)

A full functional dependency is a FD $Y\to Z$ where removal of any attribute from $Y$ means the FD does not hold anymore.

For example:

• $\{\text{SSN},\text{PNUMBER}\}\to \text{HOURS}$: full FD since neither SSN or PNUMBER into HOURS would hold.
• $\{\text{SSN},\text{PNUMBER}\}\to \text{ENAME}$: not a full FD, since $\text{SSN}\to \text{ENAME}$ also holds, this is called a partial dependency.

Link to original

Second Normal Form (Databases)

Second Normal Form says that a relation schema $R$ is in 2NF if it is in 1NF and every non-prime attribute $A$ in $R$ is fully functionally dependent on the primary key.

Link to original

We can test that the left-hand side in an FD is part of the primary key. (if the primary key contains a single attribute, the test does not need to be applied)

Example

Third Normal Form

Transitive Functional Dependency (Databases)

A transitive functional dependency is a FD $X\to Y$ that can be derived from two other FDs: $X\to Z$ and $Z\to Y$.

Examples:

• $\text{SSN}\to \text{DMGRSSN}$ is a transitive FD as SSN into DNUMBER and DNUMBER into DMGRSSN both hold.
• $\text{SSN}\to \text{ENAME}$ is non-transitive since there is no set of attributes $X$ where $\text{SSN}\to X$ and $X\to \text{ENAME}$.

Link to original

Third Normal Form (Databases))

A relational schema $R$ is in Third Normal Form if:

• It is in 2NF.
• No non-prime attribute $A$ in $R$ is transitively dependent on the primary key.

Link to original

Example

BCNF (Boyce-Codd Normal Form)

First, we can look at an alternative 3NF definition:

• The superkey of relation schema $R$ is a set of attributes $S$ of $R$ that contains a key of $R$ that contains a key of $R$.
• A relation schema $R$ is in Third Normal Form (Databases)) if whenever a FD $X\to A$ holds in $R$, then either:
  • $X$ is a superkey of $R$
  • $A$ is a prime attribute of $R$

In Boyce-Codd NF, we want to eliminate the second condition.

Byoce-Codd Normal Form

A relation schema $R$ is in Boyce-Codd Normal Form if whenever an FD $X\to A$ holds in $R$, then $X$ is a superkey of $R$.

Link to original

Suppose we have the following relation, FD $\text{AREA}\to \text{County\_name}$ holds hence this is not in BCNF, this is because the county name is a prime attribute.

In practice, most relation schema that are in 3NF are also in BCNF.