W3C home > Mailing lists > Public > www-xml-query-comments@w3.org > February 2002

RE: 20011220 draft: indexing support?

From: Paul Cotton <pcotton@microsoft.com>
Date: Mon, 11 Feb 2002 21:25:25 -0500
Message-ID: <E7AC4500EAB7A442ABA7521D18814397028D13ED@tor-msg-01.northamerica.corp.microsoft.com>
To: "Tim Bray" <twbray@antarcti.ca>
Cc: <www-xml-query-comments@w3.org>
XPath 1.0 contained a starts-with() function and the Functions and
Operators document is proposing an ends-with() function since it was a
common request of XPath programmers.  

I don't believe you need to build an index to execute this function -
you simply have to count the number of characters in the target string
and then test if the pattern matches the end of the target string.
Admittedly this is more expensive than testing for the pattern at the
beginning of the string but certainly not impossible to execute in a
reasonable fashion without an index.

But thank you for your comments.  I will ensure they are reviewed as
part of our next update to the Functions and Operators document.

/paulc

Paul Cotton, Microsoft Canada 
17 Eleanor Drive, Nepean, Ontario K2E 6A3 
Tel: (613) 225-5445 Fax: (425) 936-7329 
<mailto:pcotton@microsoft.com> 


> -----Original Message-----
> From: Tim Bray [mailto:twbray@antarcti.ca]
> Sent: Friday, February 08, 2002 6:22 PM
> To: www-xml-query-comments@w3.org
> Subject: 20011220 draft: indexing support?
> 
> A quick scan through some of the stuff in the Functions and
> Operators draft suggests that there's an issue with indexing.
> I apologize if there is already a policy in place on this that
> I should have read, but: should XQuery worry about the ease
> or general possibility of indexing support such that queries
> in principle can be resolved in a time that is less than
> linear in the size of the dataset?
> 
> An example of this is for example is "ends-with" - I was
> actually looking at this in one of the use-cases and wondering
> how on earth I would actually implement this in a real-world
> system; a substantial proportion of content indexing systems
> just don't do (and can't be made to do) suffix matching.
> 
> More generally, the difficulty of indexing support for
> the things that show up in functions & operators is all
> over the map.  Maybe conformance levels help here?  I.e.
> is there a relatively small subset that can generally
> be expected to allow efficient indexing and thus
> sublinear performance?
> 
> Cheers, Tim Bray
Received on Monday, 11 February 2002 21:25:59 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 20:21:15 UTC