# Re: What databases have taught me

Date: Mon, 26 Jun 2006 01:30:37 GMT

Message-ID: <1NGng.2301$pu3.57351_at_ursa-nb00s0.nbnet.nb.ca>

Marshall wrote:

> Chris Smith wrote:

*>
*

>>[...]

*>*

> Thanks for the very informative writeup.

*>*

*> Upon further (modest) analysis of the problem, it appears that finding*

*> regions from edges is a transitive closure problem, so there is,*

*> I will not say "difficulty" but perhaps "challenge." The rest is*

*> more or less trivial.*

*>*

>>- You don't need faces; just a (unordered) nodes and edges.

*>*

*>*

> Are you sure?

*>*

*> Consider a square, with four points, top-left, top-right, bottom-left,*

*> bottom-right. Now add a fifth edge, from top-right to bottom-left.*

*>*

*> If this edge goes through the interior of the square, that is a*

*> different set of regions than if it goes around the outside of*

*> the square.*

Marshall, I direct your attention to _Written in Anger_ EDW 696.

Suppose one labelled each of the above nodes A, B, C, D respectively. One has the following edges: AB, AC, BD, CD and finally BC.

There is a region that is adjacent to AB, AC, BD and CD that is not adjacent to BC regardless whether one draws BC through the middle of the square or around the square. Lets call that region ABCD.

Likewise, there is a region that is adjacent to AB, AC and BC that is not adjacent to BD or CD. Let's call that region ABC. Similarly, there is a region adjacent to BD, CD and BC that is not adjacent to AB or AC. Let's call that region BCD.

If you draw BC through the square, then ABCD is the outer region with ABC and BCD on either side of BC inside the square.

If you draw BC below the square, then ABC is the outer region, BCD lies between BC and the square, while ABCD is the interior of the square.

If you draw BC above the square, then BCD is the outer region, ABC lies between BC and the square, while again ABCD is the interior of the square.

However, in all the above cases, we have the same regions: ABCD, ABC and BCD. Of course, what I called a square above could be drawn as any arbitrary quadrilateral without changing anything.

Interestingly, the above suggests to me an excellent justification for relation-valued attributes as candidate keys for an edge relation and a region relation except that it would not necessarily work for the dual due to the multiplicity of edges between nodes. Hmmmm.

But then again, the logical identity for what we draw as an edge in a dual is really two regions and an edge, and one could make all three attributes relation-valued attributes.

Interesting. Received on Mon Jun 26 2006 - 03:30:37 CEST