Re: Tropashko nested sets and materialized path - great idea but how do I insert?

From: Mikito Harakiri <mikharakiri_at_ywho.com>
Date: Thu, 11 Sep 2003 13:56:40 -0700
Message-ID: <Fs58b.22$927.175@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 Thu Sep 11 2003 - 15:56:40 CDT