> `_(
/0DTimes New Roman 7d0Wo
0DTahomaew Roman 7d0Wo
0" DMonotype Sorts 7d0Wo
0e.
@n?" dd@ @@``TLlY
c$`f3f33f@g4CdCd0pjppp@uʚ;2Nʚ;<4!d!dЁ
0<4ddddЁ
0<4BdBdЁ
0&___PPT9/0
4L?O=e'Multivalued Dependencies
Fourth Normal FormDefinition of MVD0A 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, and the result will be two tuples that are also in the relation.
i.e., for each value of X, the values of Y are independent of the values of RXY.1f!k#>3ot Example\Drinkers(name, addr, phones, beersLiked)
A drinker s phones are independent of the beers they like.
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.)Z;Z(ZZZ);&3f
P
Y
Tuples Implied by name>>phones"!((3f
Picture of MVD X >>Y: MVD Rules2Every 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.P!P f$af$>J$,Splitting Doesn t HoldtLike FD s, we cannot generally split the left side of an MVD.
But unlike FD s, we cannot split the right side either  sometimes you have to leave several attributes on the right side. ExampleDrinkers(name, areaCode, phone, beersLiked, manf)
A drinker can have several phones, with the number divided between areaCode and phone (last 7 digits).
A drinker can like several beers, each with its own manufacturer.*22P
E ]
Example, ContinuedSince the areaCodephone combinations for a drinker are independent of the beersLikedmanf combinations, we expect that the following MVD s hold:
name >> areaCode phone
name >> beersLiked manf*75t
9
+ Example DataFourth Normal FormThe 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.,W
4NF DefinitionA relation R is in 4NF if: whenever X >>Y is a nontrivial MVD, then X is a superkey.
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.*aN" C33
ff(C>&,BCNF Versus 4NFRemember that every FD X >Y is also an MVD, X >>Y.
Thus, if R is in 4NF, it is certainly in 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.gLL&LGDecomposition and 4NFZIf 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.iEw"(.ExampleZDrinkers(name, addr, phones, beersLiked)
FD: name > addr
MVD s: name >> phones
name >> beersLiked
Key is {name, phones, beersLiked}.
All dependencies violate 4NF.mA
)33 b
!
!Example, ContinuedDecompose 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.Nu)u$utu
8t%
7Example: Decompose Drinkers2Either MVD name >> phones or name >> beersLiked tells us to decompose to:
Drinkers3(name, phones)
Drinkers4(name, beersLiked)O4
,*B
` ̙33` ` ff3333f` 333MMM` f` f` 3>?" dd@,?udd@ w " @ ` n?" dd@ @@``PR @ ` `p>>f(
6n P
T Click to edit Master title style!
!
0dp
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
S
0xv ``
>*
0z `
@*
0~ `
@*Z
Byh@ ? ̙33 Default Design
0zrP
(
0Bj P
j
P*
0Ej j
R*
d
c$ ?
j
0Cj
@j
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
S
6Mj `P j
P*
6dRj ` j
R*
H
0h ? ̙330 $(
r
S:p:
r
S: `
:
H
0h ? ̙33
0$(
0r
0 S,jP
j
r
0 Sjj
H
00h ? ̙33
`($(
(r
( Sj
j
r
( Sj P0j
H
(0h ? ̙33Z
p,(
,r
, SpjP
j
,
<j,$D
0
dIf we have tuples:>
,
<j`
,$D
0
:name addr phones beersLiked
sue a p1 b1
sue a p2 b2;;,Fl f
, f
,$D
0
,
<pj`
Qsue a p2 b1
sue a p1 b2
,
<jFf
/Then these tuples must also be in the relation.0.LB
,
c$D0LB
,
c$D LB
,
c$D LB
,
c$D
H
,0h ? ̙33

8(
8r
8 SDP
LB
8
c$DLB
8
c$D LB
8
c$D 0` LB
8
c$D p LB
8
c$D0`LB
8
c$Dp
8
<D>
( X Y others
equal
exchangeJ)!RB
8
s*D00RB
8
s*Dp00 RB
8
s*D0 0 RB
8
s*D
H
80h ? ̙33
<P(
<r
< SP:P
:
< SP:<$
0:
H
<0h ? ̙33
@$(
@r
@ S8P
r
@ S
H
@0h ? ̙33
D$(
Dr
D S< P
r
D S"
H
D0h ? ̙33
H$(
Hr
H S'P
r
H S@(
H
H0h ? ̙33
{
L(
Lr
L S,P
L
<H/%
<Here is possible data satisfying these MVD s:
name areaCode phone beersLiked manf
Sue 650 5551111 Bud A.B.
Sue 650 5551111 WickedAle Pete s
Sue 415 5559999 Bud A.B.
Sue 415 5559999 WickedAle Pete sb' .
5
L
<7uWa,$D
0
But we cannot swap area codes or phones by themselves.
That is, neither name>>areaCode nor name>>phone
holds for this relation.LHP,X
L
0 LB
L
c$DLB
L
c$D LB
L
c$D LB
L
c$D LB
L
c$D H
L0h ? ̙33
P$(
Pr
P SBP
r
P StC
H
P0h ? ̙33
T:(
Tr
T SIP
T SN
"p`PpH
T0h ? ̙33
XP(
Xr
X S`:P
X Spj:<$
0:
H
X0h ? ̙33
\:(
\r
\ ScP
\ S:
"p`PpH
\0h ? ̙33
0`$(
`r
` S
lIHO`QLS8U$W^`beghjl6COh+'0.`h
CS206  Electronic CommercetJeff Ullmanjeffrey d. ullmanic62fMicrosoft PowerPointCom@GV@}J@]Gg "& &&#TNPP@2OMi
&
TNPP &&TNPP
&&&&$0>$>L$LZ*$*Zh8$8hvF$FvT$Tb$bp$p~$~$$$$$$$$,$,:
$
:H$HV&$&Vd4$4drB$BrP$P^$^k$ky$y$$$$$$$$'$'5$5C$CQ!$!Q_/$/_m=$=m{K$K{Y$Yg$gu$u$$$$$$$$#$#1$1?$?M$M[+$+[i9$9iwG$GwU$Uc$cq$q$$$$$$$$$$;$;I$IW'$'We5$5erB$BrP$P^$^l$lz$z$$$$$$$$($(6$6D$DR"$"R`0$0`n>$>nL$LZ$Zh$hv$v$$$&&&&$&&&&
&&&&&&$0>$>L$LZ*$*Zh8$8hvF$FvT$Tb$bp$p~$~$$$$$$$$,$,:
$
:H$HV&$&Vd4$4drB$BrP$P^$^k$ky$y$$$$$$$$'$'5$5C$CQ!$!Q_/$/_m=$=m{K$K{Y$Yg$gu$u$$$$$$$$#$#1$1?$?M$M[+$+[i9$9iwG$GwU$Uc$cq$q$$$$$$$$$$;$;I$IW'$'We5$5erB$BrP$P^$^l$lz$z$$$$$$$$($(6$6D$DR"$"R`0$0`n>$>nL$LZ$Zh$hv$v$$$&
&&&y&w@
g؟ww wf @Times New Roman؟ww wf . 2
f1 .iyH @"Tahoma
k؟ww wf .2
CMultivalued !
!!. .2
CDependencies(!!!!
.Q1 @"Tahoma
؟ww wf ."2
!Fourth Normal Form
#
$."Systemf
!&TNPP &՜.+,0P
(Onscreen ShowStanford University, CS Dept.DqmX Times New RomanTahomaMonotype SortsDefault DesignMultivalued DependenciesDefinition of MVDExample!Tuples Implied by name>>phonesPicture of MVD X >>Y
MVD RulesSplitting Doesnt HoldExampleExample, Continued
Example DataFourth Normal Form4NF DefinitionBCNF Versus 4NFDecomposition and 4NFExampleExample, ContinuedExample: Decompose Drinkers2Fonts UsedDesign Template
Slide Titles)_Mmjeffrey d. ullmanjeffrey d. ullman
!"#$%&'()*+,./012345689:;<=>?@ABCDEFGHIJKLMNPQRSTUVXYZ[\]^aRoot EntrydO)Current UserWSummaryInformation(7/PowerPoint Document(qmDocumentSummaryInformation8O