Re: Nested sort, trying again

Bob Stearns wrote:
> mAsterdam wrote:

>> Bob Stearns wrote:
[snip]
> I thought everyone on here would be familiar with Joe Celko's Nested Set
> representation of a tree; he has an entire book devoted to it: _Trees
> and Hierarchies in SQL for Smarties_; ISBN 1-55860-920-2.

I should be. It has been on my to-buy list for way too long.

> It uses the left and right indices to represent containership.

Wouldn't they be foreign keys?

Variations on 'left' and 'right' do seem the chosen names for this :-(
I'm not really happy with those names, but I can't come up with better ones.

> For instance the tree
> a(b(c,d),e(f(g,h))) (sorry for the linear representation, ASCII does not
 > lend itself to drawing trees)

This is readable enough.

 > would be represented by the rows:

>
> a 1 16
> b 2 7
> c 3 4
> d 5 6
> e 8 15
> f 9 14
> g 10 11
> h 12 13

Ah. I see. Thank you for the explanation.

One problem here is that the data in the tables needs extra rules to be processed correctly. IOW not everything needed to preserve the integrity is in the schema.

> A leaf node has left=right-1. Higher nodes have left < left of any
> child, right > right of any child. Lots of good properties for adding
> and searching, not too difficult changing, rather harder deletion.
>
> In this case the tree is sorted in the order I want to present it to my
> users. Consider the tree z(y(x,w),v(y(t,s))) which would have a similar
> representation to the first on but which I wish to present to my users as:
>
> z
> v
> u
> s
> t
> y
> w
> x
> The question is: Is there an easy (relatively) way to produce this sort
> without a recursive sql user defined function?

Not that I know of, sorry.
Naz Gassiep promises a PL/SQL procedure for it, though: http://old.mrnaz.com/notes/nestedsets/mptt_display.php Received on Thu Sep 29 2005 - 23:31:15 CEST