Re: Q about materialized paths

"Troels Arvin" <troels_at_arvin.dk> wrote in message news:pan.2004.09.29.07.39.33.43914_at_arvin.dk...
> On Wed, 29 Sep 2004 08:31:35 +0200, <Leander> wrote:
>
> > Is it known who "invented" materialized path approach in modeling
> > hierarchical data with SQL?
>
> According to Celko[1], the materialized path (AKA "path enumeration")
> encoding was _made popular_ by [2], but Celko doesn't state who invented
> the encoding. Perhaps [2] has references to original works?
>
>
> Notes
> -----
> 1: Joe Celko: Trees and Hierarchies in SQL for Smarties
> ISBN 1558609202
> http://books.elsevier.com/mk/default.asp?isbn=1558609202
>
> 2: Ben-Gan, Moreau: Advanced Transact-SQL for SQL Server 2000
> ISBN 1893115828
> http://www.apress.com/book/bookDisplay.html?bID=72

Materialized path encoding is so obvious that, perhaps, the term "invention" applied to it looks as silly as "one-click patent".

To expand the OP question, here is some info about other encodings i found recently.

Continued Fractions encoding has been proposed as early as: P. Ciaccia, D. Maio, and P. Tiberio. A method for hierarchy processing in relational
systems. Information Systems, 14(2):93-105, 1989.

Dyadic rationals is one of the major themes of Conway's book "On numbers and games".

I'm reposting this extract from fine note by Peter Johnstone i found on the web.

Conway's definition is based on the idea that the simplest number between 0 and 1/2 is 1/4, the simplest between 1/4 and 1/2 is 3/8, and so on; thus the simplest number in any nontrivial interval is always a dyadic rational (i.e. one whose denominator is a power of 2). Suppose you want to regard all rationals as simple, and use smallness of denominator as a measure of simplicity; then you would say that the simplest number between 0 and 1/2 is 1/3, the simplest between 1/3 and 1/2 is 2/5, .... Norton observed that this notion of simplicity can be encoded by the notion of continued fraction, as follows:

Define a bijection f: [0,1] --> [0,1] as follows: if x has binary expansion .00...011...100...011...1..., where there are a (\geq 0) zeros in the first block, then a block of b (\geq 1) 1's, then c (\geq 1) zeros, and so on, then
f(x) is the continued fraction

            1
         --------------------
         (a+1) + 1
                 ------------
                 b + 1
                     ---------
                     c + ......

Thus, for example, if x = 1/4, its two binary expansions .0100000... and .00111111... yield the two expressions

            1                                1
         --------------      and          ----------
         2 + 1                            3 + 1
             ----------                       ------
             1 + 1                            \infty
                 ------
                 \infty

for f(1/4) = 1/3.