07-04-multivalued-dependencies.mp4

This video continues the topic

of relational design, talking specifically

about multivalued dependencies and Fourth Normal Form.

I know I've reminded you many times

about relational designed by decomposition,

so let me do it very quickly.

The designer specifies mega relations

with all the information they

want to store and properties of the data.

The system decomposes the mega

relations into smaller relations that

have good properties -- no anomalies and no lost information.

When we have functional dependencies, as

are properties of the data, we

get Boyce-Codd Normal form, and

then when we add to the

functional dependencies multi-value dependencies

we get fourth normal form.

And the specification of multi-

value dependencies and decomposition into

Fourth Normal Form is the topic of this video.

As a reminder from earlier,

Fourth Normal Form is stronger

than Boyce-Codd Normal Form so

if we have here all of

the relations that are in Boyce-

Codd normal form, some subset

of those are also in fourth normal form.

When we have functional dependencies, we can guarantee Boyce Codd normal

form and then when we add

multi-value dependencies that's what

allows us to narrow down to

the stronger property of fourth normal form.

So let's start with an example.

We have information about students applying to colleges.

The student is identified by their social security number.

They may apply to several colleges

and in this video we're not going

to have college states, just college names.

We'll assume they're unique.

And then the student may have hobbies.

And they may apply, as I've said,

to several colleges and have several

hobbies, but let's assume for now those are independent.

So do we have any functional dependencies for this relation?

Actually we don't have any all.

The social security number does

not determine the college name

or the hobby or anything in the other direction.

With no functional dependencies, the

only key for the relation

then is all attributes of the relation.

So is this relation in Boyce-Codd Normal Form?

As you might remember from the

previous video, Boyce-Codd

Normal Form says all functional

dependencies have a key on the left hand side.

Well, since we have no functional dependencies then the answer is yes.

It is in Boyce-Codd normal form.

On the other hand do we think this is a good design?

I'm going to say no this is not a good design Why not?

Well, let's suppose that somebody

applies to five colleges

and they have, say, six hobbies.

Then to have all

combinations of colleges and

hobbies that would yield 30

tuples in the relation and clearly that's not a good idea.

We'd rather separate the college

and hobbies if they are independent.

So the separation of independent facts

is what fourth normal form is about.

And now let's get a little bit more formal.

Like functional dependencies, multivalued dependencies

are specified based on knowledge

of the real world constraints on

the data being captured and all

instances of a relation

with a multivalued dependency must adhere to the dependency.

Now let's define exactly what a multi value dependency is.

For relation R we write

a multi value dependency using

a double headed arrow and

we say 'A' multi determines 'B'.

In this case, again, with 'A'

and 'B' possibly being sets of attributes, so that would be A

one through A N

and B one through B

M, which I'm abbreviating with A bar and B bar.

So let me write the formal definition of A multi

determines B. Again using first

order logic similarly to what

we did with functional dependencies but this one's a bit more complicated.

It says for all tuples T and

U that are in relation

R, if T with

the attributes A of T equal U

for the attributes A of U. Again these are lists of attributes.

So if the two tuples agree on

their A values then, and

remember for functional dependencies it was

simple we just said they agreed on their B values.

But now it gets more complicated.

We're going to say that there exists

a third tuple V in R that has the following properties.

V has the same A

values as T and

U. So V sub A equals

T sub A, furthermore V

has its B value,

okay, drawn from T

so it's equal there.

And finally it has its

rest, so those are

all the attributes other than

A and B equal to U rest.

Okay, so that's a mouthful but let's look at that pictorially.

So here's our relation R and

we'll have the set of

attributes A, the set of

attributes B and the rest of the attributes.

And now let's make some tuples.

So let's say that this

is tuple T and this

is tuple U. And we

said that T and U

agree on their A values.

So they have the same A values

and then they don't have to have the same B values.

So we'll call the first one B-1

and the second one B-2 and

then for the rest we'll call this R-1 and R-2.

So what the multi -value dependency

says is that we have a

third tuple, V and

V again has the same

A and it has

its B value from tuple

T. So it has B-1,

but it has its rest value

from tuple U, so then

it has R-2 here.

So again what we're saying is

that if we have these first

two tuples T and U,

then we also have tuple

V. Now let me do something a little tricky.

Let me swap the roles of

T and U and show

that we also with this definition,

are guaranteed to have a

fourth tuple and we'll call

that fourth tuple W. By

swapping the roles of

T and U, W has again the same A value.

Now it will take its B

value from U and that

will give us B2, and

we'll take its rest

value from T and that gives us R1.

So what we can see

here is that when we

have the first two tuples

that have this particular combination of

B values and rest values,

it tells us we

must have the other combinations as well.

We must have B1 with R2,

and B2 with R1.

