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:

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:

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 LATEX by HEVEA.