Re: Ordered result set with path enumeration
Date: 17 Aug 2003 21:07:39 -0700
Message-ID: <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?
If you know transitive closure, then you can answer the following mini-questions:
- Is B parent of A?
- Find all the ancestors of A.
- 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. Received on Mon Aug 18 2003 - 06:07:39 CEST