heavy stuff Celko. I would lie if I would pretend I fully understand
Your answer. I'll let sink it in.
However, I dont store a consistent tree structure. The table at hand
is more a kind of a collection of graphs where I want to find all
possible paths between a given starting point and a given end point
cheers
Juergen
[EMAIL PROTECTED] (--CELKO--) wrote in message
news:<[EMAIL PROTECTED]>...
> >> I've got a table called 'link_t' containing a collection of seller
> -
> buyer relations between two parties. <<
>
> That is not a real linked list, but let's ignore bad terminology. One
> way to do this is with cursors, but they will take time and trend to
> be proprietary.
>
> Anohter way is to build a tree, with the first seller as the root and
> the final buyer as a leaf node.
>
> The usual example of a tree structure in SQL books is called an
> adjacency list model and it looks like this:
>
> CREATE TABLE OrgChart
> (emp CHAR(10) NOT NULL PRIMARY KEY,
> boss CHAR(10) DEFAULT NULL REFERENCES OrgChart(emp),
> salary DECIMAL(6,2) NOT NULL DEFAULT 100.00);
>
> OrgChart
> emp boss salary
> ===
> 'Albert' 'NULL'1000.00
> 'Bert''Albert' 900.00
> 'Chuck' 'Albert' 900.00
> 'Donna' 'Chuck'800.00
> 'Eddie' 'Chuck'700.00
> 'Fred''Chuck'600.00
>
> Another way of representing trees is to show them as nested sets.
> Since SQL is a set oriented language, this is a better model than the
> usual adjacency list approach you see in most text books. Let us
> define a simple OrgChart table like this, ignoring the left (lft) and
> right (rgt) columns for now. This problem is always given with a
> column for the employee and one for his boss in the textbooks. This
> table without the lft and rgt columns is called the adjacency list
> model, after the graph theory technique of the same name; the pairs of
> emps are adjacent to each other.
>
> CREATE TABLE OrgChart
> (emp CHAR(10) NOT NULL PRIMARY KEY,
> lft INTEGER NOT NULL UNIQUE CHECK (lft > 0),
> rgt INTEGER NOT NULL UNIQUE CHECK (rgt > 1),
> CONSTRAINT order_okay CHECK (lft < rgt) );
>
> OrgChart
> emp lft rgt
> ==
> 'Albert' 1 12
> 'Bert'23
> 'Chuck' 4 11
> 'Donna' 56
> 'Eddie' 78
> 'Fred'9 10
>
> The organizational chart would look like this as a directed graph:
>
> Albert (1,12)
> /\
> /\
> Bert (2,3)Chuck (4,11)
>/| \
> / | \
>/| \
> / | \
> Donna (5,6) Eddie (7,8) Fred (9,10)
>
> The first table is denormalized in several ways. We are modeling both
> the OrgChart and the organizational chart in one table. But for the
> sake of saving space, pretend that the names are job titles and that
> we have another table which describes the OrgChart that hold those
> positions.
>
> Another problem with the adjacency list model is that the boss and
> employee columns are the same kind of thing (i.e. names of OrgChart),
> and therefore should be shown in only one column in a normalized
> table. To prove that this is not normalized, assume that "Chuck"
> changes his name to "Charles"; you have to change his name in both
> columns and several places. The defining characteristic of a
> normalized table is that you have one fact, one place, one time.
>
> The final problem is that the adjacency list model does not model
> subordination. Authority flows downhill in a hierarchy, but If I fire
> Chuck, I disconnect all of his subordinates from Albert. There are
> situations (i.e. water pipes) where this is true, but that is not the
> expected situation in this case.
>
> To show a tree as nested sets, replace the emps with ovals, then nest
> subordinate ovals inside each other. The root will be the largest oval
> and will contain every other emp. The leaf emps will be the innermost
> ovals with nothing else inside them and the nesting will show the
> hierarchical relationship. The rgt and lft columns (I cannot use the
> reserved words LEFT and RIGHT in SQL) are what shows the nesting.
>
> If that mental model does not work, then imagine a little worm
> crawling anti-clockwise along the tree. Every time he gets to the left
> or right side of a emp, he numbers it. The worm stops when
