Re: Multi-Valued Dependencies
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:
- 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.
- 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.
- 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.htmReceived on Sun Mar 26 2000 - 00:00:00 CET