Re: Implementing trees in a relational database

In article <bdf69bdf.0208051522.32f43478_at_posting.google.com>, Mikito Harakiri <mikharakiri_at_yahoo.com> wrote:
>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.

It's a bit more subtle than that. I would argue that an algebra is a set of operators that is closed over one or more sort (there exist things like multi-sorted algebras) and whose semantics are defined by a set of algebraic equivalencies. At least that is how I see the term mostly used by mathematicians. I suspect that the relational fundamentalists don't like this definition very much because it excludes their cherished relational algebra. There the algebraic rules are derived from the set-theoretic semantics of the operators.

Now, if we look at XQuery and especially the core algebra, as they call it, then I don't think that closedness is really a problem. (Note that XPath is not what you should look at because that is just meant as a language to select certain nodes in the document tree, so it shouldn't be closed.) The result is always roughly speaking an XML fragment and the same holds for the inputs since documents are also roughly XML fragments. That this is only roughly the case is not the fault of the algebra but rather the intricacies of XML.

So the next question is: does the algebra have (derived) algebraic rule? The answer is yes, as you can read in the defining documents, so I would say that the situation is in this respect comparable to the relational algebra. There is however an important difference and that is that the XML algebra is in some sense a higher order algebra because it is more like a calculus. The problem is that this often implies certainly implementations that might nog be optimal such as nested loops for joins. That makes it less suitable for query optimization, but one could argue that for the type of applications that you would typically use it for this is probably not a big problem.

• Jan Hidders