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