Introduction to Sequential XPath

1. Introduction

This paper will provide an explanation of and the subset of XPath which we will tentatively dub: Sequential XPath, or SXPath for ease of use. SXPath allows a event-based XML parser, such as a typical SAX-compliant XML parser, to execute XPath-like expressions without the need of more memory consumption than is normally used within a sequential parser.

2. Issues with XPath

During the conception of XPath, usage typical scenarios assumed random access to XML data. However, in real-world usage, it was quickly realized that the necessity of random access to the XML data was unnecessary and was a major performance inhibitor, as proven by the success of SAX-like parsers. The vast majority of XPath processors require the XML data to be contained in a DOM in order to queries against it. The few parsers which do not necessitate DOM-like storage are a bit more efficient than using a DOM, but still have the potential of buffering large segments of the XML document. By removing portions of the XPath language which require buffering we can enable processing within an event-based parser.

Another issue with XPath, for lack of a better term, is "random times". Simply stated: the ability to query XML data at any time while it is contained in a DOM. Obviously keeping a DOM in memory allows for flexible implementations in the query process, but results in memory usage which could be avoided had the queries been known prior to parsing the document. By removing the ability of random time processing, we can keep memory usage to the absolute minimum for a given query.

3. Inherent Nature of SXPath

By removing random access and random time processing from the standard XPath model, we yield a method of querying which an event-based parser can utilize without buffering portions of the XML document. Since there is no buffering, we essentially guarantee a “best possible” case of memory usage. Performance should also increase compared to standard parsers since there is no need to build the DOM, or similar memory structure, on one pass and then execute XPath queries on subsequent passes.1

The simplest definition/explanation for SXPath is that it is the subset of XPath which allows for queries which allow for a determination within a streaming document whether a given node is a match for the query and allows for the expulsion of needless buffering of the past and current nodes. What does this mean in lament’s terms?

1. SXPath expression is provided prior to parsing.

   This allows for a simple grammar to define valid SXPaths. If expressions were allowed during parsing of the document(as in random time), certain SXPaths would be valid at certain times and not at other times. Additionally, this allows a compiler to optimize itself prior to the onset of processing, allowing SXPath processing to have minimal impact compared to a standard event-based parser.

2. At each parser atom, SXPath filter should be able to determine without forward lookup, if an atom maps to some selected node, or not.

   This simply states that when we get any given node, we have to know if we match with an SXPath expression. We can’t buffer the current node and peek forward to see if the current node matches a query. This ensures that we’re following similar conventions compared to a standalone reader.

3. Memory consumption should be linear to the deepness of the tree/SXPath expression or better.

   Basically this means that a minimal amount of data will be buffered. This is more than a parser notice that the SXPath grammar has no need for buffered data. At most we will be simple metadata on the ancestors of the current node, not the actual ancestor nodes themselves.

4. Usage Scenarios

Let’s take a simple SOAP message for example. As we already know, SOAP is the standard for XML webservices so simplifying the processing of SOAP messages will be a tremendous boon for developers.

There are two practical ways of extracting data from a SOAP message. The first way is to load the SOAP message into a DOM-based processor. Extracting data using this method is easy to accomplish via XPath or programmatically; however, constantly building DOMs will not yield good performance when running a high volume webservice. Your other option is using an existing event-based parser and writing your own custom code to process the SOAP messages. What you gain in performance compared to the DOM, you lose in flexibility(changes in existing SOAP messages & addition of new SOAP messages) and development time.

Using an SXPath-enabled parser, you could simply have SXPath expressions which extract the necessary data out of the body of the SOAP message. The ease in adaptability is easy to see. For a change in the structure of a SOAP message, all one would have to do is change the SXPath expression they are searching for rather than rewrite state logic when using a customized reader. And since we still are a sequential reader, we continue to maintain a large performance benefit when compared to using the DOM.

