Re: Normalisation

In article <J2gBe.144131$zb3.7653479_at_phobos.telenet-ops.be>, jan.hidders_at_REMOVETHIS.pandora.be says...
> > I guess not. :) I can estimate the memory use of my algorithms, but I
> > haven't felt the need for turing tape before now.
>
> Yeah, that's right, you're an engineer, you don't need to know theory. :-(

Just like scientists don't need to know practise, I guess. What is the complexity of counting sort? Have you heard about the unit cost assumption?

Estimating complexity on Turing machines is one thing; doing it for usable programming languages / systems is slightly different. I know theory, but not *all* theory. Sorry, but we can't all be omniscient.

> >>But time complexity is also different. The unary relation can be
> >>transformed in linear time, but the string transformation requires
> >>O(n.log(n)) steps.
> >
> > Seriously?
>
> Good Lord. So let me get this straight. You are close to getting your
> PhD in computer science but you are not capable of giving correctly the
> time and space complexity in big-Oh notation of even a very simple
> algorithm?

Well, I have the (admittedly small) comfort that apparently, my professor in algorithm theory is as stupid or ignorant as I am. :)

> I hope for your sake and that of your university that you are
> trolling here. Seriously.

I wouldn't need to if you would state your views clearly instead of condescendingly dispensing you wisdom piecemeal and in hints and riddles. It is not a good strategy if you want to clarify your arguments rather than obscure them behind smokescreens, as I am pretty sure you know.

But thank you for your kind concern. I presume it extends to the authors of textbooks in algorithm theory as well.

> >>I'll give you hint. For unnesting the string you need a counter. How
> >>much space will that counter take on the Turing tape.
> >
> > I'm not versed in storing counters on turing tapes, but in my favourite
> > programming languages, that counter takes constant space. Unless the
> > string is *really* long (like over four billion characters)---is that
> > what you are talking about?
>
> Of course. We are talking about the worst-case theoretical complexity
> here.

Sophistry. This is the kind of thing that gives theory a bad name.

Anyway, your notions of 1NF and normalisation is on the one hand based on the actual operators implemented by a particular DBMS (or pragmatical assumptions thereof) and vague optimisation issues, and on the other hand ultra-theoretical nitpicking such as this? And your 1NF definition requires deep understanding of Russel's and Cantor's paradoxes, relational optimisation, domain/set/class theory and Turing machines? YMMV, but I prefer Date's definition.

> Note btw. that when we start talking about DNA data and satellite
> information such sizes are suddenly not so theoretical anymore.

Thank you very much. I never would have though of that---ensuring that my counters are big enough!

-- 
Jon