Re: Implementing trees in a relational database

Here is an extract from
http://www.dbazine.com/pascal4.html

>>>> begin >>>>
Here's Hugh Darwen on the so-called "XML query algebra": "Now, my eyes light up at the word "algebra" ... Originally, I understood it to mean a set of operations that are closed over some type. That is, every operation in X Algebra operates on zero or more values of type X and returns a value of type X. Hence, set algebra, Boolean algebra, relational algebra and the algebra of numbers that gives us arithmetic. Over what is the XML Query Algebra closed? Nobody has ever given me an answer that makes sense (apart from the occasional, honest "I don't know")."
<<<< end <<<<

Here I'm really confused. On the one hand, there is a stream of papers about XPath, etc. On the other hand, Hugh seem to imply that those really don't make any sence.

hidders_at_hcoss.uia.ac.be (Jan.Hidders) wrote in message news:<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
Received on Tue Aug 06 2002 - 01:22:36 CEST