Fwd: [bdbxml] xquery puzzle

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Fwd: [bdbxml] xquery puzzle

Meredith Gregory
All,

Suppose we have two predicates, p1, p2, holding of collections of elements and
we have a collection, <coll><e0/>...<en/></coll>. Is it possible to write an
xquery that returns all the splittings of the collection such that the
collection of the left part of the split satisfies p1 and the collection of the
right part of the split satisfies p2. So, if we name the function with the
semantics of xquery we seek, decompose, then we have

decompose(p1,p2,<coll><e0/>...<en/></coll>) =

<coll>
    <coll>
       <coll><ei0/>...<eim0/></coll>
       <coll><ej0/>...<ejn0/></coll>
    </coll>
    ...
    <coll>
       <coll><eiN/>...<eimN/></coll>
       <coll><ejN/>...<ejnN/></coll>
    </coll>
</coll>

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.

i'm not worried about complexity, right now. i expect it to be horrible. But i
am worried about doing this in `memory' as opposed to in `the db'. If i have to
drag everything into memory, then i may well write my own query language that
has this sort of thing as a primitive.

Best wishes,

--greg



------------------------------------------
To remove yourself from this list, send an
email to [hidden email]



--
L.G. Meredith

505 N 72nd St
Seattle, WA 98103

+1 206.650.3740
Reply | Threaded
Open this post in threaded view
|

RE: [bdbxml] xquery puzzle

Michael Kay-3

Suppose we have two predicates, p1, p2, holding of collections of elements and
we have a collection, <coll><e0/>...<en/></coll>. Is it possible to write an
xquery that returns all the splittings of the collection such that the
collection of the left part of the split satisfies p1 and the collection of the
right part of the split satisfies p2. So, if we name the function with the
semantics of xquery we seek, decompose, then we have

decompose(p1,p2,<coll><e0/>...<en/></coll>)  
 
Firstly, XQuery does not support higher-order functions: predicates therefore cannot be passed as arguments to a function.
 
Secondly, it looks to me as if <coll> is an element, not a collection of elements.
 
You seem to be talking about operations like "union" in a way that has no relationship to the XQuery operator of the same name.
 
Michael Kay
http://www.saxonica.com/
 
 =

<coll>
    <coll>
       <coll><ei0/>...<eim0/></coll>
       <coll><ej0/>...<ejn0/></coll>
    </coll>
    ...
    <coll>
       <coll><eiN/>...<eimN/></coll>
       <coll><ejN/>...<ejnN/></coll>
    </coll>
</coll>

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.

i'm not worried about complexity, right now. i expect it to be horrible. But i
am worried about doing this in `memory' as opposed to in `the db'. If i have to
drag everything into memory, then i may well write my own query language that
has this sort of thing as a primitive.

Best wishes,

--greg



------------------------------------------
To remove yourself from this list, send an
email to [hidden email]



--
L.G. Meredith

505 N 72nd St
Seattle, WA 98103

+1 206.650.3740
Reply | Threaded
Open this post in threaded view
|

Re: [bdbxml] xquery puzzle

Meredith Gregory
Michael,

Thanks for your reply. i'm sure there will be some clarification of language between XQuery experts and myself. i'm attempting to specify the semantics of the query, rather than write the query, because i don't know if it can be written in XQuery. As for your other points, let me clarify them here.

1. Support for higher-order functions. The semantic specification i put forward does not require higher-order functionality. i didn't say that the predicates p1 and p2 will necessarily vary. For purposes of discussion, we are free to consider them fixed and that there are  XQuery representations that correspond to them. Denote them [| p_i |]_X, 1<= i <= 2. The query i seek is free to make in-line use of [| p_i |]_X in its computation, rather than have to take them as arguments. More generally, if we assume that we are guaranteed that [| p_i |]_X exists for all the predicate pairs p_i we want to consider, then we may think of writing a compiler that takes as input p_i and generates different queries of the type i seek for each pair.

2. Coll be an element or a collection. Surely XSD supports a schema of the form

<xs:complexType name="Coll">
     <xs:sequence minOccurs="0" maxOccurs="unbounded">
          <xs:choice>
               <xs:element name="e" type="E"/>
               <xs:element name="coll" type="Coll"/>
          </xs:choice>
    </xs:sequence>
</xs:complexType>

Allowing elements that are collections and contained in collections.

3. In the specification of the semantics of the desired query, i am indeed talking about set union -- not the XQuery function. Again, i am attempting to pose a semantics -- in a form understandable by all and a language somewhat independent of XQuery -- and ascertain whether that semantics may be realized, i.e. implemented, in XQuery.

Thanks for your comments. They raise useful points of clarifications.

Best wishes,

--greg

On 12/10/05, Michael Kay <[hidden email]> wrote:

