Re: A tree with 1M nodes

From: Ernst-Udo Wallenborn <ernst-udo.wallenborn_at_freenet.de>
Date: 22 Jan 2004 18:26:11 +0100
Message-ID: <m3oesvzyh8.udo@no.domain.net>

vadimtro_invalid_at_yahoo.com (Vadim Tropashko) writes:

> http://arxiv.org/html/cs.DB/0401014

Wow. I'm deeply impressed.

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?

-- 
Ernst-Udo Wallenborn

Received on Thu Jan 22 2004 - 11:26:11 CST