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