All,
Suppose we have two predicates, p1, p2, holding of collections of elements and we have a collection, <coll><e0/>...<en/></coll>. Is it possible to write an xquery that returns all the splittings of the collection such that the collection of the left part of the split satisfies p1 and the collection of the right part of the split satisfies p2. So, if we name the function with the semantics of xquery we seek, decompose, then we have decompose(p1,p2,<coll><e0/>...<en/></coll>) = <coll> <coll> <coll><ei0/>...<eim0/></coll> <coll><ej0/>...<ejn0/></coll> </coll> ... <coll> <coll><eiN/>...<eimN/></coll> <coll><ejN/>...<ejnN/></coll> </coll> </coll> each element of the outermost collection is a pair of collections such that 1. the total set of elements of the pair unions to the original collection, e.g. <coll><ei0/>...<eim0/></coll> U <coll><ej0/>...<ejn0/></coll> = <coll><e0/>...<en/></coll> (ignoring order) 2. the pairs are disjoint, e.g. <coll><ei0/>...<eim0/></coll> /\ <coll><ej0/>...<ejn0/></coll> = <coll/> (the empty collection) 3. the first part of the pair satisfies the predicate p1 and the second satisfies p2; e.g. <coll><ei0/>...<eim0/></coll> satisfies p1; and <coll><ej0/>...<ejn0/></coll> satisfies p2. i'm not worried about complexity, right now. i expect it to be horrible. But i am worried about doing this in `memory' as opposed to in `the db'. If i have to drag everything into memory, then i may well write my own query language that has this sort of thing as a primitive. Best wishes, greg  To remove yourself from this list, send an email to [hidden email]  L.G. Meredith 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 
Suppose we have two predicates, p1, p2, holding of collections of elements and we have a collection, <coll><e0/>...<en/></coll>. Is it possible to write an xquery that returns all the splittings of the collection such that the collection of the left part of the split satisfies p1 and the collection of the right part of the split satisfies p2. So, if we name the function with the semantics of xquery we seek, decompose, then we have decompose(p1,p2,<coll><e0/>...<en/></coll>) Firstly, XQuery does not support higherorder functions:
predicates therefore cannot be passed as arguments to a
function.
Secondly, it looks to me as if <coll> is an element,
not a collection of elements.
You seem to be talking about operations like "union" in a
way that has no relationship to the XQuery operator of the same
name.
Michael Kay
http://www.saxonica.com/
=
<coll> <coll> <coll><ei0/>...<eim0/></coll> <coll><ej0/>...<ejn0/></coll> </coll> ... <coll> <coll><eiN/>...<eimN/></coll> <coll><ejN/>...<ejnN/></coll> </coll> </coll> each element of the outermost collection is a pair of collections such that 1. the total set of elements of the pair unions to the original collection, e.g. <coll><ei0/>...<eim0/></coll> U <coll><ej0/>...<ejn0/></coll> = <coll><e0/>...<en/></coll> (ignoring order) 2. the pairs are disjoint, e.g. <coll><ei0/>...<eim0/></coll> /\ <coll><ej0/>...<ejn0/></coll> = <coll/> (the empty collection) 3. the first part of the pair satisfies the predicate p1 and the second satisfies p2; e.g. <coll><ei0/>...<eim0/></coll> satisfies p1; and <coll><ej0/>...<ejn0/></coll> satisfies p2. i'm not worried about complexity, right now. i expect it to be horrible. But i am worried about doing this in `memory' as opposed to in `the db'. If i have to drag everything into memory, then i may well write my own query language that has this sort of thing as a primitive. Best wishes, greg  To remove yourself from this list, send an email to [hidden email]  L.G. Meredith 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 
Michael,
Thanks for your reply. i'm sure there will be some clarification of language between XQuery experts and myself. i'm attempting to specify the semantics of the query, rather than write the query, because i don't know if it can be written in XQuery. As for your other points, let me clarify them here. 1. Support for higherorder functions. The semantic specification i put forward does not require higherorder functionality. i didn't say that the predicates p1 and p2 will necessarily vary. For purposes of discussion, we are free to consider them fixed and that there are XQuery representations that correspond to them. Denote them [ p_i ]_X, 1<= i <= 2. The query i seek is free to make inline use of [ p_i ]_X in its computation, rather than have to take them as arguments. More generally, if we assume that we are guaranteed that [ p_i ]_X exists for all the predicate pairs p_i we want to consider, then we may think of writing a compiler that takes as input p_i and generates different queries of the type i seek for each pair. 2. Coll be an element or a collection. Surely XSD supports a schema of the form <xs:complexType name="Coll"> <xs:sequence minOccurs="0" maxOccurs="unbounded"> <xs:choice> <xs:element name="e" type="E"/> <xs:element name="coll" type="Coll"/> </xs:choice> </xs:sequence> </xs:complexType> Allowing elements that are collections and contained in collections. 3. In the specification of the semantics of the desired query, i am indeed talking about set union  not the XQuery function. Again, i am attempting to pose a semantics  in a form understandable by all and a language somewhat independent of XQuery  and ascertain whether that semantics may be realized, i.e. implemented, in XQuery. Thanks for your comments. They raise useful points of clarifications. Best wishes, greg On 12/10/05, Michael Kay <[hidden email]> wrote:
 L.G. Meredith 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 
