Re: SQL and Table Structure for Graph Traversals

On Wed, 11 Feb 1998 01:14:03 -0600, "Kenneth Murphy" <ukemurp_at_worldnet.att.net> wrote:

>Hello.
>
>In the database application I am currently working on, I am needing to do
>traversals of data that can be modeled as a 4 level directed graph with each
>child node potentially having more than one parent node.
>
>Each level represents a geography depth of
>1 = State
>2 = Region within a state
>3 = County within a region
>4 = Community within a region
>
>What is the best way to represent this in a relational model and is there a
>way to write a single SQL statement that can retrieve all the records
>assigned to an arbitrary node, and both its parent nodes and child nodes at
>all depths.
>
>Does anyone know of a book that discusses this?
>
>Any suggestions would be appreciated.
>
>Sincerely,
>Kenneth Murphy
>University of Missouri - Columbia
>Office of Social & Economic Data Analysis
>kenneth_at_oseda.missouri.edu
>
>

According to the entity-relationship model, I would define things the following way:

ENTITIES

. State
. Region
. Country
. Community

RELATIONSHIPS

Define relationships between each of the previous entities. According to what you said, some entities may belong to various parents. Thus, let's make it as generic as possible:

M-to-N relationship between State and Region
M-to-N relationship between Region and Country
M-to-N relationship between Country and Community

CONVERTING FROM ENTITY-RELATIONSHIP MODEL TO TABLES

Each entity is converted to a table.

M-to-N relationships can't be solved through implementation of a foreign-key in the child table - you must create a separate table for that purpose.

You get the following tables:

STATE
REGION
COUNTRY
COMMUNITY STATE_REGION
REGION_COUNTRY
COUNTRY_COMMUNITY Each entity-derived table must have its own primary key.

The relationship-derived tables (STATE_REGION, for ex.) contain just 2 fields - foreign keys to their corresponding tables (STATE, REGION, for ex.).

After setting all of this, you can perform traversals starting at any point of the graph, using the SELECT statement with the options START WITH and CONNECT BY, as documented in the SQL reference (be sure you read it!).

Good luck,

Nuno Guerreiro Received on Wed Feb 11 1998 - 00:00:00 CST