Re: Checking a relation in BCNF for MVDs

Sebastian wrote:
>On 6 Jan 2003 21:20:25 +0100, you wrote in comp.databases.theory:
>
>Thank you, Jan for your answer. I still have a heap of questions,
>though!

Apologies for the late answer, I was attending a conference so couldn't reply earlier.

>> The trick is usually not to try all these possibilities but to read the
>> description of the table and its contents and try to recognize
>> formulations that indicate multi-valued dependencies.
>
>If I understood it right, if I want to prove that a relation is in
>4NF, I have to show there are no multi-valued dependencies in it
>(again, please correct me if I'm wrong; I'm only beginning to grasp
>those concepts).

Loosely speaking that is correct. However, the details matter here so let me give an exact definition:

  A relation is in 4NF if for all non-trivial MVDs X->>Y the set X is a   superkey.

and as a small reminder:

  An MVD X->>Y is trivial if and only if X + Y contains all attributes of the   relation.

Now as you probably already know MVDs are generalizations of FDs in the sense that every FD X->Y is also an MVD X->>Y (but not vice versa). [Homework: try to prove this.] In some sense you could say that those MVDs are not real MVDs. In that case we can rewrite the definition of 4NF:

  A relation is in 4NF if there are no real non-trivial MVDs.

Note, by the way that the equivalence of the two definitions is easy to see but not completely trivial. [Homework: prove that the first definition implies the second (the easy part) and prove that the second definition implies the first (that's a bit harder)]. Let me know if you need help.

In some texts MVDs are written as X->>Y|Z (with X, Y and Z pair-wise disjoint but together containing all attributes of the relation) and it is required that both Y and Z are non-empty. In that case all MVDs are by definition non-trivial [Homework: prove this] and you can remove this requirement from the definition.

>How can I prove it, though, if I do not take all possible combinations into
>account? Or is there a more elegant way to prove it?

Sometimes you can. For example, in your case you told us that the relation is an all-key relation. That means that there is only one candidate key and, in fact, there is only one superkey. Now take again a look at the first definition of 4NF and of "trivial MVD". ... See what I mean?

>And another question. Say I have the relations
>
>r1(attr1, attr2)
>r2(attr1, attr2, attr3)
>
>The attributes [att1, attr2] form the primary key of r1 and they are a
>foreign key in r2, pointing to r1. r2 is an all-key-relation (as
>described above). Now, I have a FEELING that, since [attr1, attr2] is
>a foreign key, I can treat it as if it was ONE attribute in r2, and
>consequently do not have to check for MVDs in that relation any more.
>How can I formally justify this?

Whether a combination is a foreign key or not is not relevant for normalization because it only deals with what happens inside a relation.

Hope this helped,

• Jan Hidders