Re: Fwd: [bdbxml] xquery puzzle

"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

Received on Saturday, 10 December 2005 22:49:57 UTC