Dieter Nöth <dnoeth (AT) gmx (DOT) de> wrote

(abridged)
If you know transitive closure, then you can answer the following
mini-questions:

1. Is B parent of A?
2. Find all the ancestors of A.
3. How many ancestors A have?

Here I'm numbering queries progressively so that it's evident how the
subsequent queries leverage predecessors.

The subquery #3 allows you to calculate the level (or indentation) of
the each node. It is slightly more challenging to figure out the
second dimension -- depth-first tree enumeration sequence number. (I
assume that each node's children are ordered somehow; for example it
might be natural to order nodes with character string labels by
leveraging lexicographic ordering, e.g. "Bert"<"Chuck"). Let's answer
some simpler queries first:

4. What is immediate parent of A?
5. Do A and B have the same parent?

Note that query #4 is a trivial selection in the case of adjacency
list, but it's slightly more complicated in case where the base
relation is transitive closure.

Now we are ready to define a total ordering on the 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.

Translating the above steps into SQL is left as an exercise to the
reader.

Dieter Nöth <dnoeth (AT) gmx (DOT) de> wrote

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)||'enl ight'||CHR(46)||'net'

"Vadim Tropashko" <vadimtro (AT) yahoo (DOT) com> wrote

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.

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.

"Mikito Harakiri" <mikharakiri (AT) ywho (DOT) com> wrote

[...]

Ahh, very elegant. I never thought of that way to define the ordering
relation. I was more into calculating the size of each subtree s, and
then number the next sibling of s according to that. This is clearly
much better

/Lennart, a bit more enlightened
--
the above email no longer works due to spam.
values'lennart'||CHR(46)||'jonsson'||CHR(64)||'enl ight'||CHR(46)||'net'

Now, do you see why I like my Nested Sets model

"Mikito Harakiri" <mikharakiri (AT) ywho (DOT) com> wrote

Vadimtro (Mikito?). Shouldnt 6. be changed to

6. For any nodes A and B we write A > B whenever
i. B is an ancestor of A or ...

? I noticed that Mikito used the OrgChart (ancestor) relation, and
when I played a round with a similar thing myself, some tuples are
missing in my "total_order" relation using parent.

[...]

Kind regards
/Lennart


[...]

lennart (AT) kommunicera (DOT) umea.se (Lennart Jonsson) wrote in message news:<6dae7e65.0309152011.6a4cc4fa (AT) posting (DOT) google.com>...
Oops, should have been Vadim. Sorry about that.

[...]


/Lennart

It must be ancestor. When displaying hierarchy chart "rolled down"
ancestor is always preceding its descendants.

Note that in couple of places it was written "immediate parent".
Therefore, in all cases where the parent is not explicitly adjected
with "immediate", I reserve a possibility of mistake;-)

lennart (AT) kommunicera (DOT) umea.se (Lennart Jonsson) wrote in message news:<6dae7e65.0309152011.6a4cc4fa (AT) posting (DOT) google.com>...