Re: Principle of Orthogonal Design

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 :-)
>
> I'll make some bold statements here anyway, but I can't keep this up.

Your non-bold statements are also be highly appreciated. :-)

Too keep things manageable I'll try to trim the discussion heavily and keep what I think is really essential. So if I snip any of your comments it is not because I don't think they are interesting, but just that at the moment I think they are not at the core of the issue.

> Jan Hidders wrote:
> > mAsterdam wrote:
> >> Jan Hidders wrote:
> >>> ... I wanted to start simple ...
> >> Even though this suggests otherwise, I'll risk assuming
> >> that you understood the coffee analogy, and snipped it
> >> for focus.
> >
> > I *think* I understood it, but I didn't want to get into a debate
> > about it's appropriateness. My position is that in this case we don't
> > really know precisely what this "coffee" thing is anyway. It is a
> > rather vague and informal notion, so we can take the liberty to
> > redefined in a way that seems to most practical for the time being...
>
> Informal as far as most of its nature is concerned, sure.
> Its existence, however, is neither vague nor informal.
> Without it, the coffee-machine loses its purpose.
> It is because of this, that pragmatical redefinitions
> must indeed be temporary and tracked.

Sure, we agree on that. It's just that I think it is sufficient to say at the beginning something like "for this discussion we are going to define 'overlapping meaning' as .." and you want to be more careful and really use another word. As I already said, I'm fine with that, so I don't think more discussion is needed here.

[... very big and painful snip ...]

> DEFINITION: Two relations R and S are said to have dependency-induced
> overlap if there is a dependency that requires that sometimes some
> tuples(1) of R are also in S.
>
> (1) for some definition of tuples that allows restricted
> reshuffling of its values. To do.

The only way to achieve (1) so that it also takes all normal inclusion dependencies into account is to define tuples as something equivalent to bags of values. Such an operation on its internal organs is going to change the relational model beyond recognition. I'm going to strongly insist that we stick to the classical definitions of the named perspective and state in the definition that we are talking about inclusion up to relabeling:

DEFINITION: Two relations R and S are said to have dependency-induced overlap if there is a dependency that requires that sometimes some tuples of R are also in S after renaming the attribute names.

[... another big and painful snip ...]

> >>> ...additional terminology:
> >>> 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} ].

> You include some of those in the problem space
> while leaving some non-trivial dependencies out based on wether
> any of its components is a subset of another component?
>
> Let's see. This is because we are dealing with two relations
> S and R, and we have to make sure that we get all
> dependency-overlap, including the overlap of the trivial JD's.

Yes. The intuition is that if there is a JD the relation is in fact a combination of one or more predicates namely the ones that correspond to each component of the JD. It is for these predicates that we want to check overlap. We want to explicitly include the case where it is actually just one, so we also want to consider the trivial JD [ {a, b, c} ] for the header {a, b, c}.

In that terminology you can also perhaps understand why we only care about proper JDs. Suppose we have JD [ {a, b}, {b, c} ]. Then it follows that the following JD also holds: JD [ {a}, {a, b}, {b, c} ]. I think you'll understand that if the first defines a lossless decomposition, then so does the second for the simple reason that it contains at least as much information as the first. But it is not true that the component {a} also necessarily corresponds to some meaningful predicate. In fact, it probably doesn't. So that is why we want to exclude those.

Having said that, there are actually more JD's that need to be excluded than I initially thought. For example, if the JD [ {a, b}, {b, c} ] holds then also the JD [ {a, c}, {a, b}, {b, c} ] holds. Also here there is not necessarily a meaningful intuitive predicate associated with the component {a, c}. So, at the risk of causing you a serious migraine I'm going to have to tweak my definitions a little.

DEFINITION: A join dependency is said to be minimal if there is not another join dependency with a set of components that is a proper subset of the set of components of the first.

Examples: If JD [ {a, b}, {b, c} ] holds then JD [ {a, b}, {b, c}, {a, c} ] is not minimal. The JD [ {a}, {a, b} ] is never minimal because the trivial JD [ {a, b} ] always holds.

Note that a minimal join dependency is always also a proper join dependency.

The new rule then becomes:

DEFINITION: A schema is said to violate POOD if it contains relations R and S such that a component C of a minimal join dependency of R overlaps in meaning with a component D of a minimal join dependency of S, and either R and S are different, C and D are different, or both.

I just realized by rereading your comments that there might be some confusion on the notion of "component". From now on I'll strictly use the word component for a set of attribute names in a join dependency. So I would like to make the wording in the rule a bit more explicit: (changed parts are emphasized with "_")

DEFINITION: A schema is said to violate POOD if it contains relations R and S such that _the projection of R_ on a component C of a minimal join dependency of R overlaps in meaning with _the projection of S_ on a component D of a minimal join dependency of S, and either R and S are different, C and D are different, or both.

> >> It looks to me that in order to have this problem,
> >> we need to have two relations R and S, where 5NF is
> >> relevant in both, with isomorphy between components
> >> of R and components of S
> >> (which is quite imaginable when integrating databases
> >> in the same business domain, e.g. after a merger, or
> >> with similar but distinct types of complex contracts).
> >> Am I correct thusfar?
> >
> > Roughly. The "5NF is relevant" is a bit misleading. All that is
> > required is that there are proper join dependencies, but these are
> > always present. For example, any relation R(a,b,c) will have always
> > the trivial join dependency JD [{a,b,c}], i.e., the join dependency
> > with one component that contains all attribute names in the header.
> > Although trivial, it is also proper.
>
> Yep, I think I get that.
>
> > So you can violate the rule, even
> > if there is no non-trivial join dependency. A simple example would be
> > as follows: R(a,b) and S(c,d) with ID R[a,b] -> S[c,d], It violates
> > the rule because you also have for S the trivial and proper JD
> > [{c,d}]. So do you think that there is redundancy here that can be
> > removed?
> >
> > Btw. the "with isomorphism between components" can be simplified to
> > "with components of equal size". After all, components are just sets
> > of attribute names, so they have equal size iff they are isomorphic.
>
> Now I'm lost again.

My fault. I thought you were talking about components of JDs.

> >> I don't have much experience with reasoning about 5NF.
> >
> > I actually don't think that is necessary. Whether the relations are in
> > 5NF or not is not really irrelevant. But you understand what lossless
> > decompositions are, no? And I assume you also understand how they are
> > implied by functional dependencies.
>
> Up to BCNF.

Good. Let's for the moment restrict ourselves to just CKs. So say we have a relation R(a,b,c,d) with a CK {a,b}. What are the minimal join dependencies that hold?

And what if we have the CKs {a,b} and {b,c}?

So do you see for which projections we need to check overlap with other projections of other relations?

• Jan Hidders