# Re: What databases have taught me

Date: 25 Jun 2006 22:59:36 -0700

Message-ID: <1151301576.905309.194110_at_b68g2000cwa.googlegroups.com>

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