Oracle FAQ Your Portal to the Oracle Knowledge Grid
 HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US

Home -> Community -> Usenet -> comp.databases.theory -> Re: What databases have taught me

# Re: What databases have taught me

From: mAsterdam <mAsterdam_at_vrijdag.org>
Date: Sun, 25 Jun 2006 02:54:38 +0200
Message-ID: <449dde52\$0\$31639\$e4fe514c@news.xs4all.nl>

Marshall wrote:
> Dmitry A. Kazakov wrote:

```>> Marshall wrote:
>>>Dmitry A. Kazakov wrote:
>>>
>>>>And, guys, what about presenting a query statement for building a dual
>>>>graph?
```

[snip]
```>>>http://mathworld.wolfram.com/DualGraph.html
>>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?

Given A planar graph G, compute it's dual graph G' (this takes out the real hard part, BTW: given a graph compute if it's planar)

If it is still unclear: just say what is the problem, I'll do my best. (It's in my 1974 graph syllabus, and very rusty :-)

```>>>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
>
```>>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.
```--
"The person who says it cannot be done
should not interrupt the person doing it."
Chinese Proverb.
```
Received on Sat Jun 24 2006 - 19:54:38 CDT

Original text of this message

 HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US