# Re: Fwd: [bdbxml] xquery puzzle

From: Michael Dyck <jmdyck@ibiblio.org>
Date: Sat, 10 Dec 2005 14:49:36 -0800
Message-ID: <439B5B80.26BDB9C6@ibiblio.org>

```
"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

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 22:43:44 UTC