Suppose we have two predicates, p1, p2, holding of collections of elements and
we have a collection, <coll><e0/>...<en/></coll>. Is it possible to write an
xquery that returns all the splittings of the collection such that the
collection of the left part of the split satisfies p1 and the collection of the
right part of the split satisfies p2. So, if we name the function with the
semantics of xquery we seek, decompose, then we have

decompose(p1,p2,<coll><e0/>...<en/></coll>)  
 
Firstly, XQuery does not support higher-order functions: predicates therefore cannot be passed as arguments to a function.
 
Secondly, it looks to me as if <coll> is an element, not a collection of elements.
 
You seem to be talking about operations like "union" in a way that has no relationship to the XQuery operator of the same name.
 
Michael Kay
<a href="http://www.saxonica.com/" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://www.saxonica.com/
 
 =

<coll>
    <coll>
       <coll><ei0/>...<eim0/></coll>
       <coll><ej0/>...<ejn0/></coll>
    </coll>
    ...
    <coll>
       <coll><eiN/>...<eimN/></coll>
       <coll><ejN/>...<ejnN/></coll>
    </coll>
</coll>

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.

i'm not worried about complexity, right now. i expect it to be horrible. But i
am worried about doing this in `memory' as opposed to in `the db'. If i have to
drag everything into memory, then i may well write my own query language that
has this sort of thing as a primitive.

Best wishes,

--greg



------------------------------------------
To remove yourself from this list, send an
email to [hidden email]



--
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
Reply | Threaded
Open this post in threaded view
|

Re: Fwd: [bdbxml] xquery puzzle

Michael Dyck
In reply to this post by Meredith Gregory

"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

Reply | Threaded
Open this post in threaded view
|

Re: Fwd: [bdbxml] xquery puzzle

Meredith Gregory
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 <[hidden email]> 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
Reply | Threaded
Open this post in threaded view
|

Re: Fwd: [bdbxml] xquery puzzle

Michael Dyck

"L.G. Meredith" wrote:
>
> 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.

Ah, right. Well, that should be even easier:

  function decompose( input-set ):
    element coll {
       for bipartition in bipartitions( input-set, (), () )
       where p1(bipartition/coll[0]) and p2(bipartition/coll[1])
       return bipartition
    }

  function bipartitions( remaining-input, part1_so_far, part2_so_far ):
    if remaining-input is empty:
       element coll {
         element coll {part1_so_far},
         element coll {part2_so_far}
       }
    else
      let h := head(remaining-input),
          t := tail(remaining-input)
      return
      (
        bipartitions( t, part1_so_far + h, part2_so_far )
        ,
        bipartitions( t, part1_so_far, part2_so_far + h )
      )

Or, you could push the "p1 and p2" test into bipartitions(); it would
make the latter un-generic, but it might save space, depending on
the XQuery implementation.

-Michael

 
   

>        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

Reply | Threaded
Open this post in threaded view
|

Re: Fwd: [bdbxml] xquery puzzle

Meredith Gregory
Michael,

Thanks. i will look over you solution careful. Specifically, i will run it through the formal semantics by hand to see if i can convince myself that it works.

Best wishes,

--greg

On 12/10/05, Michael Dyck <[hidden email]> wrote:

"L.G. Meredith" wrote:
>
> 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.

Ah, right. Well, that should be even easier:

  function decompose( input-set ):
    element coll {
       for bipartition in bipartitions( input-set, (), () )
       where p1(bipartition/coll[0]) and p2(bipartition/coll[1])
       return bipartition
    }

  function bipartitions( remaining-input, part1_so_far, part2_so_far ):
    if remaining-input is empty:
       element coll {
         element coll {part1_so_far},
         element coll {part2_so_far}
       }
    else
      let h := head(remaining-input),
          t := tail(remaining-input)
      return
      (
        bipartitions( t, part1_so_far + h, part2_so_far )
        ,
        bipartitions( t, part1_so_far, part2_so_far + h )
      )

Or, you could push the "p1 and p2" test into bipartitions(); it would
make the latter un-generic, but it might save space, depending on
the XQuery implementation.

-Michael




>        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
Reply | Threaded
Open this post in threaded view
|

RE: Fwd: [bdbxml] xquery puzzle

Michael Kay-3
In reply to this post by Meredith Gregory
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: [hidden email] [mailto:[hidden email]] On Behalf Of L.G. Meredith
Sent: 10 December 2005 23:23
To: Michael Dyck
Cc: [hidden email]
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 <[hidden email]> 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
Reply | Threaded
Open this post in threaded view
|

Re: Fwd: [bdbxml] xquery puzzle

Meredith Gregory
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 <[hidden email]> 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
<a href="http://www.saxonica.com/" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://www.saxonica.com/


From: [hidden email] [mailto:[hidden email]] On Behalf Of L.G. Meredith
Sent: 10 December 2005 23:23
To: Michael Dyck
Cc: [hidden email]
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 <[hidden email]> 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