Graph Representations

SQL Apprentice Question
have a problem that's twisting my mind up. The summary of the problem is
that I have table of organizations, each of which can function in one of two
roles at any given time - call them Role A and role B. These organizations
will have relationships between them (I imagine it programatically as a
directed graph or linked list)...possibly to an infinite degree. For
example - representing the organizations by numerals (maybe their primary
key in the table) and the roles as defined above - we might have the
following:


(org 1 in role A -> org 2 in role B -> org 3 in role A...)


1A->2B->3A->4B->5A
|->6A


(org 2 in role A -> org 3 in role B...)


2A->3B->5A
|->2B->4A
|->6A
|->7A


As you can see, each organization will be a "root" node, but then the path
can take nearly progression to and from the other organizations, having an
infinite number of traditional "edges" in a graph. The graph would
ultimately end at one or more "leaf" nodes (as represented above). This
graph represents the relationships between the associated organizations.
There is no mutual exclusion between the paths: in other words, multiple
organizations may have a relationship with 5A (org 5 in role A) - as shown
above.


How in the world do I represent these relationships in a database structure?
Please help.




Celko Answers
Try a modifed nested sets model. Nodes have a compound key:

CREATE TABLE Nodes
(node_id INTEGER NOT NULL
CHECK(node_id > 0),
node_type CHAR(1) NOT NULL
CHECK(node_type IN ('A', 'B'),
PRIMARY KEY (node_id, node_type),
etc.);


The forest of various arrangements of nodes has to identify each tree
in that forest:


CREATE TABLE Forest
(tree_id INTEGER NOT NULL,
node_id INTEGER NOT NULL,
node_type CHAR(1) NOT NULL,
REFERENCES Nodes (node_id, node_type)
ON UPDATE CASCADE
ON DELETE CASCADE,
PRIMARY KEY (tree_id, node_id)
lft INTEGER NOT NULL,
rgt INTEGER NOT NULL,
UNIQUE (tree_id, lft),
etc.
);