[Monetdb-developers] Monetdb-developers Digest, Vol 4, Issue 13

Maurice van Keulen m.vankeulen at utwente.nl
Tue Sep 26 09:20:51 CEST 2006

Hi Peter,

I can of course wait for Jens to reply, but I guess it doesn't hurt to 
add my 2ct ...

p.a.boncz wrote:
> Hi Jens,
> I read your recursion proposal, but I do not really understand the need or
> goal for such a syntax extension:
> - is't the default XQuery function recursion more powerful? 
> - why not confine oneself to have an *internal* algebraic closure operator,
> if that is such a useful abstraction?
The idea, as I understand it, *is* to have an "internal algebraic 
closure operator" (or fixpoint operator). The problem is that XQuery 
function recursion is *too* powerful. It is an unsolved problem how to 
translate arbitrary function recursion to algebra expressions with a 
fixpoint operator. The quickest way to (1) have /some/ support for 
recursion, that (2) we know how to translate into an algebra and 
execute, is to extend the syntax with special recursion construct and 
disallow any function recursion. This is, I guess, exactly how I would 
approach it. First restrict to manageable proportions, then try to extend.
> Nor do I understand the need for the focus on nodes and set fixpoint
> semantics. If the result expression is a sequence of nodes you may define
> this to be duplicate-free and in document order, but it is less obvious why
> atomic sequences should be treated like that. Order is a first-class citizen
> in XQuery, and atomic types are also first-class. And what about element
> construction? Isn't it obvious given the recursive nature of XML that people
> may want to build XML documents with recursion -- so the choice to union all
> results always is limiting.
The restrictions on set fixpoint semantics and nodes is, I believe, to 
simply confine first to simple things that the  research community 
researched before. I believe that we first need to check what known 
techniques apply here, and only then see if we can extend these 
techniques so that they are better suitable to XQuery.
> I can imagine that *some* XQuery recursion patterns could be translated to
> this fixpoint operator. Tail recursion is the big "success story" here
> (given your node-union fixpoint semantics it will actually only be possible
> in rare cases). However, given the fact that XQuery has for-loops, it is
> quite unlikely in the first place that in the real world people will use
> tail-recursion for iteration (this may distinguish XQuery from "purer"
> functional languages). I conclude that this extension per-se does not help
> in translating recursion in XQuery for the algebra backend at all (nor is it
> its goal), rather places a second recursive vehicle beside it. 
I don't agree. The syntax extension *does* help in translating recursion 
in XQuery to the algebra backend, because it is a construct for which it 
is clear how to translate it to a fixpoint operator. "Real-world people" 
will of course want to write queries with all kinds of weird recursions 
in them. But "real-world users" will also want their queries to be 
executed. I think that with a syntax extension it is much easier for 
"real-world people" to understand what is supported and what is not. If 
they can squeeze their recursion into this syntax, it is supported. If 
they cannot, it is not supported. Otherwise, you would have to document 
which patterns are supported, supply detailed and concise error 
messages, etc. etc.
> I am completely puzzled to hear such proposals from the usually
> XQuery-standard-respecting community in Garching.
> Finally, what exactly is "hacky" about the milprint_summer recursion
> approach? Maybe you mean with "hacky" that it does not try to eliminate
> recursion, and thus only works if the target language offers recursion. The
> reality is that only trivial recursion patterns can be eliminated, so this
> limitation will apply always. And you may forget, that a lot of recursion in
> milprint_summer *is* eliminated, as all calls inside a for-loop are reduced
> to one thanks to "loop-lifting" (maybe we could even "sell" this idea in the
> FP community). So actually it surely is not as primitive/hacky as the
> implementation of recursion in say Galax.
How is /recursion/ eliminated by loop-lifting or function inlining? Any 
recursion would still remain after this, won't it?

> Defining myself as an engineer, I am aware of the limitations of my
> knowledge and understanding of such formal issues.
Let's not forget that (any variant of) SQL only has a very restricted 
form of recursion as well. Recursion in a database systems is simply an 
unsolved problem. In the context of XQuery nothing less.
> ready to be educated..
> Peter
Just my 2cts,

Dr.Ir. M. van Keulen - Assistant Professor, Data Management Technology
Univ. of Twente, Dept of EEMCS, POBox 217, 7500 AE Enschede, Netherlands
Email: m.vankeulen at utwente.nl, Phone: +31 534893688, Fax: +31 534892927
Room: INF3039, WWW: http://www.cs.utwente.nl/~keulen

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.monetdb.org/pipermail/developers-list/attachments/20060926/7fba4dee/attachment.html>

More information about the developers-list mailing list