Re: How to normalize this?
Date: Tue, 7 May 2013 08:34:44 -0700 (PDT)
Message-ID: <33121072-c704-4692-945a-324a35e5620f_at_googlegroups.com>
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".
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…
Received on Tue May 07 2013 - 17:34:44 CEST
>
> 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.