Oracle FAQ | Your Portal to the Oracle Knowledge Grid |
Home -> Community -> Usenet -> comp.databases.theory -> Re: Normalisation
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?
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.
That is correct.
>>As any good database researcher
>>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?
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