Oracle FAQ | Your Portal to the Oracle Knowledge Grid |
Home -> Community -> Usenet -> comp.databases.theory -> 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!
-- JonReceived on Thu Jul 14 2005 - 08:19:34 CDT