What it's really saying

is those B values and

the rest values are independent of each other and we'll have all combinations.

So that might get you thinking

back to our colleges and hobbies.

Incidentally, sometimes multi-value dependencies

are called tuple generating dependencies.

And that's because the definition is

is about having additional tuples

when you have some existing tuples,

unlike functional dependencies which

just talk about the relationships among existing tuples.

So let's go back to our example.

Now we have students applying to colleges and having hobbies.

Those are independent facts about the student.

We'll write our multi-value dependency

as 'social security number multi

determine C name' and

now lets use some example

data to see our definition and how it works here.

Here's our apply relation with the

social security number, the college

name and the hobby.

Let's suppose that we have

a student, 123 who's applied

to Stanford and plays the trumpet.

Now, let's suppose that same

student, 123, has applied

to Berkeley and plays tennis.

So what our multivalued dependency

says, and let's make this

tuple T and tuple U,

is that there's a further tuple

V. V takes the

same social security number and

it takes the first value

for the college name and

the second for the hobby.

It says if we have

a 123 playing trumpet at Stanford

and tennis at Berkeley, then that

same person will be playing tennis at Stanford.

Furthermore, I show that the same definition will generate automatically.

A fourth tuple with the

other combination which would be Berkley and Trumpet.

By the way one thing you

might notice here is that

we also have the multivalued

dependency, social security number multi determines hobby.

This is actually one of

the rules for multivalued dependency saying

that when you have A determines

B, then you, A multidetermines

B, then you also have A

multi determines rest and we'll

see some rules for multivalued dependencies later.

Let's look quickly at a

modification of our example where

the real world assumptions about the data are different.

So we still have exactly the same relation with the same attributes.

But let's suppose that we don't

want to reveal every hobby to every college.

Maybe we'll decide that we don't

want Stanford to know that

we're a surfer or Berkeley

to know that we're on the speech and debate team.

So if that's the case, then

what multivalued dependencies do we have in this relation?

We actually have none.

And we don't have any functional dependencies either by the way.

And is this a good design?

Well, actually I would argue yes.

In this case, this design

is a good one because

we're not going to have that

multiplicative effect of information.

Every tuple that we have

in the applied relation will

be an independent piece of important information.

Let's look at one more example

before we go on to talk about properties of multivalued dependencies.

I've extended the apply relation

now to not only include colleges

and hobbies but also the

date of application to a

college, and the major or majors that are being applied for.

Let's continue to assume that hobbies are revealed to college selectively.

We don't need to have same

hobbies for each college that a student applies to.

Secondly, lets assume that

we restrict students to apply

only once to each college,

but what I what we mean

by that is just on one day.

A student can still apply

to multiple majors at a

single college and to different majors at different colleges.

Let's also assume that majors

are independent of hobbies, which seems to make sense.

It takes some thinking to come

up with the right functional and

multivalued dependencies to capture these

constraints, but here they are.

The first one when we

say that we reveal hobbies to

college selectively is actually

the absence of a multivalued

dependency on hobbies and colleges.

The second one says as

we apply once to each

college, or on one particular

day to each college, so

that would say that when

we have a particular student

and a particular college that always

going to have the same date,

so any two tuples for

a student and college combination will be on the same date.

The last dependency that

we will have involves the independence

of the majors that are

being applied for and the

hobbies that a student has, so

we'll write that as the

multivalue dependency social security

number, plus college name,

plus date, multidetermines major,

and remember what that's saying

is that major, for a

given student, college, and

date the majors that

they apply for are independent

of what we call the rest,

which in this case is the hobbies.

So, you might take some time to

look at the formal definitions of

functional dependencies, multivalue dependencies, and

maybe write out some sample

data to convince yourself that

these are the dependencies that

are capturing the assumptions that we make about the real world.

Like with functional dependencies we

have a notion of trivial dependency

those that always hold we

also have some rule for multi valued dependencies.

The definition for a trivial

multi valued dependency A multi

determines B is in

this case, that either B

is a subset of A,

or A union B

are all attributes, a multi-value

dependency is non-trivial if that's not the case.

So let's take the look at

why these multi-value dependencies are trivial.

So let's start with the first

case where we have our

attributes A and the rest

and then attributes B are a

subset of A so lets

say that these are attributes B.

So what are definition of multi-valued

dependencies says that when we

have the same values for

A in two tuples, so

here A and A, then

we have every combination of the

B values and the rest,

well obviously we do since

the B's are subsets of the

A's here, the B values

are going to be the same as

well and we clearly have every combination.

For the other case of trivial multi-value dependencies.

We have A and B together

being all attributes of the

relation, so in that

case, there's no rest, so

clearly we have every combination

of values of A and

B and rest, because there's no rest to combine with.

