# Re: What databases have taught me

Date: Mon, 26 Jun 2006 09:53:11 +0200

Message-ID: <lukih5xkzujg.152jv9oy6tkga.dlg_at_40tude.net>

On 25 Jun 2006 20:04:07 -0700, Aloha Kakuikanu wrote:

>> Marshall <marshall.spight_at_gmail.com> wrote: >>> Dmitry A. Kazakov wrote: >>> > >>> > My feeling is that it could turn quite hard for RA. That's why I've >>> > presented it! (:-)) The feeling is based on a trivial observation that the >>> > nodes of the dual graph aren't present in the original graph either as >>> > nodes or as relations. You have to "invent" them (identify the regions). >>> >>> Every query is an "invention" in this sense. Sometimes it is a trivial >>> one, when all one does it pick out some rows and/or columns. But >>> you can also write expressions. Simple example: select a+b as c from R. >> >> I don't know anything about the theoretical limits of relational algebra >> or SQL. However, my intuition is that Dmitry might be right about >> finding a planar embedding. I believe I mentioned earlier that it's >> neither an obvious nor a trivial problem.

*>*

> Excuse me, but the "planar embedding" idea was never in the original

*> challenge. He stated "find the dual of a graph" and that turned out to*

*> be trivial if faces of the planar graph are known.*

An analogy might probably help.

Problem:

Write a compiler

Compiler designer:

Hmm, there seem to be many possible representations of a program in machine code. Please, annotate the source code with a machine code of...

> Yes, "face" is a

*> legitimate concept -- p.13 of Algebraic Graph Theory byGodsil&Royle. If
**> they are not known, then please provide a formal way to define planar
**> embedding. Without planar embedding the problem is ambiguous. The
**> answer for ambiguous problem would be a set of dual graphs, and when
**> answer becomes a set of structures it is usually much harder query.
**> However, his query was "find the dual of a graph" where the "dual" is
**> singular. Therefore, just accept the defeat.
*

It would be sufficient to produce a dual for an arbitrarily chosen embedding. "Arbitrarily" means that your solution is free to take any.

[ As for embedding, as I remotely remember, it has linear algorithms. Not that hard. ]

-- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.deReceived on Mon Jun 26 2006 - 09:53:11 CEST