Re: [xml-dev] The limitations of XPath and navigation for XML databasepr

[noah_mendelsohn@us.ibm.com]

Jonthan Robie wrote:

> Clearly, /a/b/c can be given a procedural interpretation (startwith the 
> top of the document, go down to the a element, etc) or a declarative 
> interpretation

Yes, though the procedural (I prefer to say declarative) interpretation is 
likely to result in a subtly different language.  The declarative XPath 
interpretation doesn't say anything about which nodes to visit first in 
assembling the answer; an impertive specification likely would.

I used as an example in an earlier email:

>         result = new ListOfElements;
>         r = root();
>       // Go through all children of root
>         for (i=0; i<r.length(); i++) {
>         hopingForA = r.getNextChild();
>         if (hopingForA == "A")
>          // for all A children of root
>          for (j=0; j<hopingForA.length(); j++) {
>            hopingForB = hopingForA.getNextChild();
>              if (hopingForB == "B")
>              // for all elements matching /A/B
>              for (k=0; k<hopingForB.length(); k++) {
>                hopingForC = hopingForB.getNextChild();
>                  if (hopingForC == "C")
>                     // found an /A/B/C
>                     result.append(hopingForC);
>              }
> 
>          }
>         }
>       return result;

The above code pretty much can't be given a declarative implementation, 
and that highlights the difference between languages that are inherently 
declarative and those that are declarative.  There are typically 
declarative steps that will produce the same result as some declarative 
specification (except that the declarative interpretation tends to 
constrain you to doing things in a certain order, and if that's visible 
from the outside, e.g. due to when faults are reported, then you really do 
have a different language.)  Conversely, as shown immediately above, when 
you have a language that's inherently declarative there typically isn't an 
easy mapping to a declarative equivalent. 

XPath is declarative.  The order of evaluation isn't specified.  SQL is 
declarative.  The order of evaluation isn't specified.  COBOL and Java are 
imperative or if you prefer procedural:  those languages are fundamentally 
specified in terms of a time-ordered sequence of steps.  Any optimizations 
you do must produce output that's the same is if the steps had been 
performed in the order stated.  You could invent procedural languages that 
would include the syntax /A/B/C and would in that case produce output the 
same as XPath.  If you weren't very, very careful, they would also have 
externally visible side effects of having specified the order in which the 
work was done, and those would make the languages different from XPath 
after all.

Noah

--------------------------------------
Noah Mendelsohn 
IBM Corporation
One Rogers Street
Cambridge, MA 02142
1-617-693-4036
--------------------------------------