Re: Normalisation

From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Sun, 10 Jul 2005 09:17:34 GMT
Message-ID: <OI5Ae.141460$zX6.7309433@phobos.telenet-ops.be>

Jon Heggland wrote:
> In article <xfCze.140548$uH4.7139418_at_phobos.telenet-ops.be>,
> jan.hidders_at_REMOVETHIS.pandora.be says...
>

>>>>>A set can be transformed into a unary relation with a simple operation. 
>>>>>A string can be transformed into a binary relation (integer and 
>>>>>character) with a simple operation.
>>>>
>>>>That requires logarithmic space, and not constant space as my 
>>>>transformation. So it is arguably more complex.
>>>
>>>Please elaborate. Assuming for the sake of the argument that you are 
>>>right, so what?
>>
>>It indicates that in one case there is a larger similarity than in the 
>>other because you meed more work to do the transformation. You're not 
>>asking me to explain the stated complexity classes of the operations, 
>>are you?

>
> Well, yes, I actually am. Sorry if it is trivial, but I don't see the
> difference. Or the logarithm.

Come on, Jon. How much tape does the Turing machine need that computes this transformation if n is the size of the input?

> Anyway, that is an implementation matter. The transformation at the
> logical level is trivial.

That it requires logarithmic space is implementation independant and an objective measure of its complexity.

>>Usually it is relatively well-known which operations are possible in a 
>>DBMS and which aren't. That makes it in practice actually a quite stable 
>>notion even though it is a relative one.

>
> Fair enough. It is the odd one out of the normal forms, though, since
> the others aren't relative in that way. And it has the unfortunate
> consequence that higher normal forms don't imply 1NF, if I understand
> you correctly.

That is correct.

>>As any good database researcher

>
> How do you know I'm any good? :)
>

>>you probably know 
>>and understand the notion of "genericity". Just as a test to see if you 
>>really understood it, can you tell me the relationship between this 
>>notion and the notion of 1NF I defined?

>
> It would be easier if you would care to restate your 1NF definition,
> including (if necessary) the definition of atomicity (and other non-
> trivial terms), but I'll have a go. :)
>
> "Relation" is a generic (is "generic type" bad form?), and allowing
> operators that manipulate generics breaks atomicity and leads to
> paradoxes and optimisation problems. Except the classic relational
> operator; those are okay.

Hm, that was actually not the notion of genericity I meant. What I meant is the notion that is associated with query languages and mentioned for example in page 3 paragraph 3 of
http://citeseer.ist.psu.edu/vandenbussche01applications.html

Jan Hidders

Received on Sun Jul 10 2005 - 04:17:34 CDT