On the opposite end of the spectrum, let’s use a large XML document as an example. Suppose you have an XML document which contains hundreds of purchase orders. This document is potentially going to be several megabytes in size. Loading this document into the DOM to extract information on specific orders would result in a major performance hit for such a trivial procedure. Once again, the ideal answer is something which gives us the speed of event-based parsers with the data extraction ease of the DOM.

5. Sequential XPath Functionality and Axes

There are several changes to the standard XPath grammar, but the biggest change is the restriction in the usage of axes. Now, certain axes are valid in the predicate while other axes are valid only in the non-predicate portion of the SXPath expression. We have classified the axes in to three different groups.

1. Common Axes: These can be applied in both the predicate and location path due to their nature.

2. Forward Axes: These can only be applied in the location path context since they are looking for ‘future’ nodes. An example is “child’’; we can successfully select the child nodes of a given path if “child” is in the path. However, if “child” were in the predicate, we would not be able to select the current node since we cannot look ahead to its children to test the predicate expression.

3. Reverse Axis: Essentially the opposite of Forward Axes. An example would be “parent”. If parent was in the location path, we would want to return the parent of a specific node. Once again, since we cannot go backward, we cannot support this in the location path. However, in the predicate, we can test whether the node has the correct parent (this would be among the metadata collected), and successfully return the path if necessary.

Here is a table showing the current valid axes based of XPath axes:

Common Axes	attribute, namespace, self
Forward Axes	child, descendant, descendant-or-self, following, following-sibling
Reverse Axis	ancestor, ancestor-or-self, parent, preceeding, preceeding-sibling

The functional changes came about due to two inherent differences between XPath and SXPath. XPath returns node-sets whereas SXPath returns events. And SXPath’s inherent sequential nature compared to XPath’s random access.

Note: The following table reflects the changes in SXPath functionality vs. XPath functionality. All undocumented XPath functions are still valid in SXPath.

XPath Function	SXPath Version	Reason
number last()		Cannot work without buffering the entire document.
number count(node-set)		Cannot work without buffering the entire document.
string local-name(node-set?)	string local-name()	Cannot use a node-set as a parameter.
string namespace-uri(node-set?)	string namespace-uri()	Cannot use a node-set as a parameter.
string name(node-set?)	string name()	Cannot use a node-set as a parameter.
number sum(node-set)		Cannot work without buffering the entire document.

6. Sequential XPath Grammar

Following is the subset of XPath grammar for SXPath. Keep in mind, that besides syntax limitations, there will be semantics limitations, described above.

Note: The table below contains certain conditions within the grammar (Part 6), to make it easier to comprehend.

