Re: How to normalize this?

Op dinsdag 7 mei 2013 17:34:44 UTC+2 schreef nvitac..._at_gmail.com het volgende:
> On Tuesday, May 7, 2013 5:27:25 PM UTC+2, Erwin wrote:
>
>
>
> > The 1992 paper you pointed to contains/points out the formal foundation for what I informally called "carrying over". Page 2, lemma 1, "pullback rule".
>
> >
>
> > And it implies that you have to look at all the (and only those) relation schemas that are the "target" of an IND, to see if any FDs can be inferred/carried over to the "source" of the IND.
>
> >
>
> > Remaining question might be whether there are any other rules that could also cause "possible inference/carrying over" ... I can certainly see things getting complicated there.
>
>
>
> Definitely. And provably so.
>
>
>
> The “implication problem” for a set of dependencies (of some form) is the problem of proving that a given dependency is a logical consequence of others (e.g., A->C is a logical consequence of A->B and B->C). For FDs, the implication problem can be solved in linear time. For INDs, the implication problem is PSPACE-complete. For FDs and INDs combined, the implication problem is undecidable. Etc…

That seems like a curious result.

Given that all FDs correspond to keys, all keys are database constraints, and all database constraints can be expressed as INDs. Received on Tue May 07 2013 - 19:07:24 CEST