Re: Ordered result set with path enumeration

"Vadim Tropashko" <vadimtro_at_yahoo.com> wrote in message news:22d2e427.0308172007.7eb298f_at_posting.google.com...
> Dieter Nöth <dnoeth_at_gmx.de> wrote in message
news:<bhooo1$1kdal$1_at_ID-28204.news.uni-berlin.de>...
> (abridged)
> > Modifying Celko's Adjaceny List example to a table containing a
> > transitive closure of a tree (without pathlength):
> > 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?

>

>


> 1. Is B parent of A?

> 2. Find all the ancestors of A.

> 3. How many ancestors A have?

create or replace view Nodes as
select emp name,

   (select count(1) from OrgChart hh where h.emp=hh.emp) indent,    (select boss from OrgChart hh where h.emp=hh.emp     and (select count(1) from OrgChart hhh where hh.emp=hhh.emp)     =(select count(1) from OrgChart hhh where hh.boss=hhh.emp)+1    ) reportsTo
from OrgChart h
union
select boss name,

   (select count(1) from OrgChart hh where h.boss=hh.emp) indent,    (select boss from OrgChart hh where h.boss=hh.emp     and (select count(1) from OrgChart hhh where hh.emp=hhh.emp)     =(select count(1) from OrgChart hhh where hh.boss=hhh.emp)+1    ) reportsTo
from OrgChart h

select * from nodes

NAME INDENT REPORTSTO
---------- ---------- ----------

Albert              0
Bert                1 Albert
Chuck               1 Albert
Donna               2 Chuck
Eddie               2 Chuck
Fred                2 Chuck
George              3 Eddie
Herbert             1 Albert

I aliased level as "indent", because "level" is a reserved word in oracle. Alias "reportsTo" means (immediate) parent. Also note that Oracle doesn't requre AS keyword between expression and alias.

The union just serves a sole purpose of adding just one more node since neither emp nor boss column alone contains complete set of nodes.

> 6. For any nodes A and B we write A > B whenever
> i. B is parent of A or
> ii. there exists node B' which is an ancestor of B,
> and A' which is an ancestor of A,
> and both A' and B' having the same parent,
> and A' > B'
> 7. For any node A, the depth first enumeration number is the number of
> nodes that are predecessors of A with the ordering defined at the
> step# 6.

create view DepthFirst as (

   select boss lesser, emp greater from OrgChart    union
   select distinct n1.name, n2.name
   from nodes n1, nodes n2, nodes n01, nodes n02    where n01.reportsTo = n02.reportsTo and n01.name < n02.name    and (n01.name=n1.name or n01.name in

      (select boss from OrgChart where emp = n1.name))    and (n02.name=n2.name or n02.name in

      (select boss from OrgChart where emp = n2.name)) )

select greater as name, count(1) from DepthFirst group by greater union
select lesser, (select count(1) from nodes)-count(1)-1 from DepthFirst group by lesser

NAME COUNT(1)
---------- ----------

Albert              0
Bert                1
Chuck               2
Donna               3
Eddie               4
Fred                6
George              5
Herbert             7

Here union is used again to add one extra node. Clearly the sequence number in the total oredring could be calculated 2 way, incremantally from the beginning of the list, or decrementally from the list end.

By joining these 2 queries together you'll be able to get the report you need.

While the solution is formally not a single SQL query, it could be easily transformed into a such. You could either inline views, or use "with" clause. Received on Mon Aug 18 2003 - 23:13:39 CEST