I'm sure this has been answered many times before, unfortunately my news
server only has the last 300 or so messages from this group.

I have implemented Tropashkos' nested sets and materialized path algorithms
for my tree structure - I can see how I might insert a new node after the
current right-most node, but I cannot see how to "insert_before(node)" or
"insert_after(node)" or cut/paste parts of the hierarchy around. I guess
the problem
here is I lack an understanding of binary fractions. For example, say the
hierarchy
node .2.3 is represented by 83/64, is there a quick and easy way of bumping
the node up one to 2.4? And then how can I also increment the node 2.3.2
for
example so it is now 2.4.2? I would like to do this with a single "Update",
so I can
make a gap for the new node to be inserted. I know how to select the
hierarchy
from a give node.

This would seem to me to be a real problem with this method which the
adjacency list handles sweetly. Perhaps there is a discussion on these
points somewhere? I would love a solution because without it I will just
have to ditch the nested sets and materialized path implementation and head
back over to the rather dodgy adjacency list.

Thanks for any info you can give me.


Robin Tucker

"Robin Tucker" <r.tucker (AT) thermoteknix (DOT) com> wrote

The article mentioned that every subtree is a scaled up (or down) replica of
the other subtree. That's the idea.

Suppose you want to move the node 27/16 positioned in a subtree originated
in 3/2 into a subtree originated in 7/8. (Actually you want to move the
whole subtree originated in 27/16 into the new position 3/2).
Let's intoduce some notation:
"old"=27/16
"old_origin"=3/2
"new_origin"=27/16
so that we want to know what "new" position is. We'll write scaling&shifting
transformation component-wise as follows:

new_x - new_origin_x = k * (old_x - old_origin_x)
new_y - new_origin_y = k * (old_y - old_origin_y)

That's again nothin more than linear transformation, where k is zooming
factor. Zooming factor is just the ratio of the origin's denominators -- the
main picture of the article can convince you if you have any doubt about it.

If we add these equations together, then we have

(new_x+new_y) - (new_origin_x+new_origin_y) =
k * ((old_x+old_y) - (old_origin_x+old_origin_y))

Now since those node codings were defined as sums of componets we simplify
it to

new - new_origin = k * (old - old_origin)

The implementation is straightforward. The only technicality is using
integer numbers, this is why it is more lengthy that it could be. Let's
introduce 2 helper functions that would normalize a rational binary number
first:

CREATE or replace
function normalize_numer( numer integer, denom integer )
RETURN integer IS
num integer;
den integer;
BEGIN
num := numer;
den := denom;
while floor(num/2) = num/2 loop
num := num/2;
den := den/2;
end loop;
RETURN num;
END;
/

CREATE or replace
function normalize_denom( numer integer, denom integer )
....
RETURN den;
END;
/

select normalize_numer(10, 16) || '/' || normalize_denom(10, 16) from dual
5/8

Now the functions that calculate moved node position:

CREATE or replace
function new_numer
( old_numer integer, old_denom integer,
old_origin_numer integer, old_origin_denom integer,
new_origin_numer integer, new_origin_denom integer )
RETURN integer IS
ret_num integer;
ret_den integer;
zoom_factor integer;
is_magnified boolean;
BEGIN
-- hangs in that special case, no time to investigate why
if old_numer=old_origin_numer and old_denom=old_origin_denom then
RETURN new_origin_numer;
end if;
if old_origin_denom < new_origin_denom then
is_magnified := false;
zoom_factor := new_origin_denom/old_origin_denom;
-- subtract old - old_origin first, then multiply
-- certainly old_denom > old_origin_denom
ret_num := old_numer - old_origin_numer*old_denom/old_origin_denom;
ret_den := old_denom*zoom_factor;
ret_num := normalize_numer(ret_num, ret_den);
ret_den := normalize_denom(ret_num, ret_den);
else
is_magnified := true;
zoom_factor := old_origin_denom/new_origin_denom;
ret_num := (old_numer -
old_origin_numer*old_denom/old_origin_denom)*zoom_factor;
ret_den := old_denom;
ret_num := normalize_numer(ret_num, ret_den);
ret_den := normalize_denom(ret_num, ret_den);
end if;
-- now we don't know if ret_denom is larger than new_origin_denom or not
if ret_den < new_origin_denom then
ret_num := new_origin_numer + ret_num*new_origin_denom/ret_den;
ret_den := new_origin_denom;
else
ret_num := new_origin_numer*ret_den/new_origin_denom + ret_num;
ret_den := ret_den;
end if;
ret_num := normalize_numer(ret_num, ret_den);
ret_den := normalize_denom(ret_num, ret_den);
RETURN ret_num;
END;
/

CREATE or replace
function new_denom
( old_numer integer, old_denom integer,
old_origin_numer integer, old_origin_denom integer,
new_origin_numer integer, new_origin_denom integer )
RETURN integer IS
ret_num integer;
ret_den integer;
zoom_factor integer;
is_magnified boolean;
BEGIN
....
RETURN new_origin_denom; -- special case
....
RETURN ret_den; -- main logic
END;
/

Warmup testing:

select new_numer(27,16, 3,2, 3,4)||'/'||new_denom(27,16, 3,2, 3,4) from dual
27/32

select new_numer(27,16, 7,4, 3,4)||'/'||new_denom(27,16, 7,4, 3,4) from dual
11/16

Main test, given

SQL> select substr(lpad(' ',3*depth)||name, 1, 15), substr(path,1,15),
numer, denom
2 from hierarchy order by numer_left/denom_left;

