Re: What databases have taught me

Chris Smith wrote:
> Aloha Kakuikanu <aloha.kakuikanu_at_yahoo.com> wrote:
> > However, his query was "find the dual of a graph" where
> > the "dual" is singular. Therefore, just accept the
> > defeat.
>
> Umm, alrighty then. Someone got up on the wrong side of
> the bed.

Does he sleep? :-)

> I was just providing information ... that finding a plan
> embedding, while it is possible in linear time, is
> decidedly not a trivial problem. It's at least
> sufficiently non-trivial that even though I understand the
> general idea of Bob Tarjan's algorithm, I don't think I
> could actually do it in any language, SQL included,
> without a good bit of research. More research than I'd do
> just because of a newsgroup post. And I seem to know as
> much about the problem as most people here.

I couldn't agree with you more on all points. I can't even think of a naive (even exponential) algorithm that is what I would call "simple". You know of any super-naive slow as hell but simple algorithms? How about a randomized one?

We never covered this problem in any of the algorithms or computation courses I took. If one wanted to compare network and relational implementations I can think of /many/ more commonly useful algorithms: minimum spanning tree, shortest path, all-pairs shortest path, isomorphism etc.

Hehe ... it all goes back to Dimitry's seemingly innocent little challenge: "And, guys, what about presenting a query statement for building a dual graph?" In hindsight it seems to be a sneak attack. Or maybe DAK had a deeper purpose and it trying to point out something fundamental. However, I'm more inclined to agree with you that finding the dual would be a pain in any language.

• Keith -- Fraud 6