Location Paths
[1] LocationPath	RelativeLocationPath | AbsoluteLocationPath
[2] AbsoluteLocationPath	'/' RelativeLocationPath? | AbbreviatedAbsoluteLocationPath
[3] RelativeLocationPath	Step | RelativeLocationPath '/' Step | AbbreviatedRelativeLocationPath
Location Steps
[4] Step	AxisSpecifier NodeTest Predicate* | AbbreviatedStep
[5] AxisSpecifier	CommonAxisName '::' | AbbreviatedAxisSpecifier
Axes
[6] CommonAxisName	'attribute' | 'namespace' | 'self' | ForwardAxisName (Only valid if axis is in location path context) | ReverseAxisName (Only valid if axis is in predicate context)
[7] ForwardAxisName	'child' | 'descendant' | 'descendant-or-self' | 'following' | 'following-sibling'
[8] ReverseAxisName	'ancestor' | 'ancestor-or-self' | 'parent' | 'preceeding' | 'preceeding-sibling'
Node Tests
Predicates
[9] NodeTest	NameTest | NodeType '(' ')' | 'processing-instruction' '(' Literal ')'
[10] Predicate	'[' PredicateExpr ']'
[11]PredicateExpr	Expr
Abbreviations
[12] AbbreviatedAbsoluteLocationPath	'//' RelativeLocationPath
[13] AbbreviatedRelativeLocationPath	RelativeLocationPath '//' Step
[14] AbbreviatedStep	'.'
[15] AbbreviatedAxisSpecifier	'@'?
Variable References
[16] Expr	OrExpr
[17] PrimaryExpr	VariableReference | '(' Expr ')' | Literal | Number | FunctionCall
Node-Sets
[18] UnionExpr	FilterExpr | UnionExpr '|' FilterExpr
[19] FilterExpr	PrimaryExpr | FilterExpr Predicate
Function Call
[20] FunctionCall	FunctionName '(' ( Argument ( ',' Argument )* )? ')'
[21] Argument	Expr
Booleans
[22] OrExpr	AndExpr | OrExpr 'or' AndExpr
[23] AndExpr	EqualityExpr | AndExpr 'and' EqualityExpr
[24] EqualityExpr	RelationalExpr | EqualityExpr '=' RelationalExpr | EqualityExpr '!=' RelationalExpr
[25] RelationalExpr	AdditiveExpr | RelationalExpr '<' AdditiveExpr | RelationalExpr '>' AdditiveExpr | RelationalExpr '<=' AdditiveExpr | RelationalExpr '>=' AdditiveExpr
Numeric Expressions
[26] AdditiveExpr	MultiplicativeExpr | AdditiveExpr '+' MultiplicativeExpr | AdditiveExpr '-' MultiplicativeExpr
[27] MultiplicativeExpr	UnaryExpr | MultiplicativeExpr MultiplyOperator UnaryExpr | MultiplicativeExpr 'div' UnaryExpr | MultiplicativeExpr 'mod' UnaryExpr
[28] UnaryExpr	UnionExpr | '-' UnaryExpr
Expression Lexical Structure
[29] ExprToken	'(' | ')' | '[' | ']' | '.' | '@' | ',' | '::' | NameTest | NodeType | Operator | FunctionName | CommonAxisName | Literal | Number | VariableReference
[30] Literal	'"' [^"]* '"' | "'" [^']* "'"
[31] Number	Digits ('.' Digits?)? | '.' Digits
[32] Digits	[0-9]+
[33] Operator	OperatorName | MultiplyOperator | '/' | '//' | '|' | '+' | '-' | '=' | '!=' | '<' | '<=' | '>' | '>='
[34] OperatorName	'and' | 'or' | 'mod' | 'div'
[35] MultiplyOperator	'*'
[36] FunctionName	QName - NodeType
[37] VariableReference	'$' QName
[38] NameTest	'*' | NCName ':' '*' | QName
[39] NodeType	'comment' | 'text' | 'processing-instruction' | 'node'
[40] ExprWhitespace	S

7. Example

XML Data sample:

<orders>
     <order id="1">...</order>
     .
     <order id="2372">
          <name>Homer Simpson</name>
          <address1>742 Evergreen Terrace</address1>
          <address2 city="Springfield state="OH" zip="45502"/>
          <items>
               <item SKU="3" quantity="5"/>
          </items>
     </order>
     .
     <order id="54363">...</order>
</orders>

Code example:

SXPathParser parser;
XMLDocument doc;
parser.setDoc(doc);
parser.addPath("/order/@id=2372");
while(parser.scan())
{
     parser.goto("address2");
     if (parser.attribute("state").textValue == "WA")
     {
          return false;  // No sales tax will be charged
     }
     else
     {
          return true;  // Sales tax will be charged
     }
}

This simple example extracts the customer's name from a specific order. Even though

8. Conclusion

By creating a streaming XML parser which utilizes Sequential XPath, one is able to reap the inherent benefits of a streaming parser with the querying power of XPath. By defining this proper subset of XPath, we enable developers and users to utilize XML in a wide array of applications thought to be too performance sensitive for traditional XML processing.

Design and Development by deepX Ltd.