Re: Multi-Valued Dependencies

From: Randy Yates <yates_at_207.87.184.178>
Date: 2000/03/26
Message-ID: <38DD844F.A59CCF42_at_207.87.184.178>


Hello Harry,

I really appreciate having someone to discuss this issue with. Thank you for taking the time to understand my questions.

Due to a combination of lack of time to ponder this issue and the requirement for me to think really hard about it, it has taken me a few days to respond. Well, finally, here is my response:

Harry Chomsky wrote:
>
> Randy Yates wrote in message <38D923E5.B3220C33_at_rtp.ericsson.com>...
> >Harry Chomsky wrote:
> >> In fact, in *any* relation with two or more attributes, you can partition
> >> the attributes into subsets X and Y and verify that X ->-> Y. This fact
 is
> >> not very interesting though. When designers talk about MVDs, they
 generally
> >> mean non-trivial ones.
> >
> >You seem to be using the term trivial for two different reasons:
> >
> > Trivial A: An MVD is trivial if the subset C is null
>
> "Trivial A" is what I meant.

OK.

> > Trivial B: An MVD is trivial if the set of B values
> > matching a given (A value, C value) pair is of
> > cardinality "1" (i.e., the set contains only one value).
> >
> >The case defined by trivial B is the only way I can reconcile your
> >statement that *any* relation with two or more attributes and
> >be considered MVDs, otherwise, e.g., the relation
> >
> > COURSE TEACHER
> > Physics Green
> > Math Green,
> >
> >where COURSE is a primary key, would not be considered an MVD.
>
> In this case, still, we have the trivial (in sense A) MVD COURSE ->->
> TEACHER. That is, the set of TEACHER values matching any given COURSE value
> depends only on the COURSE value. It sounds stupid to say it that way
> because it's so obvious -- hence "trivial" :-).

OK, there are several different issues here that are intertwining:

  1. I agree with you that, in my example above, COURSE ->-> TEACHER, according to Date's definition of MVD, which did not exclude trivial A or trivial B types of MVDs.
  2. I disagree that, if you limit MVD to the non-trivial B types, that my example above contains MVDs. However, this was not Date's original definition, i.e., he had no restriction on the cardinality of the multi-dependent set of attribute values.
  3. I now agree with your blanket statement that *any* relation with two or more attributes can be partitioned into attribute sets A and B such that A ->-> B IF you do not restrict the definition of MVD to exclude trivial B types (indeed Date did not make any such exclusion). This is a direct consequence of the fact that a) any relation with two or more attributes can be partitioned into attribute sets A and B such that A -> B, and b) FD -> MVD (the symbol "->" here is used to mean the logical "imply" operation, i.e., "if FD, then MVD").

> >I really don't mean to be hung up on this point - it really
> >seems to be important in being able to proceed to the
> >definition of fourth normal form. The problem is, I'm not
> >sure which characteristic of relvars the concept of MVD
> >is meant to identify: the characteristic in which two or
> >more sets of attributes are independent of one another but dependent
> >on some other set of attributes, or the characteristic in
> >which a single set of attributes contains a "set" of values that
> >are, as a set, dependent on another set of attributes (i.e.,
> >a "relation-valued" attribute).
>
> The former. As far as I can tell, the latter characteristic is satisfied by
> every relation. If X is any subset of the attributes and Y is its
> complement, then for any value of X, there is a set of corresponding values
> of Y. Collectively, these sets define the relation. To put it a different
> way, you could define a new relation with the attributes from X and a new
> attribute A, where A is defined on the domain of "sets of tuples on the
> attributes from Y". In the new relation, X is a (super)key, hence X -> A.
> The new relation contains the same information as the old one -- either can
> be reconstructed from the other.
>
> For example, if X = { COURSE } and Y = { TEACHER }, the new relation would
> contain a row for each course, in which the A value would be the set of
> teachers of that course. This works whether or not the FD COURSE -> TEACHER
> is satisfied in the original relation.

I agree, IF we do not exclude relations which have only one value in the relation-valued attribute. Otherwise, e.g., a two-attribute relvar in BCNF would not be included.

OK, here's the real issue for me: Date's definition of MVD does not match the characteristic I think he is after. That characteristic is the situation in which a relvar contains non-trivial B relation-valued attributes. This is supported by Date's statement just prior to his definition of MVD: "Intuitively, what this means is that, although a course does not have a *single* corresponding teacher---i.e., the *functional* dependence COURSE -> TEACHER does *not* hold---nevertheless, each course does have a well-defined *set* of corresponding teachers."

Given that the distinguishing feature is that of a *set* of values of attribute set B that depend on another attribute set A, I see no reason to to split the relvar into *three* sets A, B, and C in the MVD definition. Herein lies my confusion. Even though I can agree with you on many of your points on MVDs *as Date defines them*, I don't see how Date's definition of MVD gets us where we really want to go.

> Date actually gives examples like
> this in his "Third Manifesto".

Is that another book of his?

> I hope this sheds light rather than creating more confusion!

Well, we're getting there, but we haven't arrived!

-- 
% Randy Yates                   % "Midnight, on the water... 
%% DIGITAL SOUND LABS           %  I saw...  the ocean's daughter." 
%%% Digital Audio Sig. Proc.    % 'Can't Get It Out Of My Head' 
%%%% <yates_at_ieee.org>           % *El Dorado*, Electric Light Orchestra
http://207.87.184.178/index.htm
Received on Sun Mar 26 2000 - 00:00:00 CET

Original text of this message