# Re: Normalisation

Date: Thu, 14 Jul 2005 15:19:34 +0200

Message-ID: <MPG.1d4084bc99c7ce589896f9_at_news.ntnu.no>

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!

-- JonReceived on Thu Jul 14 2005 - 15:19:34 CEST