Re: [Monetdb-developers] Monetdb-developers Digest, Vol 4, Issue 13
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..
Peter
-----Original Message----- From: monetdb-developers-bounces@lists.sourceforge.net [mailto:monetdb-developers-bounces@lists.sourceforge.net] On Behalf Of monetdb-developers-request@lists.sourceforge.net Sent: Saturday, September 23, 2006 12:14 AM To: monetdb-developers@lists.sourceforge.net Subject: Monetdb-developers Digest, Vol 4, Issue 13
Send Monetdb-developers mailing list submissions to monetdb-developers@lists.sourceforge.net
To subscribe or unsubscribe via the World Wide Web, visit https://lists.sourceforge.net/lists/listinfo/monetdb-developers or, via email, send a message with subject or body 'help' to monetdb-developers-request@lists.sourceforge.net
You can reach the person managing the list at monetdb-developers-owner@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@in.tum.de Subject: [Monetdb-developers] Upcoming feature: Recursion in Pathfinder (algebra) To: monetdb-developers@lists.sourceforge.net Cc: Loredana Afanasiev lafanasi@science.uva.nl Message-ID: 20060922121103.GF11762@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
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.
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@utwente.nl] Sent: Tuesday, September 26, 2006 9:21 AM To: p.a.boncz Cc: monetdb-developers@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.
Hi all,
before this diverges and Jens can chime in, a quick clarification:
On Sep 26, 2006, 9:54 AM, p.a.boncz wrote with possible deletions:
[...] 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.
The motiviation behind 'with $v seeded by e1 recurse e2' purely stems from our desire to collaborate with the UvA people (Loredana, in particular). The construct will bring Regular XPath (search Google) to MonetDB/XQuery -- and all chances are that MonetDB/XQuery gains some visibility because Regular XPath currently is a very prominent dialect of XPath in the data integration and DB theory communities. No less, no more.
We clearly have the real ambition to do (1). And it indeed seems that a ''recursive back-end'' is required to achieve this. (But not for Regular XPath.) There is more involved, though, than ''simply'' map to the recursion feature in the back-end. We'd want to look at controlled unrolling (schema knowledge may help here) and identityfing some cases of tail recursion (presence of 'for' does not alleviate the need for tail recursion -- it's the other way around).
More on this later today?!, --Teggy -- | Prof. Dr. Torsten Grust grust@in.tum.de | | http://www-db.in.tum.de/~grust/ | | Database Systems - Technische Universität München (Germany) |
Thanks Torsten!
All clear here. I may have created the impression to be opposed to this, but my emotions are instead better summarized as surprise.
-----Original Message----- From: Torsten Grust [mailto:torsten.grust@gmail.com] Sent: Tuesday, September 26, 2006 10:05 AM To: p.a.boncz Cc: 'Maurice van Keulen'; monetdb-developers@lists.sourceforge.net Subject: Re: [Monetdb-developers] Monetdb-developers Digest, Vol 4, Issue 13
Hi all,
before this diverges and Jens can chime in, a quick clarification:
On Sep 26, 2006, 9:54 AM, p.a.boncz wrote with possible deletions:
[...] 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.
The motiviation behind 'with $v seeded by e1 recurse e2' purely stems from our desire to collaborate with the UvA people (Loredana, in particular). The construct will bring Regular XPath (search Google) to MonetDB/XQuery -- and all chances are that MonetDB/XQuery gains some visibility because Regular XPath currently is a very prominent dialect of XPath in the data integration and DB theory communities. No less, no more.
We clearly have the real ambition to do (1). And it indeed seems that a ''recursive back-end'' is required to achieve this. (But not for Regular XPath.) There is more involved, though, than ''simply'' map to the recursion feature in the back-end. We'd want to look at controlled unrolling (schema knowledge may help here) and identityfing some cases of tail recursion (presence of 'for' does not alleviate the need for tail recursion -- it's the other way around).
More on this later today?!, --Teggy -- | Prof. Dr. Torsten Grust grust@in.tum.de | | http://www-db.in.tum.de/~grust/ | | Database Systems - Technische Universität München (Germany) |
participants (3)
-
Maurice van Keulen -
p.a.boncz -
Torsten Grust