Normalisation Theory, Dependencies¶
Normalisation Theory¶
- The normalisation theory is used to decide whether or not \(R\) is in a "good form"
- If \(R\) is not in a good form, then it will be decomposed into relations \(\{R_i\}\) such that
- Each relation is itself in good form
- The decomposition is lossless
Functional Dependency¶
There are cosntraints on data in the real world. These constraints manifest in the database as functional dependencies. Some examples include: * Students are uniquely identified by ID * Each Student has only one name * Each Professor is only associated with one department * The department has just one budge
If an instance of a relation satisfies these real-world constraints, we call it a legal instance. A database is called a legal instance if all relation instances in it are legal. A functional dependency is a generalisation of the notion of a key.
Example¶
Consider \(\alpha \subseteq R\) and \(\beta \subseteq R\). The functional dependency \(\alpha \to \beta\) only holds if any two tuples agreeing on a value for \(\alpha\) implies these two tuples will also agree on a value for \(\beta\). Consider the table
| A | B |
|---|---|
| 1 | 4 |
| 1 | 5 |
| 3 | 7 |
In this case, \(B \to A\) holds but \(A \to B\) doesn't.
Closure¶
A set of functional dependencies may be logically implied by the main set. This is decided by basic logic rules. For example, \(\(A \to B,\ B \to C,\ thus\ A \to C\)\) The set of all functional dependencies logically implied by \(F\) is called the closure of \(F\), denoted as \(F^+\)
Armstrong's Axioms¶
These are the axioms we use to compute closures * Reflexive Rule: If \(\beta \subseteq \alpha\), then \(\alpha \to \beta\) * Augmentation Rule: If \(\alpha \to \beta\), then \(\gamma \alpha \to \gamma \beta\) * Transitivity Rule: If \(\alpha \to \beta\), and \(\beta \to \gamma\), then \(\alpha \to \gamma\)
These rules are both correct and comprehensive. Some additional derived rules include, * Union Rule: If \(\alpha \to \beta\) and \(\alpha \to \gamma\), then \(\alpha \to \beta \gamma\) * Decomposition Rule: If \(\alpha \to \beta \gamma\), then \(\alpha \to \beta\) and \(\alpha \to \gamma\) * Pseudo-Transitivity Rule: If \(\alpha \to \beta\) and \(\beta \gamma \to \delta\), then \(\alpha \gamma \to \delta\)