RE: Fwd: [bdbxml] xquery puzzle

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


From: [] On Behalf Of L.G.
Sent: 10 December 2005 23:23
To: Michael Dyck
Subject: Re: Fwd: [bdbxml] xquery puzzle


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,


On 12/10/05, Michael Dyck <> 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 

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}
      let h := head(remaining-input), t := tail(remaining-input)
        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.


L.G. Meredith

505 N 72nd St
Seattle, WA 98103

+1 206.650.3740 

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