Re: Ordered result set with path enumeration

From: Vadim Tropashko <vadimtro_at_yahoo.com>
Date: 17 Aug 2003 21:07:39 -0700
Message-ID: <22d2e427.0308172007.7eb298f@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 Sun Aug 17 2003 - 23:07:39 CDT