Re: The "standard" way to get to 3NF
From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Sat, 10 Apr 2004 08:41:45 GMT
Message-ID: <drOdc.66186$337.4619398_at_phobos.telenet-ops.be>
>>Jan Hidders wrote:
>>
>>>Jan Hidders wrote:
>>>
>>>>[...] The usual algorithm that gets you to 3NF in one step (the one
>>>>using the minimal cover) splits as little as possible. See for example
>>>>sheet 46 on:
>>>>
>>>> http://cs.ulb.ac.be/cours/info364/relnormnotes.pdf
>>>
>>>Did anyone notice that this algorithm is actually not correct? Take the
>>>following example of a relation R(A,B,C,D,E) with the set of FDs:
>>>
>>> { AB->C, AB->D, BC->D }
>>
>>You've lost E - was that a mistake in the FD's or in the example relation?
>>
>>
>>>It is clear that the relation ABCD is not in 3NF. Since the set of FDs
>>>it is already a minimal cover the resulting decomposition is:
>>>
>>> { ABCD, BCD }
>>>
>>>But that gives us our old relation back (plus a projection) so this is
>>>definitely not in 3NF.
>>>
>>>The strange thing is that this algorithm appears as such in the Elmasri
>>>and Navathe and also in Date (but not Ullman). Surely these two major
>>>textbooks would not get the most fundamental algorithm in normalization
>>>theory wrong? Or would they? Reminds me a little of the
>>>misrepresentation of 5NF in many textbooks.
>
Date: Sat, 10 Apr 2004 08:41:45 GMT
Message-ID: <drOdc.66186$337.4619398_at_phobos.telenet-ops.be>
Bert Blink wrote:
> On Sat, 10 Apr 2004 04:31:06 GMT, Jonathan Leffler > <jleffler_at_earthlink.net> wrote:
>>Jan Hidders wrote:
>>
>>>Jan Hidders wrote:
>>>
>>>>[...] The usual algorithm that gets you to 3NF in one step (the one
>>>>using the minimal cover) splits as little as possible. See for example
>>>>sheet 46 on:
>>>>
>>>> http://cs.ulb.ac.be/cours/info364/relnormnotes.pdf
>>>
>>>Did anyone notice that this algorithm is actually not correct? Take the
>>>following example of a relation R(A,B,C,D,E) with the set of FDs:
>>>
>>> { AB->C, AB->D, BC->D }
>>
>>You've lost E - was that a mistake in the FD's or in the example relation?
>>
>>
>>>It is clear that the relation ABCD is not in 3NF. Since the set of FDs
>>>it is already a minimal cover the resulting decomposition is:
>>>
>>> { ABCD, BCD }
>>>
>>>But that gives us our old relation back (plus a projection) so this is
>>>definitely not in 3NF.
>>>
>>>The strange thing is that this algorithm appears as such in the Elmasri
>>>and Navathe and also in Date (but not Ullman). Surely these two major
>>>textbooks would not get the most fundamental algorithm in normalization
>>>theory wrong? Or would they? Reminds me a little of the
>>>misrepresentation of 5NF in many textbooks.
>
> See p321Table 10.1 in E&N 4th Edition & elswhere in the text. > > It specifically mentions the need to preserve the Candidate Key (CK) > as a separate relation in particular when the CK is not on the LHS of > any FD in the minimal cover. > > So you need an extra relation r3(A, B, E).
The E shouldn't have been there. But even if it is, that doesn't solve the problem. The decomposition { ABCD, BCD, ABE } is also not in 3NF.
- Jan Hidders