Path: news.netfront.net!news.glorb.com!postnews.google.com!v4g2000hsf.googlegroups.com!not-for-mail
From: Jan Hidders
Newsgroups: comp.databases.theory
Subject: Re: Principle of Orthogonal Design
Date: Sun, 27 Jan 2008 12:51:29 -0800 (PST)
Organization: http://groups.google.com
Lines: 89
Message-ID: <21b464e3-4d21-4a4c-89e1-eaa71827aa6c@v4g2000hsf.googlegroups.com>
References:
<2e13fa2d-c7fd-4f5d-ab5d-55ead0e3ae07@x69g2000hsx.googlegroups.com>
<4795bade$0$85795$e4fe514c@news.xs4all.nl>
<47963c0a$0$85784$e4fe514c@news.xs4all.nl> <8e5fa53e-5342-4429-a231-90370e80eb74@e23g2000prf.googlegroups.com>
<479755b9$0$85777$e4fe514c@news.xs4all.nl>
<47999a9d$0$85779$e4fe514c@news.xs4all.nl> <8e2c55d4-2a37-4ce8-9f49-37d4617ebe07@x69g2000hsx.googlegroups.com>
<479b9fbd$0$85794$e4fe514c@news.xs4all.nl>
NNTP-Posting-Host: 84.192.48.81
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1201467090 7067 127.0.0.1 (27 Jan 2008 20:51:30 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Sun, 27 Jan 2008 20:51:30 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: v4g2000hsf.googlegroups.com; posting-host=84.192.48.81;
posting-account=i7Ak-QoAAABlJ1qBkr1tS-dBPg_3Ujft
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X; en-us)
AppleWebKit/523.10.6 (KHTML, like Gecko) Version/3.0.4 Safari/523.10.6,gzip(gfe),gzip(gfe)
Xref: news.netfront.net comp.databases.theory:47245
On 27 jan, 13:49, "David Cressey" wrote:
> "Jan Hidders" wrote in message
>
> news:c4a59c20-5686-4f4a-aa43-512cdee1df64@d70g2000hsb.googlegroups.com...
>
>
>
> > mAsterdam schreef:
> > > This is all way over my head. Jan, you may be used to
> > > sailing these waters; I am not. I think it is interesting,
> > > but very time-consuming.
> > > Am I talking rubbish? I try not to, but I don't know - nobody
> > > else chimes in. You keep replying, but hey, you are a nice guy :-)
>
> It's even further over my head.
>
>
>
> > > >>> DEFINITION: A join dependency is said to be a proper if it does no=
t
> > > >>> hold that any of its components is a subset of another component.
> > > >> Proper is a nicer than non-trivial.
> > > > Note that it's semantically different. Not all proper join
> > > > dependencies are non-trivial, and not all non-trivial join
> > > > dependencies are proper.
>
> > > Thanks, I have to read more carefully.
>
> > > Trivial dependencies are the ones implied by the
> > > candidate keys.
>
> > Not precisely. Trivial dependencies are those that hold in any schema.
> > For example the FK a,b -> a is always true as long as you have
> > attributes 'a' and 'b' in the header. Another example is the JD
> > [ {a,b}, {b,c}, {a,b,c} ] if the attributes in the header are {a,b,c}.
> > This is always a lossless decomposition, but also a very redundant
> > one. Another is the JD [ {a,b,c} ].
>
> I really need to understand the word "trivial" =A0as used above in a more
> careful manner than I do.
Ok. I'll try to give it a shot.
So the general meaning is that a dependency is trivial if it holds in
any schema in which it makes sense (i.e. that defines the used
relation and attribute names) and independent of which constraints /
dependencies have been specified.
For functional dependencies, for example, these are exactly all FDs X -
> Y such that Y is a subset of X. So FD a,b -> b is such an FD and FD
a -> b is not. So the trivial FDs always hold, and the non-trivial
ones only hold if they have been explicitly specified or if they
follow from constraints that have been explicitly specified. The
intuition behind the term "trivial" is that if you write down a
complete list of the dependencies that hold, then you can always write
down the trivial ones first, because these will hold, no matter what
the specific situation is.
This notion has been generalized for all kinds of dependencies. For
multi-value dependencies (MVDs) this characterization is a bit more
complicated. An MVD X ->> Y is trivial iff Y is a subset of X or the
union of X and Y is the header of the relation. So for R(a,b,c) the
MVD a ->> b,c always holds.
For join dependencies it actually gets easier again. We know that a JD
[ X1, .. , Xn ] is trivial iff one of the components Xi is the header
of the relation. Clearly if one of the components of your
decomposition is the whole original relation, the decomposition is
going to be lossless.
> So I need to understand "trivial dependencies", =A0in a really tight fashi=
on.
> My loose understanding of one form of trivial dependence is that a compone=
nt
> of a composite key is trivially dependent on that key. =A0In this case,
> "trivial" means, =A0to me, =A0that the dependency provides no additonal
> information about anything. =A0The sort of thing that, in common parlance,=
> would draw the response, =A0"well, duh!"
Yes, that intuition is roughly correct. And you can generalize this
even beyond the types of dependencies I mentioned. As usually defined,
all dependencies are a specific syntactical subclass of statements /
formulas in first order logic. All trivial dependencies are then
defined as the tautologies within that subclass.
Does that shed some light?
-- Jan Hidders