Re: yet another hierarchy model

Vadim Tropashko <nospam_at_newsranger.com> wrote in message news:<JlJz7.34751
> One big distinction between materialized path and your decomposition into
> product of primes is that the first one is resilient to tree modifications,
> while the second one isn't (what happens if you add 2 more children to Fred?).

You just multiply the new factors into the ancestors of the new nodes (see below).

> Therefore, the similarity between "Albert.Chuck.Fred" and 2*3*3 is only
> superficial; I would suggest that they are different methods.

True, this is more of a way of embedding a tree on a lattice, that is, each node maps to a set of objects which is a superset of all the nodes below it. In this case each set is a set of prime factors (chosen from the first n primes, say, for some n), but you can use any set, or a bitmap representing a set, etc.

eg adding a leaf node

   6       ==>  30  (more bits)
  / \           / \
 2   3         2  15  (more bits)
                    \
                     5 (few bits)

   (note I'm retaining the ID 3 at the intermediate node; it might be better to assign a prime ID to every node, not just leaves as I first proposed)

   A       ==>   A  (same bits)
  / \           / \
 AB AC         AB  AC  (same)
                    \
                   ACD  (more bits)

The similarity with the materialized path approach is more in the number of bits used; both require variable-length bitstrings. The difference is that adding a leaf node adds bits to nodes all the way up to the root, whereas the materialized path only adds a suffix at the leaf node and leaves the rest unchanged.

As an alternative to doing a lot of multiplying, an equivalent approach would be to just materialize a set at each node consisting of all the node ID's below it, eg:

  ABCD
  / \
 B CD

      \
       D

Unfortunately there's no "subset" operator in SQL, so it's hard to find much use for this in practice. Received on Sat Oct 20 2001 - 02:28:37 CEST