Nested Sets (was: mRFC 0024: Full text indexing in Midgard)

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi Jukka,

- --Jukka Zitting wrote on 2006-01-03 11:31:
>> > The parent_down and parent_up fields contain special depth-first traversal
>> > indexes of the object within the global content tree. This allows for very quick
>> > determination of ancestor relations using predicates like:
>> >
>> > A is an ancestor of B :-
>> >     A.parent_down < B.parent_down,
>> >     A.parent_up > B.parent_up.
>>
>> I'm not sure if I fully understand this. I keep asking myself "why not having
>> just a depth integer", but i have the distinct feeling that I miss something here.
> 
> It's the nested set model for storing hierarchical information in a
> relational database (see
> http://threebit.net/tutorials/nestedset/tutorial1.html). It gives you
> a single query implementation of the "ancestor of" and "descendant of"
> predicates. A depth integer doesn't cut it as it doesn't distinguish
> between separate branches of the content tree.

Ah, ok. Now I think I get it. The columns you've named parent_(up|down) are what
the article dfines as "left/right" indexes in the "artificial" depth list.

For those who are new to this like me: The nested set theory link in the
reference gave by Jukka is down. A bit of Google brought me to
http://www.developer.com/db/article.php/3517366 which was a bit easier to
understand for me.

http://www.dbmsmag.com/9603d06.html seems to be the article of the "founder" of
the idea.


Live long and Prosper!
Torben Nehmer

- --
Torben Nehmer, Guenzburg, Bavaria, Germany
http://www.nathan-syntronics.de, mailto:[email protected]
PGP Public Key: https://www.link-m.de/pgp/t.nehmer.asc
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (MingW32)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFDullcJPh4Kn6d5FYRAqdAAJ4jnkkVt78PUSlIs57KxgT4ITLeMgCfSM7B
HiC+Y7pq6Q5p0dhHvH81zwg=
=WMmk
-----END PGP SIGNATURE-----