Like with functional dependencies there are

a whole bunch of rules that hold for multi-valued dependencies.

We will just talk about three of

them, and the first one is

the most important and interesting,

and that's the rule that says

if we have a functional dependency

from A to B then we

also have a multi-valued dependency

from A to B. And I'm

gonna go ahead and prove that rule

for you again because this is an important one.

I'm going do this proof using a

template for the relation similar to

the what I did with rules for functional dependencies.

So let's say we have our

A attributes, our B attributes,

and our rest, and what

we need to prove, to prove

the multi-value dependencies, is when

there are tuples T and

U with a certain form,

there exists a tuple V of another form.

So let's fill in some values first for the tuples.

So Let's say that we

have A and A here,

that's what we need for the

equality of the A values.

Then we have B1 and R1,

and we have B2 and

R2, and in order

to prove this multi-value dependency,

I need to prove that there

exists a tuple V that has

the same A value that it

has B1 from tuple T

and R2 from Tuple U,

and what I have in order

to prove that is the fact

that we have a functional dependency from

A to B. Because we

have the functional dependencies and because

T and U have the same A value.

What that tells us is

that B1 equals B2 here.

And so if B1 equals B2

then we know that this value

B1 here is equivalent

to B2 and in order

to prove the existence of this

tuple well we have that tuple

here already and we're done.

So you might check that again,

but what that says is

using the knowledge of a

functional dependency we can prove

that we always have a corresponding

multivalued dependency there are

a couple more rules for

multivalued dependencies that you can

prove for yourself if you're so inclined.

The first one is the intersection

rule, it says that if

we have A multi determines

B and A multi determines

C, then we have

A multi determines B

intersects C. The transitive

rule is slightly different than from exact transitivity.

What it says is if

we have A multi determine B,

and we have B multi determines

C then we have

A multi determined not

C exactly but C minus

B.
And you might work

some examples because it yourself

why we don't have just

A multi determines B and

to subtract the attributes for B, although it's fairly complicated.

So again these rules can

be proven and there are many

other rules of multivalued dependencies

that you can read about in any of the readings provided on our website.

By the way, regarding rules, let's

come back to the fact

that every functional dependency is a multivalued dependency.

So we can use another Venn diagram.

This is different than our previous one.

We can list all of our

multivalued dependencies here and the

functional dependencies are a

subset of those, so what

that tells us is if we

ever have a rule that applies

for multivalued dependencies here, that

will cover the entire Ven diagram

and so that rule will apply for functional dependencies as well.

So every rule for MVDs is

also a rule for functional dependencies.

On the other hand if we

have a rule that applies

for functional dependencies that rule

does not necessarily have to

apply all multivalued dependencies because

it might be specialized just for this portion of the Venn diagram.

So an example of such a rule is the splitting rule.

The splitting rule is a

rule that applies to functional dependencies,

but does not always apply to multivalued dependencies.

And again you could work an example to convince yourself of that fact.

Woo.

So after all that set up

of multivalue dependencies, we're finally

ready to talk about fourth normal form.

The definition of fourth normal

form looks very similar to the one for Boyce-Codd normal form.

Says we take a relation and

we take now a set of

multivalued dependencies for that

relation and the relation

is in fourth normal form if

every non-trivial

multivalued dependency has on

it's left hand side a key.

Remember for functional dependencies it

looks exactly the same except

we have the functional dependency all here instead of multivalued dependencies.

So, let's see exactly what fourth

normal form telling us and why it's a good thing.

So we have A, B, and

rest as usual and let's

suppose that we have a non trivial multivalued dependency.

So that's telling us that

if we have 2 tuples, T

and U and we'll

put in some values for B

and the rest, then we're going

to have the combination of those, as well.

So, that's kind of the proliferation of

tuples we get when we

squish independent facts in the same relation.

But, if the left

side is a key, so if

the A attributes are

a key here then we won't have

those 2 tuples and will

never have to worry about the proliferation.

Now, remember that I said fourth

normal form implies Boyce-Codd Normal Form.

Or if you prefer it in

Venn diagram format, Fourth

Normal Form is stronger than

Boyce-Codd Normal Form and let's see why that's the case.

If we have a fourth

normal form and we want

to show that we're in Boyce-Codd normal

form, then we have to

show that if we have

a functional dependency then

the left hand side A is a key.

That would tell us we're in Boyce-Codd normal form.

Well, if we have a functional

dependency, we had a rule

that tells us we also have

the multivalued dependency and then

since we're in fourth normal form, we get that A as a key.

So again, fourth normal form

implies Boyce-Codd normal form.

Now let's take a look at

the decomposition of algorithm into fourth normal form.

It's extremely similar to the

BCNF decomposition algorithm.

The input is a relation.

