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

p.a.boncz p.a.boncz at chello.nl
Tue Sep 26 09:54:18 CEST 2006


Hi Maurice,

Thanks for your clarifications. They still leave me wondering about my
question what the goal of this proposal is.

From:
(a) the compilation limitations of recursion are well known and there is no
hope at all to eliminate recursion in the general case
(b) XQuery contains full recrsion

It follows that the only way to implement the recursion feature in XQuery is
to use an execution environment that supports recursion. Call it hacky or
not.

In case of MIL and MAL, recursion happens to be supported. Some variants of
PL/SQL (i.e. the scripted procedural language offerered by your RDBMS) also
support recursion. To be precise, such a PL/SQL must support recursive table
functions for it to be useful. 

The specific cases of XQuery recursion that can be eliminated or translated
to fixpoint notation are rare. With the set-union semantic only very very
special cases of easily recognizable functions could conceivably be
translated to fixpoint.

Thus my question to Jens what is the goal: 
(1) translation of existing XQuery recursion to fixpoint notation?
(2) provide a separate different recursive language construct in XQuery?

Contrary to what you say, this proposal is not just an internal algebraic
operator, but foremost (2) a syntax extension. So all evidence points to (2)
and the absence of a real ambition to do (1). After all, we know beforehand
that if automatic translation were attempted, it would only work for rare
cases.

On milprint-summer: I did not say it *eliminates* recursion; rather it
*reduces* the amount of calls. In recursive functions that do all recursive
calls inside the same for-loop it reduces the number of calls to one per
calling-depth.

Peter



-----Original Message-----
From: Maurice van Keulen [mailto:m.vankeulen at utwente.nl] 
Sent: Tuesday, September 26, 2006 9:21 AM
To: p.a.boncz
Cc: monetdb-developers at lists.sourceforge.net
Subject: Re: [Monetdb-developers] Monetdb-developers Digest, Vol 4, Issue 13

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,
Maurice.

-- 
----------------------------------------------------------------------
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





More information about the developers-list mailing list