# Re: What databases have taught me

Date: 25 Jun 2006 20:04:07 -0700

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

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. 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. Received on Mon Jun 26 2006 - 05:04:07 CEST