Re: Principle of Orthogonal Design

From: Jan Hidders <>
Date: Sun, 27 Jan 2008 12:51:29 -0800 (PST)
Message-ID: <>

On 27 jan, 13:49, "David Cressey" <> wrote:
> "Jan Hidders" <> wrote in message
> > 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 not
> > > >>> 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"  as 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",  in a really tight fashion.
> My loose understanding of one form of trivial dependence is that a component
> of a composite key is trivially dependent on that key.  In this case,
> "trivial" means,  to me,  that the dependency provides no additonal
> information about anything.  The sort of thing that, in common parlance,
> would draw the response,  "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
Received on Sun Jan 27 2008 - 21:51:29 CET

Original text of this message