Database Normalization

Functional Dependency

Let R(..., A, ..., B, ...) be a relational schema.
There is a functional dependency between A and B denoted $A - > B$ in R if for any instance of R, tuples with the same value for A have the same value for B.

In other words the value of B follows from the value of A.

Examples:

$b i r t h_d a t e - > a s t r o l o g i c a l_s i g n$ : the astrological sign (B) will always be the same for the same values of birth_date (A)
$s s n - > n a m e$ : since the ssn is unique (A) it will agree with name (B)
on the other hand ssn (B) does not functionally depend on birth_date (A) because there can be multiple people born on the same date (and they would have a different B).

Functional Dependencies For Sets:

Functional Dependency

Let R be a relational schema.
Let X, Y be sets of attributes.
There is a functional dependency between X and Y denoted $X - > Y$ in R if for any instance of R, tuples with the same values for X also have the same values for Y.

In other words the values of Y follow from the values of X

Rewrite Rules for FDs

Rewrite Rules

$X Y - > X$ (reflexivity)
$If X - > Y then X Z - > Y Z$ (augmentation)
$If X - > Y and Y - > Z then X - > Z$ (transitivity)
$If X - > Y and Y W - > Z then X W - > Z$
$If X - > Y and X - > Z then X - > Y Z$
$If X - > Y Z then X - > Y and X - > Z$

Rules 1-3 are known as Armstrong's Axioms. Rules 4-6 are convenient rules derived from Armstrong's Axioms.

Closure

For a set of functional dependencies $F$ , it's closure $F^{+}$ is the set of all functional dependencies that can be logically implied by $F$

Algorithms

Naive Algorithm

Compute the closure by applying rewrite rules until no more FDs can be derived.

Smarter Algorithm

If we have $A - > B$ can we find some $Y$ such that $Y - > A$ ? Then from $Y - > A, A - > B$ we derive $Y - > B$ .

Example

Given: $A B C - > E, C D - > B, E - > D$ Which new FD's can we derive ?

Applying $E - > D$ to $C D - > B$ yields $C E - > B$ ( $C E - > C D - > B$ )
Applying $A B C - > E$ to $E - > D$ yields $A B C - > D$
Applying $C D - > B t o A B C - > E y i e l d s A C D - > E$

Written Formally:

Let,

F = {A B C - > E, C D - > B, E - > D} $ $ b e t h e s e t o f F D s f o r a r e l a t i o n * R (A, B, C, D, E) * T h e c l o s u r e o f t h i s s e t : $ $ F^{+} = {A B C - > D E, A C D - > E, C D - > B, C E - > B, E - > D}

Notation

Discard trivial FDs (like $A B C - > A$ )
Consider only FDs with a single attribute as the right hand side.
If FDs have identical left-hand sides, combine them as a shorthand notation. (i.e. $A B C - > D E$ for $A B C - > D, A B C - > E$ )

show table

S	N	B	A
115565789	Alice Anderson	1987-04-15	Aries
136729221	Bill Brown	1973-05-02	Taurus
262823054	Bill Brown	1998-03-21	Aries
228923541	Chris Carpenter	1992-07-17	Leo

Example

F = {S - > N B, B - > A}

we can add $S - > A from S - > B, B - > A$

F^{+} = {S - > N B A, B - > A}

Closure of a set of attributes

$X^{+} = X \cup {all attributes that are functionally dependent on X}$

For example:

F = {c o u r s e - > r e s p o n s i b l e, r e s p o n s i b l e - > o f f i c e t e l_n o, t e l_n o - > o f f i c e}

${r e s p o n s i b l e}^{+} = {r e s p o n s i b l e o f f i c e t e l_n o}$
${c o u r s e}^{+} = {c o u r s e r e s p o n s i b l e o f f i c e t e l_n o}$
${o f f i c e}^{+} = {o f f i c e}$
${t e l_n o}^{+} = o f f i c e t e l_n o$

Normal Forms

1NF

All attributes have atomic values: each attribute contains a single value.

This normal form is enforced by default by the way we construct database schemas: consequence of the principle that attributes in a class diagram cannot have set values.

2NF

The relation is in 1NF There is no non-prime attribute that is functionally dependent on a proper subset of a candidate key.

non-prime attribute: an attribute that is not part of any candidate key.

In other words all non-key attributes are fully dependent on the primary key.

Example

Not 2NF Not Normalized

course	teacher	office
Database Theory	Rebecca Roberts	AB 183
Database Theory	Stuart Stevens	AB 240
Database Theory	Theresa Thompson	H 3072
Advanced Programming	Stuart Stevens	AB 240
Advanced Programming	William Walters	H 3122

Functional dependency: $t e a c h e r - > o f f i c e$
One candidate key: course teacher
Not in 2NF because: office depends on part of the candidate key. (teacher)

2NF Normalized

course	teacher
Database Theory	Rebecca Roberts
Database Theory	Stuart Stevens
Database Theory	Theresa Thompson
Advanced Programming	Stuart Stevens
Advanced Programming	William Walters

teacher	office
Rebecca Roberts	AB 183
Stuart Stevens	AB 240
Theresa Thompson	H 3072
William Walters	H 3122

Functional dependencies:

{c o u r s e - > r e s p o n s i b l e r e s p o n s i b l e - > o f f i c e}

One candidate key: course.

3NF

The relation is in 2NF
No non-prime attribute is transitively dependent on a superkey

transitive dependency: $X - > and Y - > Z$ then Z is transitivley dependent on X.

Example:

not 3NF Not Normalized

