Re: Implementing trees in a relational database
Date: 30 Jul 2002 17:06:05 +0200
Message-ID: <3d46ab5d$1_at_news.uia.ac.be>
In article <vafeldlnw12.fsf_at_lucy.cs.uni-dortmund.de>,
Kai Großjohann <Kai.Grossjohann_at_CS.Uni-Dortmund.DE> wrote:
>"Paul DeWolf" <paul_at_thievesandkings.com> writes:
>
>> Can someone point me to information (books, white papers) on techniques for
>> efficiently implementing trees and networks in an RDBMS? Has anyone done it
>> themselves and showed that they can scale linearly?
>
>"Accelerating XPath location steps" by Torsten Grust. The idea is to
>number the nodes in preorder and postorder and to store both numbers
>for each node. If you also store the level in the tree then you can
>find out whether A is ancestor of B or A is parent of B really
>quickly.
That's actually a standard trick and equivalent to Joe Celko's nested sets approach. If you are interested in this check out also the paper on this at SIGMOD/PODS by Cohen, Kaplan and Milo titles "Labeling Dynamic XML trees"
http://www.informatik.uni-trier.de/~ley/db/conf/pods/pods02.html#CohenKM02
It tries to come up with numbering schemes for trees that change a lot, because that is the weak spot of the numberting scheme.
- Jan Hidders