Re: What databases have taught me

Dmitry A. Kazakov wrote:
> On 24 Jun 2006 10:36:00 -0700, Marshall wrote:
>
> > Dmitry A. Kazakov wrote:
> >>
> >> And, guys, what about presenting a query statement for building a dual
> >> graph?
> >
> > I'm not at all familiar with graph theory. I couldn't make sense out of
> > this:
> >
> > http://mathworld.wolfram.com/DualGraph.html
> >
> > Can you explain it better?
>
> See:
>
> http://en.wikipedia.org/wiki/Planar_graph
> http://en.wikipedia.org/wiki/Dual_graph

Neither of these provides an unambiguous specification of the problem.

> It is a quite intuitive thing. I was born in St.Petersburg, but you can
> consider Venice for the same purpose. The graph of channels is the dual of
> one of the bridges. Regions are the islands + one for mainland.

So, if all we are doing is converting bridges in to channels, how about INSERT INTO Channels (SELECT * FROM Bridges)

But it would probably be better to provide an unambiguous definition of the problem. Perhaps a minimal example as well?

> > Is there some known theoretical complexity of this problem? (In other
> > words, are you just setting me up? :-)
>
> It is not hard.

Reading about the history of the analysis of the problem, coupled with the fact that I can't seem to find a decent explanation of it, woud seem to contradict this. Perhaps it is only not hard after one has already learned about it.

> The problem specifically for RA lies elsewhere.

Ah, you do have something up your sleeve. How about you just come clean with it and we talk about it?

You know, the c.d.t. people are well aware of issue like transitive closure and Turing completeness, and how the traditional and various modern RAs stack up in comparison. We could discuss it if you wish.

Marshall Received on Sat Jun 24 2006 - 23:39:13 CEST