SUBSTR(LPAD('', SUBSTR(PATH,1,1 NUMER DENOM
--------------- --------------- ---------- ----------
KING .1 3 2
CLARK .1.3 19 16
MILLER .1.3.1 39 32
BLAKE .1.2 11 8
TURNER .1.2.4 163 128
MARTIN .1.2.3 83 64
WARD .1.2.2 43 32
ALLEN .1.2.1 23 16
JONES .1.1 7 4
FORD .1.1.2 27 16
SMITH .1.1.2.1 55 32
SCOTT .1.1.1 15 8
ADAMS .1.1.1.1 31 16

we move all hierarchy under "BLAKE" into "MILLER" as follows:

SQL> update emps
2 set numer = new_numer(numer,denom, 11,8, child_numer(39,32,1),
child_denom(39,32,1))
3 , denom = new_denom(numer,denom, 11,8, child_numer(39,32,1),
child_denom(39,32,1))
4 where distance(numer,denom, 11,8)>=0
5 ;

5 rows updated.

The idea is to find the first child of MILLER -- child_...(39,32,1) -- and
move all the nodes reachable from BLAKE (11/8) into the new place

The resulting hierarchy:

SQL> select substr(lpad(' ',3*depth)||name, 1, 15), substr(path,1,15),
numer, denom
2 from hierarchy order by numer_left/denom_left;

SUBSTR(LPAD('', SUBSTR(PATH,1,1 NUMER DENOM
--------------- --------------- ---------- ----------
KING .1 3 2
CLARK .1.3 19 16
MILLER .1.3.1 39 32
BLAKE .1.3.1.1 79 64
TUR .1.3.1.1.4 1251 1024
MAR .1.3.1.1.3 627 512
WAR .1.3.1.1.2 315 256
ALL .1.3.1.1.1 159 128
JONES .1.1 7 4
FORD .1.1.2 27 16
SMITH .1.1.2.1 55 32
SCOTT .1.1.1 15 8
ADAMS .1.1.1.1 31 16

Thanks for a most interesting explaination. I had no idea it would be quite
so "simple" (compared to the adjacency list). I have read so much bull
about how this is the Achilles heal of the nested set method.

"Mikito Harakiri" <mikharakiri (AT) ywho (DOT) com> wrote

I have a chapter on Tropashko's binary fractions method in my
forcoming book on trees and hierarchies in SQL. I would like to use
this in that chapter, with credit (I also need to get your permission
for some other quotes from newsgroups).

This looks nice! I have not had time to play with the code and
translate it into an SQL dialect I have on a machine at work yet.

What is the purpose of the "is_magnified BOOLEAN" variable? Besides
my usual objection to having the proprietary BOOLEAN data type in a
program, it is assigned a value and then never used.

joe.celko (AT) northface (DOT) edu (--CELKO--) wrote in message news:<a264e7ea.0309141102.600a5858 (AT) posting (DOT) google.com>...
No problem.

Vadim Tropashko (aka Mikito Harakiri)

joe.celko (AT) northface (DOT) edu (--CELKO--) wrote in message news:<a264e7ea.0309141102.600a5858 (AT) posting (DOT) google.com>...
It's redundant indeed. Redundant variables can be considered as comments, though.

I wondered about the is_magnified variable too. Changed it from BOOLEAN to
BIT before realising that it isn't needed. Anyway, this is the T-SQL
version below - it works like a charm.

Thanks people.


CREATE FUNCTION dbo.func_Move_Numerator
(
@old_numer INTEGER,
@old_denom INTEGER,
@old_origin_numer INTEGER,
@old_origin_denom INTEGER,
@new_origin_numer INTEGER,
@new_origin_denom INTEGER
)
RETURNS INTEGER
AS
BEGIN
DECLARE @ret_num INTEGER
DECLARE @ret_den INTEGER
DECLARE @zoom_factor INTEGER
DECLARE @is_magnified BIT

IF @old_numer = @old_origin_numer AND @old_denom = @old_origin_denom
RETURN @new_origin_numer

IF @old_origin_denom < @new_origin_denom
BEGIN
SET @is_magnified = 0

SET @zoom_factor = @new_origin_denom / @old_origin_denom
SET @ret_num = @old_numer - @old_origin_numer * @old_denom /
@old_origin_denom
SET @ret_den = @old_denom * @zoom_factor

SET @ret_num = dbo.func_Normalize_Numerator ( @ret_num )
SET @ret_den = dbo.func_Normalize_Denominator ( @ret_num, @ret_den )
END
ELSE
BEGIN
SET @is_magnified = 1

SET @zoom_factor = @old_origin_denom / @new_origin_denom
SET @ret_num = ( @old_numer - @old_origin_numer * @old_denom /
@old_origin_denom ) * @zoom_factor
SET @ret_den = @old_denom
SET @ret_num = dbo.func_Normalize_Numerator ( @ret_num )
SET @ret_den = dbo.func_Normalize_Denominator ( @ret_num, @ret_den )
END

IF @ret_den < @new_origin_denom
BEGIN
SET @ret_num = @new_origin_numer + @ret_num * @new_origin_denom /
@ret_den
SET @ret_den = @new_origin_denom
END
ELSE
BEGIN
SET @ret_num = @new_origin_numer * @ret_den / @new_origin_denom +
@ret_num
SET @ret_den = @ret_den
END

SET @ret_num = dbo.func_Normalize_Numerator ( @ret_num )
SET @ret_den = dbo.func_Normalize_Denominator ( @ret_num, @ret_den )

RETURN @ret_num
END