We label each tree node with a single positive integer number. This
labeling is closely related to binary rational interval labeling
defined in http://www.dbazine.com/tropashko4.html

Given natural number N, let k be maximal integer satisfying 2^k <= N.
In other words

k = floor(log(2,N))

We define mapping between binary rational interval labeling (x,y) and
N as follows:

y+(1-x) = 1 - 1/2^(k+1)

1-x = (N-2^k)/2^k

For example, the node "1.4" or <x=9/16, y=17/32> corresponds to N=23.

The nice property of single integer labeling is very simple definition
of transitive closure relation. Given 2 nodes i and j such that i <= j
let k' be maximal integer satisfying i*2^k' <= j. Consider binary
relation "le" satisfying

i "le" j <=> j-i*2^k' < i*2^(k'-1)/j or i = j.

Here is implementation as a distance function

CREATE or replace
function dist ( child integer, parent integer )
RETURN integer IS
ret integer;
arifgeom integer;
pwr integer;
BEGIN
if parent > child then
RETURN -1;
end if;
if parent = child then
RETURN 0;
end if;
arifgeom := parent;
pwr := 0;
while arifgeom*2 <= child loop
arifgeom := arifgeom*2;
pwr := pwr+1;
end loop;
if child-arifgeom < arifgeom/(parent*2) then
RETURN pwr;
end if;
RETURN -1;
END;
/

select dist(11,3), dist(12,3), dist(13,3), dist(14,3) from dual
-1 2 2 -1

In other words the function returns distance between parent and child
in the tree or -1 if child is not reacheable from parent.

I'll submit more readable version to dbazine.com (with pictures!)

Excellent. However, as I have project meeting this afternoon to discuss my
technical specification for our project, I am still not sure whether to
recommend Materialized Path or Adjacency List - perhaps you could flesh it
out a little more before then ?

"Vadim Tropashko" <vadimtro (AT) yahoo (DOT) com> wrote

No, I wouldn't rely on it, especially when being constrained by
project schedule. For one thing, this new labeling method works well
when traversing hierarchy up. When traversing hierarchy down (for
example, aggregated total report), then the subtree is potentially too
large to build "in-list" of node labels, but yet small enough for
range scan in nested intervals method. Therefore, you would still need
to translate to intervals in that case, which renders the method much
less useful.

In short, fix the ariphmetics. It's something much more
straightforward than inventing new tree labeling method.

As some more goofy alternative you can write parsing functions which
would work with materialized path exclusively. For example, the
distance function is the difference in the number of dots (or whatever
separator token is), assuming that one path is the prefix of the
other.

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