Higher Forms of Normalization"Lossless" JoinsPreserving FDsFact of life...Multivalued Dependencies (MVDs)Fourth Normal FormFifth Normal FormNormalization SummaryCaveat11/6/97 K-1© 1997 UW CSEHigher Forms of NormalizationChapter 13.1-13.3(skim)11/6/97 K-2"Lossless" Joins•The main idea: if you decompose a relation schema, then join the parts of an instance via a natural join, you might get more rows than you started with, i.e., spurious tuples–This is bad!–Called a "lossy join".•Goal: decompositions which produce only "lossless" joins–"non-additive" join is more descriptive11/6/97 K-3Preserving FDs•What if, when a relation is decomposed, the X of an XY ends up only in one of the new relations and the Y ends up only in another?•Such a decomposition is not dependency-preserving.•Goal: Always have FD-preserving decompositions11/6/97 K-4Fact of life...Finding a decomposition which is both lossless and dependency-preserving is not always possible.11/6/97 K-5Multivalued Dependencies (MVDs)•XY means that given X, there is a unique set of possible Y values (which do not depend on other attributes of the relation)•Classic example: PARENTNAMECHILDNAME•An FD is also a MVD•MVD problems arise if there are two independent 1:N relationships in a relation.11/6/97 K-6Fourth Normal Form•A relation R is in 4NF if for every nontrivial XY, X is a superkey of R.•Decomposition into 4NF: If there is a non-trivial XY, form one relation with only X and Y, and another with R-Y.•This will be lossless, but not necessarily FD-preserving.–Achieving 4NF is a trade-off11/6/97 K-7Fifth Normal Form•Sometimes a relation cannot be losslessly decomposed into two relations, but can be into three or more.•5NF captures the idea that a relation scheme must have some particular lossless decomposition ("join dependency").•Finding actual 5NF cases is difficult.11/6/97 K-8Normalization Summary•1NF: usually part of the woodwork–even so, know how to decompose•2NF: usually skipped–but lots of defs. that make great exam Q's!•3NF: a biggie–Always aim for this•BCNF and 4NF: tradeoffs start here –in re: d-preserving and losslessness•5NF: You can say you've heard of it...11/10/97 K-9Caveat•Normalization is not the be-all and end-all of DB design•Example: suppose attributes A and B are always used together, but normalization theory says they should be in different tables.–Normalization might produce unacceptable performance loss (extra disk
View Full Document