Multivalued Dependencies
目录
Definition of MVD
Example: MVD
MVD Rules
Fourth Normal Form
4NF Definition
BCNF Versus 4NF
Decomposition and 4NF
Example: 4NF Decomposition
Definition of MVD
A multivalued dependency (MVD) on R, X ->->Y
-
says that if two tuples of R agree on all the attributes of X, then their components in Y may be swapped（多值依赖讲的是当X中的值全相等，那么Y的值是可交换的）
-
the result will be two tuples that are also in the relation（交换后的元组也在关系中）
-
for each value of X, the values of Y are independent of the values of R-X-Y（Y的值是独立于其他属性的）
Example: MVD
Drinkers(name, addr, phones, beersLiked)
A drinker’s phones are independent of the beers they like.（phones是独立于喜爱的啤酒的）
name->->phones and name ->->beersLiked.
Thus, each of a drinker’s phones appears with each of the beers they like in all combinations.（饮酒者的电话号码与他们喜欢的啤酒自由组合）
This repetition is unlike FD redundancy.
name->addr is the only FD.
MVD Rules
Every FD is an MVD (promotion ).
- If X ->Y, then swapping Y ’s between two tuples that agree on X doesn’t change the tuples.
- Therefore, the “new” tuples are surely in the relation, and we know X ->->Y.
Complementation : If X ->->Y, and Z is all the other attributes, then X ->->Z.（多值依赖可以理解为相互独立）
Fourth Normal Form
-
The redundancy（冗余） that comes from MVD’s is not removable by putting the database schema in BCNF.
-
There is a stronger normal form, called 4NF
that (intuitively) treats MVD’s as FD’s when it comes to decomposition, but not when determining keys of the relation.
4NF Definition
-
A relation R is in 4NF if: whenever X ->->Y is a nontrivial MVD, then X is a superkey.（当X非平凡多值依赖与Y时，X一定是超键）
-
Nontrivial MVD means that:
Y is not a subset of X, and X and Y are not, together, all the attributes.
- Note that the definition of “superkey” still depends on FD’s only.（注意的是超键的定义依然取决于函数依赖）
BCNF Versus 4NF
-
Remember that every FD X ->Y is also an MVD, X ->->Y
-
Thus, if R is in 4NF, it is certainly in BCNF.（模式R满足4NF一定满足BCNF）
Because any BCNF violation is a 4NF violation (after conversion to an MVD).
But R could be in BCNF and not 4NF, because MVD’s are “invisible” to BCNF.
Decomposition and 4NF
If X ->->Y is a 4NF violation for relation R, we can decompose R using the same technique as for BCNF.
-
XY is one of the decomposed relations.
-
All but Y – X is the other.
Example: 4NF Decomposition
Drinkers(name, addr, phones, beersLiked)
FD: name -> addr
MVD’s: name ->-> phones 、name ->-> beersLiked
Key is {name, phones, beersLiked}.
-
Decompose using name -> addr: Drinkers1(name, addr) In 4NF;
only dependency is name -> addr.
-
Drinkers2(name, phones, beersLiked) Not in 4NF.
-
MVD’s name ->-> phones and name ->-> beersLiked apply.
No FD’s, so all three attributes form the key.
-
Either MVD name ->-> phones or name ->-> beersLiked tells us to decompose to: Drinkers3(name, phones) 、Drinkers4(name, beersLiked)