Re: What databases have taught me

From: Dmitry A. Kazakov <mailbox_at_dmitry-kazakov.de>
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:

> Chris Smith 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.de
Received on Mon Jun 26 2006 - 09:53:11 CEST

Original text of this message