In reply to this post by Meredith Gregory
"L.G. Meredith" wrote: > > each element of the outermost collection is a pair of collections such > that > > 1. the total set of elements of the pair unions to the original > collection, e.g. > <coll><ei0/>...<eim0/></coll> U <coll><ej0/>...<ejn0/></coll> > = <coll><e0/>...<en/></coll> (ignoring order) > 2. the pairs are disjoint, e.g. > <coll><ei0/>...<eim0/></coll> /\ <coll><ej0/>...<ejn0/></coll> = > <coll/> (the empty collection) > 3. the first part of the pair satisfies the predicate p1 and the > second satisfies p2; e.g. > <coll><ei0/>...<eim0/></coll> satisfies p1; and > <coll><ej0/>...<ejn0/></coll> satisfies p2. So, just to clarify:  If some ei in the input collection satisfies neither p1 nor p2, the result will be an empty collection.  If k elements in the input collection satisfy both p1 and p2, the result will have 2^k pairs (since each of those elements can appear in either part of each pair, and you want all distinct combinations). If so, here's some pseudocode: function decompose( inputset ): element coll { foo( inputset, (), () ) } function foo( remaininginput, p1s_so_far, p2s_so_far ): if remaininginput is empty: element coll { element coll {p1s_so_far}, element coll {p2s_so_far} } else let h := head(remaininginput), t := tail(remaininginput) return if p1(h): foo( t, p1s_so_far + h, p2s_so_far ) else: () , if p2(h): foo( t, p1s_so_far, p2s_so_far + h ) else: () It should be fairly straightforward to translate that to proper XQuery. Michael 
Michael,
Thanks for taking a whack at it. But, there was a slight misunderstanding. The predicates hold of a (sub)collection  not of an element. That is, a predicate p_i will have type p_i : Coll > bool, not p_i: E > bool, where Coll is the type of coll and E is the type of e. Additionally, it will almost never be the case that p_i is the pointwise lifting of some predicate q:E > bool. So, this solution will not work. Best wishes, greg On 12/10/05, Michael Dyck <[hidden email]> wrote:
 L.G. Meredith 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 
"L.G. Meredith" wrote: > > Michael, > > Thanks for taking a whack at it. But, there was a slight > misunderstanding. The predicates hold of a (sub)collection  not of > an element. Ah, right. Well, that should be even easier: function decompose( inputset ): element coll { for bipartition in bipartitions( inputset, (), () ) where p1(bipartition/coll[0]) and p2(bipartition/coll[1]) return bipartition } function bipartitions( remaininginput, part1_so_far, part2_so_far ): if remaininginput is empty: element coll { element coll {part1_so_far}, element coll {part2_so_far} } else let h := head(remaininginput), t := tail(remaininginput) return ( bipartitions( t, part1_so_far + h, part2_so_far ) , bipartitions( t, part1_so_far, part2_so_far + h ) ) Or, you could push the "p1 and p2" test into bipartitions(); it would make the latter ungeneric, but it might save space, depending on the XQuery implementation. Michael > function decompose( inputset ): > element coll { foo( inputset, (), () ) } > function foo( remaininginput, p1s_so_far, p2s_so_far ): > if remaininginput is empty: > element coll { > element coll {p1s_so_far}, > element coll {p2s_so_far} > } > else > let h := head(remaininginput), t := > tail(remaininginput) > return > if p1(h): foo( t, p1s_so_far + h, p2s_so_far ) else: > () > , > if p2(h): foo( t, p1s_so_far, p2s_so_far + h ) else: > () > > It should be fairly straightforward to translate that to > proper XQuery. > > Michael > >  > L.G. Meredith > > 505 N 72nd St > Seattle, WA 98103 > > +1 206.650.3740 
Michael,
Thanks. i will look over you solution careful. Specifically, i will run it through the formal semantics by hand to see if i can convince myself that it works. Best wishes, greg On 12/10/05, Michael Dyck <[hidden email]> wrote:
 L.G. Meredith 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 
In reply to this post by Meredith Gregory
I think we're going to have great difficulty helping you
with this if you continue to use terms like "collection", "predicate", and
"union" in senses different from the meanings of these terms as
used in XQuery. I simply have no confidence that I understand the
problem.
Michael Kay

Michael Kay,
As i said to Michael Dyck, it appears that his second solution is correct. i am in the process of checking it against the formal semantics, by hand. It did appear, however, that Michael Dyck got the gist of what i was saying. i agree that it's a tricky business trying to find a common language. If you stick only to XQuery meanings of common terms, it makes it difficult for people from the outside to make contact with XQuery. On the other hand, if one uses meanings of common terms that make little sense to the XQuery community, it's difficult to make contact as well. i tried to straddle the gap by using the common meanings from mathematics. Fortunately, there are people like Michael who have enough of both domains to help me bridge the gap into the XQuery world. Best wishes, greg On 12/11/05, Michael Kay <[hidden email]> wrote:
 L.G. Meredith 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 
Free forum by Nabble  Edit this page 