Multivalued Dependencies

Fourth Normal Form

Reasoning About FD’s + MVD’s

1
 Definition of MVD
‹A multivalued dependency (MVD) on
R, X ->->Y , says that if two tuples of R
agree
g on all the attributes of X, then
their components in Y may be
swapped and the result will be two
swapped,
tuples that are also in the relation.
‹i.e., for each value of X, the values of Y
are independent
p of the values of R-X-Y.
2
 E
Example:
l MVD
Drinkers(name, addr, phones, lemonadesLiked)
‹A drinker
drinker’ss phones are independent of the
lemonades they like.
Š name->->phones and name ->->lemonadesLiked.
->->lemonadesLiked
‹Thus, each of a drinker’s phones appears with
each of the lemonades they like in all
combinations.
‹This repetition is unlike FD redundancy.
Š name->addr is the onlyy FD.
3
Tuples Implied by name->->phones
If we have tuples:

name addr phones lemonadesLiked

sue a p1
1 l1
sue a p2 l2
sue a p2 l1
sue a p1 l2
Th these
Then th tuples
t l mustt also
l beb in
i the
th relation.
l ti

4
Picture of MVD X ->->Y

X Y others

equal

exchange

5
 MVD Rules
‹Every FD is an MVD (promotion ).
Š If X ->Y, then swapping Y ’s between two
tuples
p that agree
g on X doesn’t change
g the
tuples.
Š Therefore, the “new”
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.
6
 Splitting Doesn’t Hold
‹Like FD’s, we cannot generally split the
left side of an MVD.
‹But unlike FDFD’ss, we cannot split the
right side either --- sometimes you have
to leave several attributes on the right
side.

7
Example: Multiattribute Right Sides
Drinkers(name, areaCode, phone,
lemonadesLiked, manf)
‹A drinker can have several phones
phones,
with the number divided between
areaCode and phone (last 7 digits).
digits)
‹A drinker can like several lemonades,
each with its own manufacturer.

8
 Example Continued
‹Since the areaCode-phone
combinations for a drinker are
p
independent of the lemonadesLiked-
manf combinations, we expect that the
following MVD
MVD’ss hold:
name ->-> areaCode phone
name ->-> lemonadesLiked manf

9
 Example Data
Here is possible data satisfying these MVD’s:

name areaCode phone lemonadesLiked manf

Sue 650 555-1111 Bud A.B.
A B
Sue 650 555-1111 WickedAle Pete’s
Sue 415 555-9999 Bud A.B.
Sue 415 555-9999 WickedAle Pete’s

But we cannot swap area codes or phones by themselves.

That is, neither name->->areaCode nor name->->phone
holds for this relation
relation.
10
 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
4NF, MVD s as
FD’s when it comes to decomposition,
but not when determining keys of the
relation.
11
 4NF Definition
‹ A relation R is in 4NF if: whenever
X ->->Y is a nontrivial MVD, then X
is a superkey.
p y
Š Nontrivial MVD means that:
1. Y is not a subset of X, and
1
2. X and Y are not, together, all the attributes.
Š Note that the definition of “superkey” still
depends on FD’s only.

12
 BCNF Versus 4NF
‹Remember that every FD X ->Y is also
an MVD, X ->->Y.
‹Thus if R is in 4NF,
‹Thus, 4NF it is certainly in
BCNF.
Š Because
B any BCNF violation
i l ti iis a 4NF
violation (after conversion to an MVD).
‹But R could be in BCNF and not 4NF,
because MVD’s
MVD s are “invisible”
invisible to BCNF.
13
 Decomposition and 4NF
‹ If X ->->Y is a 4NF violation for
relation R, we can decompose R
usingg the same technique
q as for BCNF.
1. XY is one of the decomposed relations.
2 All but Y – X is the other.
2. other

14
 Example: 4NF Decomposition
Drinkers(name, addr, phones, lemonadesLiked)
FD: name -> addr
MVD’s:
MVD s: name ->->
> > phones
name ->-> lemonadesLiked
‹Key is {name, phones, lemonadesLiked}.
‹All dependencies violate 4NF.
4NF

15
 Example Continued
