Oracle FAQ Your Portal to the Oracle Knowledge Grid

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

Re: What databases have taught me

From: mAsterdam <>
Date: Sun, 25 Jun 2006 02:54:38 +0200
Message-ID: <449dde52$0$31639$>

Marshall wrote:
> Dmitry A. Kazakov wrote:

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


> 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?

How about:
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
> one has already learned about it.
>>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