Difference between revisions of "Normalization"
From Wiki Notes @ WuJiewen.com, by Jiewen Wu
m (→Functional Dependency (FD)) |
m (→Entailment) |
||
Line 12: | Line 12: | ||
===Entailment=== | ===Entailment=== | ||
− | A set of FDs | + | A set of FDs F entails another set of FDs G if F entails every FD in G. That is, if every relation satisfies every FD in F, it must satisfy every FD in G. |
− | The closure of | + | The closure of F, denoted as F<sup>+</sup>, is the set of all FDs entailed by F. The attribute closure is |
+ | |||
+ | X<sub>F<sup>+</sup></sub> = {A | X->A in F<sup>+</sup>} |
Revision as of 13:16, 5 August 2010
Functional Dependency (FD)
A FD, an integrity constraint, on a relation scheme R is a constraint X->Y, where X and Y are sets of attributes. For a pair of tuple t and s, they satisfies the above FD if they agree on all attributes in Y whenever they agree on all attributes in X.
Some properties of FDs.
- Trivial (Reflexive) FDs: X->Y if Y is a subset of X.
- Augmentation: if X->Y then XZ->YZ
- Transitivity: if X->Y and Y->Z, then X->Z.
- Union: if X->Y and X->Z, then X->YZ.
- Decomposition: if X->YZ, then X->Y and X->Z.
Entailment
A set of FDs F entails another set of FDs G if F entails every FD in G. That is, if every relation satisfies every FD in F, it must satisfy every FD in G.
The closure of F, denoted as F+, is the set of all FDs entailed by F. The attribute closure is
XF+ = {A | X->A in F+}