Re: What databases have taught me

From: Dmitry A. Kazakov <mailbox_at_dmitry-kazakov.de>
Date: Sat, 24 Jun 2006 21:04:49 +0200
Message-ID: <yrnog7qldqyp.1kfntxml10hzj.dlg@40tude.net>

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

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.

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

It is not hard. The problem specifically for RA lies elsewhere. The dual graph is not a subgraph or a product of some relational operation on the graph. You cannot "select" it from something you already have. You need to construct it from scratch, so to say. It is like power set. The constructed object, of course, must have the chosen representation of a graph in RA. A symmetric binary relation is an obvious candidate, plus planarity constraint. Euler's formula is good for that. You should start with queries identifying regions, these will give you new nodes. Then for each arc xGy (two arcs actually, but the relation is symmetric xGy=yGx) of the original graph you create one in the new graph.

(I can't tell if dual is "algebraic" in RA, but it is in OO (:-))

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Received on Sat Jun 24 2006 - 14:04:49 CDT