Oracle FAQ | Your Portal to the Oracle Knowledge Grid |
Home -> Community -> Usenet -> comp.databases.theory -> Re: What databases have taught me
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?
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.deReceived on Sat Jun 24 2006 - 14:04:49 CDT