Re: self referencing tables/ nested sets etc...

On Fri, 26 Mar 2004 01:03:38 +0100, Rob Hoopman <rob@tuna.nl> wrote:
>So it seems that you are right, but the magic number seems to be 49

>NOTICE:  num is:   3
>NOTICE:  den is:   2
>NOTICE:  child is: 49
>WARNING:  Error occurred while executing PL/pgSQL function child_numer
>WARNING:  while casting return value to function's return type
>ERROR:  Bad int8 external representation "1.12589990684263e+15"

>    RETURN num*pow(2, child)+3-pow(2, child);

pow() is a floating point function.  Double has a precision of 48 bits,
so 2 ^ 48 is the largest number that can reliably be converted from
double to bigint.  Better use integer arithmetic:

CREATE OR REPLACE FUNCTION pow2(bigint) RETURNS bigint AS '
DECLARE
  e bigint;
  ret bigint;
BEGIN
  e = $1;
  IF (e < 0) THEN
    RAISE EXCEPTION ''2 ^ % does not fit into a bigint'', e;
  END IF;
  IF (e > 62) THEN
    RAISE EXCEPTION ''2 ^ % does not fit into a bigint'', e;
  END IF;
  ret = 1;
  WHILE (e > 0) LOOP
    ret = 2 * ret;
    e = e - 1;
  END LOOP;
  RETURN ret;
END
' LANGUAGE plpgsql;

Thus you could use OMPM to store up to 61 child nodes, but only for the
very first parent node ("1.1", ..., "1.61").

BTW, I've read Tropashko's follow-up articles
http://arxiv.org/html/cs.DB/0401014, http://arxiv.org/pdf/cs.DB/0402051,
as well as various discussions on comp.databases.theory.  My conclusion
is that OMPM is irreparably broken.  With every kludge added to it
(Farey Intervals, Continued Fractions) the correspondence to
materialized path strings gets even more obfuscated, but the main
shortcoming remains:  If you try to store materialized path information
in a fixed number of integers you run out of bits very soon.

And if you use floating point you lose accuracy.
Fuzzy trees: "My boss is JONES.  Or is it CLARK?"

Servus
 Manfred