[Bug 1665] New: user-defined tree navigation primitives

http://www.w3.org/Bugs/Public/show_bug.cgi?id=1665

           Summary: user-defined tree navigation primitives
           Product: XPath / XQuery / XSLT
           Version: Last Call drafts
          Platform: Macintosh
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: XQuery
        AssignedTo: chamberl@almaden.ibm.com
        ReportedBy: lafanasi@gmail.com
         QAContact: public-qt-comments@w3.org


Dear Members of W3C XQuery working group,

We have the following question/remark regarding the user-defined functions.

Q: How easy is it to define and use tree navigation primitives in XQuery?

There are very natural cases of user-defined navigation axes that
would profit, both in readability and efficiency, from the applicative nature of
the navigation paths (as opposed to the {\em iterative style} of programming
that XQuery adopted). See for example \cite{bird:exte05} that extends XPath with
linguistically motivated navigation axis.

Let's consider the following example
based on a virtual XML document called \verb|example.xml| in which all the
elements contain an attribute \verb|a| of type \verb|xs:integer|. And suppose
your application makes frequent use of queries containing a \verb|desc_a|
primitive. \verb|desc_a| applies on a context set of nodes and returns all the
descendants with the \verb|@a|-value bigger then the \verb|@a|-value of the
context node.

The following XQuery query  below describes the \verb|desc_a| primitive as a
user-defined function and applies it on a initial sequence of nodes obtained by
evaluating an abstract location path \verb|path1|. The result of evaluating the
user-defined axis step is passed as {\em
  evaluation context} to another abstract location path \verb|path2|.

\begin{verbatim}
declare function desc_a($x as element()) as element()*
{
   for $y in $x/descendant::*
   where $x/@a < $y/@a
   return $y
}

for $x in doc(example.xml)/path1
return desc_a($x)/path2

\end{verbatim}

It seems natural (and we believe, more efficient) to express this in a path-like
manner:

\begin{verbatim}
doc('example.xml')/path1/desc_a()/path2
\end{verbatim}

Here \verb|desc_a()| is the same user-defined function as above,
except we would like in this case, the evaluation results of the
\verb|path1| to be passed as the evaluation context to
\verb|desc_a()|. To achieve this it is required that the {\em dynamic
  context} applies to user-defined functions, which is not the case in
XQuery.

Now let's try to express a location path that contains the
\verb|desc_a()| primitive in the scope of a filter expression.

\begin{verbatim}
doc('example.xml')/path1[desc_a()]
\end{verbatim}

We cope with this query in XQuery for example, using the
\ver|for-where| expression.

\begin{verbatim}
for $x in doc('example.xml')/path1
where exists(desc_a($x))
return $x
\end{verbatim}

This example might not convince you that XQuery should allow for
user-defined navigational axes, but our concern here is the
compositionality of the approach above. What happens in case we want to express
a location path that contains \verb|desc_a()| primitive in the scope of a nested
filter expression, like the example below.  We believe that the pseudo XPath
query below requires effort both to
express it in XQuery and also to interpret it  afterwards.

\begin{verbatim}
doc('example.xml')/path1[path2/desc_a()[path3/desc_a()/@a = 10]]
\end{verbatim}

We would appreciate your comments on this issue.

Best regards,
Loredana Afanasiev 
Maarten Marx

----
References:

@InProceedings{bird:exte05,
  author =          {S. Bird and  Y. Chen and  S. Davidson and
                  H. Lee   and Y. Zheng},
  title =          {Extending {XPath} to Support Linguistic Queries}, booktitle
=          {Proceedings of Programming Language
Technologies for XML (PLANX)},
  pages =         {35-46},
  year =         2005
}

Received on Saturday, 16 July 2005 16:18:10 UTC