Difference between revisions of "Normalization"

From Wiki Notes @ WuJiewen.com, by Jiewen Wu
Jump to: navigation, search
m (Functional Dependency (FD))
m (Functional Dependency (FD))
 
(One intermediate revision by the same user not shown)
Line 12: Line 12:
  
 
===Entailment===
 
===Entailment===
A set of FDs X entails another set of FDs Y if X entails every FD in Y. That is, if every relation satisfies every FD in X, it must satisfy every FD in Y.
+
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 X, denoted as X<sup>+</sup>
+
The closure of F, denoted as F<sup>+</sup>, is the set of all '''FDs''' entailed by F. The attribute closure is the set of all '''attributes''' A s.t. X->A is entailed by F, i.e.,
 +
 
 +
X<sub>F<sup>+</sup></sub> = {A | X->A in F<sup>+</sup>}

Latest revision as of 13:19, 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 the set of all attributes A s.t. X->A is entailed by F, i.e.,

XF+ = {A | X->A in F+}