Re: What databases have taught me

From: Dmitry A. Kazakov <>
Date: Mon, 26 Jun 2006 09:53:11 +0200
Message-ID: <>

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

> Chris Smith wrote:

>> Marshall <> 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.


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. ]

Dmitry A. Kazakov
Received on Mon Jun 26 2006 - 09:53:11 CEST

Original text of this message