DDO SXPath

Abstract: DDO SXPath is the SXPath implementation that enables the optimized evaluation of XPath and sxpath expressions for SXML documents. DDO stands for Distinct Document Order — the primary optimization method performed, that sorts nodes in a nodeset in document order and removes duplicate nodes. Additional optimization methods are implemented that guarantee the polynomial execution time for an arbitrary XPath expression and arbitrary SXML document.

1  Motivation

Experiments conducted in [1] revealed that XPath expression evaluation in several popular XPath processors required time exponential in the size of expressions in the worst case. The paper reveals that the straightforward approach to an XPath implementation leads to an exponential time complexity of the implementation obtained thus.

The main 2 aspects leading to exponential time complexity are revealed:

• the growing nodeset size due to duplicate nodes occuring during evaluation of intermediate XPath location steps;
• deeply nested XPath predicates are evaluated for multiple times for a single value of context, i.e. a single combination of (context-node, context-position, context-size).

DDO SXPath is the solution for overcoming the above negative aspects and for providing the polynomial XPath and sxpath evaluator for SXML documents.

2  Optimizations performed

The main following kinds of optimization methods are designed and implemented in DDO SXPath:

• All XPath axes are implemented to keep a nodeset in distinct document order (DDO). Some of the techniques suggested in [2] and [3] have been elaborated here. An axis can now be considered as a converter: nodeset_in_DDO --> nodeset_in_DDO ;
• Type inference for XPath expressions allows determining whether a predicate involves context-position implicitly;
• Faster evaluation for particular kinds of XPath predicates that involve context-position, like: [position() > number] or [number];
• Sort-merge join and radix-sort join algorithms are implemented for XPath EqualityComparison of two nodesets;
• Deeply nested XPath predicates are revealed statically and are evaluated at the very beginning of the evaluation phase, to guarantee that the evaluation of deeply nested predicates is performed no more than once for each value of the context;
• Deeply nested XPath predicates are evaluated lazily and are thus actually evaluated for the necessary values of context only;
• UnionExpr is evaluated in linear time of the nodeset size, distinct document order of the unioned nodeset is supported;
• Access to XPath variables in constant time is provided;
• A practical combination of location steps "//para" is rewritten into "descendant::para" where appropriate, to speed up its evaluation;
• Evaluation of AbsoluteLocationPath is placed outside the predicates, and is thus removed outside the cycle of potentially multiple predicate evaluations.

3  Experiments

(This section is currently under reconstruction).

Here you can find the experimental results of comparing DDO SXPath with the other popular XPath processors.

4  API

The API of DDO SXPath is compatible with that of conventional SXPath. For a detailed description of conventional SXPath API you can follow this link.

DDO SXPath API functions are dealing with XPath expressions which may be represented in a textual form compatible with W3C XPath recommendation ("textual" SXPath):

(ddo:txpath "table/tr[3]/td/@align")

or as a list of steps in the location path ("native" SXPath):

(ddo:sxpath '(table (tr 3) td @ align))

It is possible to combine "native" and "textual" location paths and location step functions in one query, constructing an arbitrary XML query far beyond capabilities of XPath. For example, the query

(ddo:sxpath `("document/chapter[3]" ,relevant-links @ author))

makes a use of location step function relevant-links which implements an arbitrary algorithm in Scheme. Moreover, provided that relevant-links returns its result in distinct document order, the result of the complete expression is guaranteed to be in distinct document order as well.

5  License

This software is in Public Domain except for the HtmlPrag included into some packages. HtmlPrag implies the GNU Lesser General Public License.

6  Download

DDO SXPath is included into SSAX-SXML package.
To download the package, go to the Download page.

References

[1]

Gottlob G., Koch Ch., Pichler R. Efficient Algorithms for Processing XPath Queries : Proc. 28th Int. Conf. on Very Large Data Bases (VLDB’2002), Hong Kong, China, 20-23 Aug., 2002 // VLDB. – Morgan Kaufmann, 2002. – pp. 95-106.
http://www.dbai.tuwien.ac.at/research/xmltaskforce/vldb2002.pdf

[2]

Helmer S., Kanne C.-Ch., Moerkotte G. Optimized Translation of XPath into Algebraic Expressions Parameterized by Programs Containing Navigational Primitives : Proc. 3rd Int. conf. on Web Information Systems Engineering (WISE), Singapore, 12-14 December, 2002 // WISE. – IEEE CS Press, 2002. – pp. 215-224.
http://pi3.informatik.uni-mannheim.de/publications/TR-02-011.pdf

[3]

Kay M. XSLT and XPath Optimization : Proc. conf. XML Europe, Amsterdam, Netherlands, 18-21 Apr., 2004.
http://idealliance.org/papers/dx_xmle04/papers/02-03-02/02-03-02.pdf

Back to XML-Functional page

This document was translated from L^AT_EX by H^EV^EA.