- From: Michael Kay <mhk@mhk.me.uk>
- Date: Sun, 11 Dec 2005 15:53:40 -0000
- To: "'L.G. Meredith'" <lgreg.meredith@gmail.com>, "'Michael Dyck'" <jmdyck@ibiblio.org>
- Cc: <www-ql@w3.org>
- Message-ID: <E1ElTWU-0004UH-7j@maggie.w3.org>

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 http://www.saxonica.com/ _____ From: www-ql-request@w3.org [mailto:www-ql-request@w3.org] On Behalf Of L.G. Meredith Sent: 10 December 2005 23:23 To: Michael Dyck Cc: www-ql@w3.org Subject: Re: Fwd: [bdbxml] xquery puzzle 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 <jmdyck@ibiblio.org> wrote: "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( input-set ): element coll { foo( input-set, (), () ) } function foo( remaining-input, p1s_so_far, p2s_so_far ): if remaining-input is empty: element coll { element coll {p1s_so_far}, element coll {p2s_so_far} } else let h := head(remaining-input), t := tail(remaining-input) 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

Received on Sunday, 11 December 2005 15:54:10 UTC