Re: What databases have taught me

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