W3C home > Mailing lists > Public > www-ql@w3.org > October to December 2005

Re: [bdbxml] xquery puzzle

From: L.G. Meredith <lgreg.meredith@gmail.com>
Date: Sat, 10 Dec 2005 13:14:53 -0800
Message-ID: <5de3f5ca0512101314v7d15fe2esfd1ed1ebb3867e70@mail.gmail.com>
To: Michael Kay <mhk@mhk.me.uk>
Cc: www-ql@w3.org
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 <mhk@mhk.me.uk> 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
> 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 xml-unsubscribe@sleepycat.com
>
>
>
> --
> 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 Saturday, 10 December 2005 21:15:04 UTC

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