# Re: Fwd: [bdbxml] xquery puzzle

```Michael Kay,

As i said to Michael Dyck, it appears that his second solution is correct. i
am in the process of checking it against the formal semantics, by hand. It
did appear, however, that Michael Dyck got the gist of what i was saying. i
agree that it's a tricky business trying to find a common language. If you
stick only to XQuery meanings of common terms, it makes it difficult for
people from the outside to make contact with XQuery. On the other hand, if
one uses meanings of common terms that make little sense to the XQuery
community, it's difficult to make contact as well. i tried to straddle the
gap by using the common meanings from mathematics. Fortunately, there are
people like Michael who have enough of both domains to help me bridge the
gap into the XQuery world.

Best wishes,

--greg

On 12/11/05, Michael Kay <mhk@mhk.me.uk> wrote:
>
> 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
>
>

--
L.G. Meredith

505 N 72nd St
Seattle, WA 98103

+1 206.650.3740
```

Received on Monday, 12 December 2005 07:44:29 UTC