A set of functional dependencies

and multi value dependencies and we

need to separate them because

we use the functional dependencies to find keys.

The output is a decomposition

of R into good relations,

in this case fourth normal form,

and it's a good decomposition in

the sense that reassembling the relations gives you back the original.

As with Boyce-Codd normal form

we start by computing keys using

the functional dependencies, and then

we repeat the decomposition process

until all of our relations are in fourth normal

form.

Just as with functional dependencies

in BCNF, we pick a relation

that has a violating dependency, in

this case a multi-value dependency, and

we split the relation based on that dependency.

So we create one relation that

has the attributes of the dependency

and another relation that has

the left-hand side of the dependency and the rest of the attributes.

After that, we need to

compute the functional dependencies for

the decomposed relation and the

multi-value dependencies for it, and then we can compute the keys.

Now finding these multi-value

dependencies is actually a fairly complex process.

Usually it's very intuitive,

but I'm going to refer you

to the readings to read about the algorithm itself.

And in fact, it can be

so complicated in the general

case that some of the readings don't even provide the algorithm.

But again, in general, it's very intuitive.

Our first example is going to be very fast to do.

As you remember, this example has

one multi-value dependency - social

security number determines college name,

multi determines college name -

and it has no keys other than all of the attributes.

So obviously, this is a

violating multi value dependency,

and so we decompose into two

relations, we'll call them A1 and A2.

The first one has the attributes

of the multivalue dependency, the

social security number and

the college name, and the second

one has the left hand

side multivalued dependency as well

as all the remaining attributes, which in this case is the hobby.

These two decomposed relations actually

have no FDs and no

MVDs so in that

case we're definitely in 4th

normal form and we're done

with the decomposition and I think

we can agree that this looks like

a good schema for the data at hand.

Our second example is quite a bit more complicated.

Remember in this example we

have that the social

security number and college name

functionally determine date.

That means we have each student

applies to each college on a specific date.

And secondly, we assume that

majors that were being applied for were independent of hobbies.

So we have social security number,

college name and date

multi determines the major.

And incidentally that would mean it multi determines the hobby too.

Once again, we have no keys

for the relation, except for all attributes.

So we have both a violating

functional dependency in this case

and we have a violating multivalue dependency.

Let's use the multivalue dependency for

our first decomposition step.

So we'll create A1 and A2.

A1 will contain all the attributes of our multivalued dependency.

And then A2 will contain

all the remaining attributes along with

the left hand side of our multivalue dependency.

And that turns out to be all of the attributes except the major.

Now let's look at our

decomposed relations and see

what we have in terms of

functional dependencies and multi-value dependencies for them.

So after the decomposition, we don't

have any more multivalued dependency but

our functional dependency actually applies

to both of the decomposed

relations and we still

don't have a key on the left hand side.

So we need to decompose further based on the first functional dependency.

So let's start by decomposing A1.

We'll turn A1 into A3

and A4, and A3 will have

the functional dependency, all three attributes.

And then A4 will have the

left side of the functional

dependency and the remaining

attributes, which in this case is the major.

So now we're finished with A1

and we have a similar problem with A2.

And so we decompose A2

similarly, although we'll discover

that A3 is the same relation in

the decomposition of A2 as we got with A1.

So we actually only add one

more relation now, which is A5.

That contains the social

security number and the college

name from the left side of

the functional dependency and the

hobby, which is the remaining attribute.

And then we cross out A2.

Now the only functional dependencies are multi-value dependencies we have

left do have a key on the left-hand side.

I'll let you verify that for yourself.

And these three relations are our

final decomposition into 4th normal form.

And I think you will agree

that this is a good design

again for the data at hand.

So let's wrap up this long

unit on on dependencies and normal forms with a quick summary.

If we have a relation RABC, a

functional dependency from A

to B tells us that

when we have the same A values,

we have the same B values,

and the Boyce-Codd normal form tells

us to factor that...those attributes

into their own relation so that

we don't repeat that relationship over and over.

For multi-value dependencies, let's say

we have the relation RABCD,

and if we have

the multi-value dependency A multi

determines B, what that tells

us is that we have every combination

for a given A of B

values and CD values

- we called those rest earlier -

and when we have that multiplicative effect

of combinations, again, we take

the A and B attributes and

we put them in a separate

relation so that we can

separate out those facts from

the independent fact of A and its CD values.

Finally, in the design process,

multi-value dependencies are something

we add to functional dependencies, only they're stronger.

So fourth normal form is

a stronger property than Boyce-Codd normal form.

Now usually this design process

works very well and is

very intuitive for many schemas, I hope for the examples that I gave here.

But there are actually a few

shortcomings to using Boyce-Codd

Normal Form or Fourth Normal Form

and we'll cover those in the next video.