Re: A tree with 1M nodes

Ernst-Udo Wallenborn wrote:

> But i have a question: shouldn't the '>=' in the last line
> of the following
>
> -- all descendants of O = (5/7,3/4]
> with O as (select rational(5,7) l, rational(3,4) r from dual)
> select name, '('|| t.lft.print() ||','|| rgt(t.lft).print() ||']'
> from tree t, O
> where compare(l, lft) > 0 and compare(lft, r) >= 0;
> be a '>'? I seem to always retrieve the next older sibling with '>=',
> e.g. (this is implemented in PostgreSQL):
>
>
> test=> select * from tree;
> payload | num | den
> ---------+-----+-----
> 1 | 1 | 2
> 1.1 | 2 | 3
> 1.1.1 | 3 | 4
> 1.2 | 3 | 5
> 1.3 | 4 | 7
> (5 rows)
>
> test=> select * from offspring(rational(3,5));
> payload | num | den
> ---------+-----+-----
> 1.1 | 2 | 3
> (1 row)
>
> where the 2/3 node seems to match the equality. Since if lft = 3/5
> rgt(lft) = 2/3 (hence the semi-open interval for 1.2 is (3/5,2/3])
> then for l = 2/3 in the select compare(2/3,2/3) is 0 and the
> node shows up in the result set.
>
> Am i overlooking something?

You are correct! The predicate initially has been written as

compare(l, lft) > 0 and compare(rgt, r) >= 0

which is a condition for nesting of semi-open interval (lft,rgt] inside (l,r]. It is equivalent to

compare(l, lft) > 0 and compare(lft, r) > 0

Non peer-reviewed publication is expected to have snags like that;-) Received on Thu Jan 22 2004 - 18:49:05 CET