Re: Tropashko nested sets and materialized path - great idea but how do I insert?
From: Robin Tucker <r.tucker_at_thermoteknix.com>
Date: Fri, 12 Sep 2003 12:23:49 +0100
Message-ID: <bjsa9j$oc5$1$8300dec7_at_news.demon.co.uk>
> "Robin Tucker" <r.tucker_at_thermoteknix.com> wrote in message
> news:bjphtu$279$1$8302bc10_at_news.demon.co.uk...
> > I cannot see how to cut/paste parts of the hierarchy around.
>
> 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
>
>
>
>
>
Received on Fri Sep 12 2003 - 13:23:49 CEST
Date: Fri, 12 Sep 2003 12:23:49 +0100
Message-ID: <bjsa9j$oc5$1$8300dec7_at_news.demon.co.uk>
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.com> wrote in message
news:Fs58b.22$927.175_at_news.oracle.com...
> "Robin Tucker" <r.tucker_at_thermoteknix.com> wrote in message
> news:bjphtu$279$1$8302bc10_at_news.demon.co.uk...
> > I cannot see how to cut/paste parts of the hierarchy around.
>
> 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
>
>
>
>
>
Received on Fri Sep 12 2003 - 13:23:49 CEST