Home -> Usenet -> comp.databases.theory -> Re: How to normalize this?

Re: How to normalize this?

From: <nvitacolonna_at_gmail.com>
Date: Wed, 8 May 2013 14:58:01 -0700 (PDT)
Message-ID: <9864906b-910c-4890-b9d0-f3d1ba7af8bd_at_googlegroups.com> 






On Wednesday, May 8, 2013 12:30:45 PM UTC+2, Erwin wrote:


> Op dinsdag 7 mei 2013 16:50:03 UTC+2 schreef nvitac..._at_gmail.com het volgende:





> "And, in the general case, there is no algorithm that is guaranteed to give you an answer!"


> 

> In this example, it seemed to me like the "pullback rule" was sufficient to find the answer.  Applying the pullback rule to a finite set of explicitly stated INDs, their sources and their targets, certainly seems like a feasible piece of algorithm.

> 

> So what is "the general case" ?




The general case is when you allow a database schema to have FDs together with an arbitrary set of INDs, in particular INDs that may form cycles. The pullback rule is not enough to infer all the consequences. In fact, there is no complete recursively enumerable set of axioms for finite implication (that is, something like Armstrong axioms for FDs). For all the details, see:


J. C. Mitchell. The implication problem for functional and inclusion dependencies. Information and Control, 56:154–173, 1983.
M. A. Casanova, R. Fagin, and C. H. Papadimitriou. Inclusion dependencies and their interaction with functional dependencies. Journal of Computer and System Sciences, 28:29–59, 1984.
A. K. Chandra and M. Y. Vardi. The implication problem for functional and inclusion dependencies is undecidable. SIAM J. Comput., 14(3):671–677, Aug. 1985.





I believe that these negative results have basically discouraged research on normal forms including INDs, although, for many subclasses, problems become decidable. Ling and Goh's approach, if my memory assists me, was to define a normal form based only on those dependencies derivable with the pullback rule (so, using an incomplete inference system); Mannila and Räihä's approach, later studied by Levene and Millist, was to impose that FDs and INDs do not interact (so that the implication problems for FDs and INDs could be treated independently).



Nicola
Received on Wed May 08 2013 - 23:58:01 CEST












Original text of this message