Re: Ordered result set with path enumeration

Dieter Nöth <dnoeth_at_gmx.de> wrote in message news:<bhooo1$1kdal$1_at_ID-28204.news.uni-berlin.de>...
> Modifying Celko's Adjaceny List example to a table containing a
> transitive closure of a tree (without pathlength):
>
> CREATE TABLE OrgChart
> (emp CHAR(10) NOT NULL,
> boss CHAR(10) NOT NULL,
> PRIMARY KEY (emp, boss)
> );
>
> INSERT INTO OrgChart VALUES('Bert', 'Albert');
> INSERT INTO OrgChart VALUES('Chuck', 'Albert');
> INSERT INTO OrgChart VALUES('Donna', 'Albert');
> INSERT INTO OrgChart VALUES('Donna', 'Chuck');
> INSERT INTO OrgChart VALUES('Eddie', 'Albert');
> INSERT INTO OrgChart VALUES('Eddie', 'Chuck');
> INSERT INTO OrgChart VALUES('Fred', 'Albert');
> INSERT INTO OrgChart VALUES('Fred', 'Chuck');
> INSERT INTO OrgChart VALUES('Herbert','Albert');
> INSERT INTO OrgChart VALUES('George', 'Albert');
> INSERT INTO OrgChart VALUES('George', 'Chuck');
> INSERT INTO OrgChart VALUES('George', 'Eddie');
>
> Expected order by hierarchy:
> Albert
> Bert
> Chuck
> Donna
> Eddie
> George
> Fred
> Herbert
>
>
> I'd like to know if there's a _single_ SQL statement to retrieve that
> result set?
>
> Dieter

I assume what you asking for is how to retrive the emps in an order that reflects their org position. I suspect it to be a hard problem (impossible?) for "unlimited" trees. With "unlimited" I mean that we cannot assume a maximum depth nor a maximum width for the organisation.

If we on the other hand could assume max depth, width on the tree, it would be possible to calculate an ordering number for each emp. The indent level could be calculated by repeat(' ', depth).

The relation parent together with the depth of each emp could be calculated as something like:

with ancestors (emp, boss, depth) as (

    select emp, boss,

          (select count(1) from OrgChart where o.boss = emp) as depth     from OrgChart o
), parent (emp, boss) as (

    select emp, boss from ancestors a
    where depth = (select max(depth) from ancestors where emp = a.emp) ) select p.emp, p.boss, a.depth from parent p, ancestors a   where p.emp = a.emp and p.boss = a.boss"    

/Lennart

--
the above email no longer works due to spam.
values'lennart'||CHR(46)||'jonsson'||CHR(64)||'enlight'||CHR(46)||'net'