course	responsible	office
Database Theory	Rebecca Roberts	AB 183
Advanced Programming	William Walters	AB 240
Operation Systems	William Walters	AB 240
Artificial Intelligence	Phil Petersen	PT 5120
Discrete Mathematics	Naomi Nilsson	H 2403

Functional dependencies:

{c o u r s e - > r e s p o n s i b l e r e s p o n s i b l e - > o f f i c e}

Transitive dependency: $c o u r s e - > o f f i c e$

A non-prime attribute office is transitively dependent on the superkey course, therfore the relation is not in 3NF.

3NF Normalized

course	responsible
Database Theory	Rebecca Roberts
Advanced Programming	William Walters
Operation Systems	William Walters
Artificial Intelligence	Phil Petersen
Discrete Mathematics	Naomi Nilsson

responsible	office
Rebecca Roberts	AB 183
William Walters	H 3122
Phil Petersen	PT 5120
Naomi Nilsson	H 2403

BCNF (Boyce-Codd Normal Form)

BCNF

If $X - > Y$ is a functional dependecy of R, then either $X - > Y$ is a trivial dependency (i.e $Y \subseteq X$ ) or X is a superkey of R.

or:

A relation is in BCNF if the left-hand side of every nontrivial FD is a superkey.

BCNF decomposition algorithm

The BCNF decomposition algorithm serves allows us to make a relational schema satisfy BCNF.

algorithm

Let R be a relational schema. FD X -> Y be a violation of the BCNF constraint
- compute $X^{+}$
- $R_{1} = X^{+}$
- $R_{2} = X \cup {a l l a t t r i b u t e s n o t i n X^{}}$
- Compute FDs for $R_{1}$ and $R_{2}$
If $R_{1}$ or $R_{2}$ not in BCNF, apply the same rules.

The decomposition is losless, i.e. an instance of R can be reconstructed from instances of $R_{1}$ and $R_{2}$ .

Decomposition Properites

elimination of anomalies
recoverability of information (losslessness)
Preservation of dependencies

BCNF guarantees 1,2
3NF guarantees 2,3

Multivalued Dependencies

MVD

Let R(XYZ) be a relational schema
Let X, Y, Z be sets of attributes (a mvd only exists when there are at least three attributes.)

$X ↠ Y$ if for any instance of R the following holds:

If $x y_{1} z_{1} in R and x y_{2} z_{2} in R$
Then also $x y_{1} z_{2} in R and x y_{2} z_{1} in R$

$↠$ is called a multivalued dependency.

Example

Kindergarten has a database with parents, their tel numbers and their children. This is their table:

| parent | tel_no | child | | Alice Anderson| 053-4332567| Tom | | Alice Anderson | 06-10547732 | Tom | | Alice Anderson | 053-4332567 | Bram | | Alice Anderson | 06-10547732 | Bram | | Bob Anderson | 053-4332567 | Tom | | Bob Anderson | 053-4332567 | Bram | Deborah Davids | 074-2662359 | Harry | | Deborah Davids | 06-18809372 | Harry |

this table is in BCNF because it has no functional dependencies.

But if a new child would be born we would have to add to add a new row to the table for each tel_no of that parent. 😬

There are two multivalued dependencies in this relation: ${p a r e n t} ↠ {t e l_{n} o} and {p a r e n t} ↠ {c h i l d}$

MVD Properties

Let R(XYZ) be a relation:

If $X ↠ Y then X ↠ Z$
If $X - > Y then X ↠ Y$

Fourth normal form

4NF

If $X ↠ Y$ a functional dependency of R, then either X \twoheadrightarrow Y is a trivial MVD (i.e. $Y \subseteq X$ ) or X is a superkey of R.

Example

MVDs:

${p a r e n t} ↠ {t e l_{n} o}$
${p a r e n t} ↠ {c h i l d}$ Candidate key:
(parent, tel_no, child)

Decomposition:

parent	tel_no
Alice Anderson	053-4332567
Alice Anderson	06-10547732
Bob Anderson	053-4332567
Bob Anderson	053-4332567
Deborah Davids	074-2662359
Deborah Davids	06-18809372

parent	child
Alice Anderson	Tom
Alice Anderson	Bram
Bob Anderson	Tom
Bob Anderson	Bram
Deborah Davids	Harry

OS-&-CN

Calculus

Mathematics

Information-Literacy

Information Management

Production Management

Supply Chain Management

OOP

basics

data-structures

networks

security

software-development

book

1-reasoning

2-optimization

3-ML

decision-trees

Readings

week1

week2

week3

week4

DQ

Ethics

Knowledge Representation

ML

Architectures

XAI

Database Normalization ​

Functional Dependency ​

Rewrite Rules for FDs ​

Closure ​

Algorithms ​

Naive Algorithm ​

Smarter Algorithm ​

Example ​

Closure of a set of attributes ​

Normal Forms ​

1NF ​

2NF ​

Example ​

3NF ​

Example: ​

BCNF (Boyce-Codd Normal Form) ​

BCNF decomposition algorithm ​

Decomposition Properites ​

Multivalued Dependencies ​

Fourth normal form ​

Database Normalization

Functional Dependency

Rewrite Rules for FDs

Closure

Algorithms

Naive Algorithm

Smarter Algorithm

Example

Closure of a set of attributes

Normal Forms

1NF

2NF

Example

3NF

Example:

BCNF (Boyce-Codd Normal Form)

BCNF decomposition algorithm

Decomposition Properites

Multivalued Dependencies

Fourth normal form