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