# Re: What databases have taught me

Date: Sun, 25 Jun 2006 10:44:48 +0200

Message-ID: <gsarqokfgi42.1gs0nk8bgx9ps.dlg_at_40tude.net>

On 24 Jun 2006 14:39:13 -0700, Marshall wrote:

> Dmitry A. Kazakov wrote:

>> http://en.wikipedia.org/wiki/Planar_graph >> http://en.wikipedia.org/wiki/Dual_graph

*>*

> Neither of these provides an unambiguous specification of

*> the problem.*

See the nice post by Chris Smith.

>> 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)*

That could be the final step. The actual problem is the end points of the arcs. Which depends on the graph representation you choose. If graph were represented "naturally" as a relation, then each arc would be a pair tuples (the relation is symmetric).

>> The problem specifically for RA lies elsewhere.

*>*

> Ah, you do have something up your sleeve.

Look at me, I wear a T-shirt! (:-))

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

As I said, I don't know if it is "algebraic" in RA. It must definitively be Turing complete. Ask Chris Smith, he seems to know far more on the topic than me.

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

-- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.deReceived on Sun Jun 25 2006 - 10:44:48 CEST