‹ Decompose using name -> addr:
1. Drinkers1(name, addr)
‹ In 4NF; only dependency is name -> addr.
addr
2. Drinkers2(name, phones, lemonadesLiked)
‹ Not in 4NF. MVD’s name ->-> phones and
name ->-> lemonadesLiked apply. No FD’s,
so all three attributes form the key.

16
Example: Decompose Drinkers2
‹Either MVD name ->-> phones or
name ->-> lemonadesLiked tells us to
p
decompose to:
Š Drinkers3(name, phones)
Š Drinkers4(name,
Drinkers4(name lemonadesLiked)

17
Reasoning About MVD’s + FD’s
‹Problem: given a set of MVD’s and/or
FD’s that hold for a relation R, does a
certain FD or MVD also hold in R ?
‹Solution: Use a tableau to explore all
inferences from the given set
set, to see if
you can prove the target dependency.

18
 Why Do We Care?
1. 4NF technically requires an MVD
violation.
Š Need to infer MVD’s
MVD s from given FD’s
FD s and
MVD’s that may not be violations
themselves.
2. When we decompose, we need to
project FD’s + MVD’s
MVD’s.

19
 Example: Chasing a Tableau
With MVD
MVD’ss and FD
FD’ss
‹To apply a FDFD, equate symbols
symbols, as
before.
‹To apply an MVD, generate one or both
of the tuples we know must also be in
the relation represented by the tableau.
‹We’llll prove: if A
‹We A->->BC
BC and D
D->C,
C, then
A->C.

20
 The Tableau for A->C
Goal: prove that c1 = c2.

A B C D
a b1 c1 c2 d1
a b2 c2 d2
a b2 c2 d1

Use D->C (first and

Use A
A->->BC
> >BC (first row
row’ss third row agree on D,
D with second row’s BC ). 21 C ).
therefore agree on
Example: Transitive Law for MVD’s
‹If A->->B and B->->C, then A->->C.
Š Obvious from the complementation rule if
the Schema is ABC.
Š But it holds no matter what the schema;
we’llll assume ABCD.
we

22
 The Tableau for A->->C
Goal: derive tuple (a,b1,c2,d1).

A B C D
a b1 c1 d1
a b2 c2 d2
a b1 c2 d2
a b1 c2 d1
Use A > >B to swap B from
A->->B Use B > >C to swap C from
B->->C
the first row into the second. the third row into the first.
23
Rules for Inferring MVD’s + FD’s
‹Start with a tableau of two rows.
Š These rows agree on the attributes of the
left side of the dependency
p y to be inferred.
Š And they disagree on all other attributes.
Š Use unsubscripted variables where they
agree, subscripts where they disagree.

24
 Inference: Applying a FD
‹Apply a FD X->Y by finding rows that
agree on all attributes of X. Force the
g
rows to agree on all attributes of Y.
Š Replace one variable by the other.
Š If the replaced variable is part of the goal
tuple, replace it there too.

25
 Inference: Applying a MVD
‹Apply a MVD X->->Y by finding two
rows that agree in X.
Š Add to the tableau one or both rows that
are formed by swapping the Y-components
of these two rows.

26
 Inference: Goals
‹To test whether U->V holds, we
succeed by inferring that the two
variables in each column of V are
actually the same.
‹If we are testing U
U->->V,
> >V, we succeed if
we infer in the tableau a row that is the
original two rows with the components
of V swapped.
27
 Inference: Endgame
‹Apply all the given FD’s and MVD’s until
we cannot change the tableau.
‹If we meet the goal
goal, then the
dependency is inferred.
‹If not, then
h theh final
fi l tableau
bl is
i a
p relation.
counterexample
Š Satisfies all given dependencies.
Š Original two rows violate target dependency
dependency.
28
A Complete Set of Inference
Rules

29
 Normal Forms
‹ Every component of every tuple is an atomic value (1NF)
‹ 2NF is permits transitive FD
FD’ss in a relation,
relation but forbids a
nontrivial FD with a left side that is a proper subset of a
key.
y
‹ If whenever A1A2…An->B is a nontrivial FD, either
{A1A2…An } is superkey, or B is a member of some key
(3NF)
‹ If whenever there is a nontrivial FD A1A2…An->B, it is case
that {A1A2…A An } is a superkey (BCNF)
‹ If whenever A1A2…An->->B1B2…Bm is a nontrivial MVD
A1A2…An->B , {A1A2…An } is a superkey (4NF)
30