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

p.a.boncz p.a.boncz at chello.nl
Mon Sep 25 16:02:34 CEST 2006

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?

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.

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

Defining myself as an engineer, I am aware of the limitations of my
knowledge and understanding of such formal issues.

ready to be educated..


-----Original Message-----
From: monetdb-developers-bounces at lists.sourceforge.net
[mailto:monetdb-developers-bounces at lists.sourceforge.net] On Behalf Of
monetdb-developers-request at lists.sourceforge.net
Sent: Saturday, September 23, 2006 12:14 AM
To: monetdb-developers at lists.sourceforge.net
Subject: Monetdb-developers Digest, Vol 4, Issue 13

Send Monetdb-developers mailing list submissions to
	monetdb-developers at lists.sourceforge.net

To subscribe or unsubscribe via the World Wide Web, visit
or, via email, send a message with subject or body 'help' to
	monetdb-developers-request at lists.sourceforge.net

You can reach the person managing the list at
	monetdb-developers-owner at lists.sourceforge.net

When replying, please edit your Subject line so it is more specific
than "Re: Contents of Monetdb-developers digest..."

Today's Topics:

   1. Upcoming feature: Recursion in Pathfinder	(algebra) (Jens Teubner)
   2. configure & *_config.h include files (Stefan Manegold)
   3. Re: configure & *_config.h include files (Stefan Manegold)
   4. Error with the Java Client (Jim Foley)
   5. Re: Error with the Java Client (Fabian Groffen)


Message: 1
Date: Fri, 22 Sep 2006 14:11:03 +0200
From: Jens Teubner <jens.teubner at in.tum.de>
Subject: [Monetdb-developers] Upcoming feature: Recursion in
	Pathfinder	(algebra)
To: monetdb-developers at lists.sourceforge.net
Cc: Loredana Afanasiev <lafanasi at science.uva.nl>
	<20060922121103.GF11762 at notekemper14.informatik.tu-muenchen.de>
Content-Type: text/plain; charset=us-ascii

Hi all,

this is to keep you informed what we are currently working on in Munich.

Pathfinder's purely relational approach so far cannot handle *recursion*
in XQuery expression in a sensible way (recursion in the W3C XQuery
language is possible by means of user-defined recursive function).  The
milprint_summer branch includes some hacky implementation (with help of
MIL PROCs) that provides recursion nevertheless.

Together with people from UVA (Loredana Afanasiev in particular), we are
currently working on support for recursion in an algebraic manner.

A generic handling of recursion seems quite difficult.  The W3C XQuery
language syntax does not pose any restrictions on the style of recursion
that can be described.  The common approaches to deal with recursion in
relational systems, in contrast, cannot cope with all these variants of
recursion.  A second problem is that the kind of recursion used in a
given query (e.g., tail recursion) used in a given query seems quite
tricky to infer (and a consistent treatment of this case in the
algebraic compiler adds another challenge).

Hence, we decided to go for a limited recursion feature in Pathfinder
first.  We may later on try to add a more generic handling.  We are
currently implementing a *syntax extension* to Pathfinder that allows to
describe a limited notion of recursion.  The new construct

  with $var seeded by expr1 recurse expr2

will have the following semantics:

 1. expr1 is evaluated once and then used as a seed to initiate the
    recursion.  $var is bound to the result of expr1 in the first
    recursion step.

 2. Then, expr2 is evaluated over and over.  Variable $var is visible
    in expr2 and for each recursion step will be bound to the union of
    all items (nodes) obtained in the previous recursion steps.  (The
    results of all recursion steps are collected into the overall result
    using set semantics.)

 3. Recursion terminates if a recursion step does not contribute any new
    items (nodes) to the overall result (i.e., we reached a fixpoint).

(Remark: There still is some discussion if (for performance reasons)
each recursion step should only observe the *new* items obtained in the
previous recursion step, or whether the entire result set collected so
far should be observable in expr2.)

The `union' semantics of this new recursion construct implies that we
can do recursion only on *nodes*, not on atomic values.  This quite
directly matches the requirements of the UVA group (and others) that are
looking for a "transitive closure" operator.

Note that the above syntax extension that we are about to introduce does
not interfere with any existing constructs.  So our changes will not
affect any (existing) valid XQuery expression.

Motivation: There is a high demand for transitive closure functionality
in the group at UVA (i.e., Loredana and others), but also in other
research groups (as I was told).  Transitive closure is, e.g., a vital
component of an XPath dialect known as "Regular XPath".

Regards from Garching


Jens Teubner
Technische Universitaet Muenchen, Department of Informatics
D-85748 Garching, Germany
Tel: +49 89 289-17259     Fax: +49 89 289-17263

Software is like sex: It's better when it's free
                               -- Linus B. Torvalds

More information about the developers-list mailing list