Re: What databases have taught me

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

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.

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.

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