Re: DM expressing until-like queries in XPath 2.0

On Wed, Feb 04, 2004 at 03:35:41PM +0100, Jan Hidders wrote:
> Kay, Michael wrote:
> 
> >Maarten,
> >
> >Thankyou for sending this comment:
> >
> >http://lists.w3.org/Archives/Public/public-qt-comments/2003Nov/0302.html
> >
> >The joint XSL and XQuery working groups looked at this comment and the
> >subsequent correspondence at our January meeting.
> >
> >There is always going to be a class of queries that can only be
> >expressed using recursive functions (or higher-order functions, if we
> >had them). Whether or not your particular example falls into this class
> >or not isn't directly relevant to this.
> >
> FWIW, the query in question can be expressed in XPath 2.0 without higher 
> order functions. This is because you have the set difference operator in 
> XPath 2.0, viz., the except operator. There is a nice (unpublished) 
> result that says that all queries expressible in FO3 (that's first order 
> logic with only 3 variables) over a signature with the 
> ancestor-descendant relationship and a document-order relationship can 
> be expressed in XPath if you have all axes, node tests, filter 
> expressions and the set difference. So you don't even need a  
> for-expression for this query.
> 
> -- Jan Hidders
> 

In addition to the comment made by Jan the following related result:

A small addition to Core XPath (Xpath 1.0) yields that every first
order query is expressible. It is sufficient to be able to express
"until in all four directions". For instance, one can add to Core
XPath, the location step (child::n[p])+, that is, the transitive
closure of child::n[p], and similarly in the other directions. 
Then until(p,q) in the downward direction is expressible as 
(child::*[q])+/child::*[p]. Also the document order is definable in
this language. 
The first order language I consider here is in the signature with all
four basic steps, plus their transitive closures, plus unary predicates.
This result is unpublished,  presently under submission and
available from me.


Maarten Marx





-- 
***************************************************************************
Maarten Marx 	    marx@science.uva.nl     http://www.science.uva.nl/~marx

 Language and Inference Technology Group, ILLC, Universiteit van  Amsterdam
        Nieuwe Achtergracht 166, 1018 WV  Amsterdam, The Netherlands. 
      Phone: +31 20 525 2888 Mobile: 06 400 16 120 Fax: +31 20 525  2800
***************************************************************************

Received on Thursday, 5 February 2004 02:28:42 UTC