Ordered result set with path enumeration
Dieter Nöth
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
Vadim Tropashko
(abridged)
> Modifying Celko's Adjaceny List example to a table containing a
> transitive closure of a tree (without pathlength):
> 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?
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.
Lennart Jonsson
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'
Mikito Harakiri
"Vadim Tropashko" <vadi...@yahoo.com> wrote in message
news:22d2e427.0308...@posting.google.com...
> Dieter Nöth <dno...@gmx.de> wrote in message
news:<bhooo1$1kdal$1...@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?
>
> 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?
> 5. Do A and B have the same parent?
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.
Lennart Jonsson
> "Vadim Tropashko" <vadi...@yahoo.com> wrote in message
[...]
>
> > 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))
> )
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
--CELKO--
that result set? <<
Now, do you see why I like my Nested Sets model :)
Lennart Jonsson
> news:22d2e427.0308...@posting.google.com...
> > Dieter Nöth <dno...@gmx.de> wrote in message
> news:<bhooo1$1kdal$1...@ID-28204.news.uni-berlin.de>...
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
> > 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.
>
[...]
Lennart Jonsson
> "Mikito Harakiri" <mikha...@ywho.com> wrote in message news:<msb0b.24$hi4...@news.oracle.com>...
> > "Vadim Tropashko" <vadi...@yahoo.com> wrote in message
> > news:22d2e427.0308...@posting.google.com...
> > > Dieter Nöth <dno...@gmx.de> wrote in message
> > news:<bhooo1$1kdal$1...@ID-28204.news.uni-berlin.de>...
>
> Vadimtro (Mikito?). Shouldnt 6. be changed to
>
Oops, should have been Vadim. Sorry about that.
[...]
/Lennart
Vadim Tropashko
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;-)
len...@kommunicera.umea.se (Lennart Jonsson) wrote in message news:<6dae7e65.03091...@posting.google.com>...