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.
Experiments conducted in  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:
(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.
The main following kinds of optimization methods are designed and implemented in DDO SXPath:
nodeset_in_DDO --> nodeset_in_DDO;
[position() > number]or
//para" is rewritten into "
descendant::para" where appropriate, to speed up its evaluation;
(This section is currently under reconstruction).
Here you can find the experimental results of comparing DDO SXPath with the other popular XPath processors.
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):
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" ,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.
This software is in Public Domain except for the HtmlPrag included into some packages. HtmlPrag implies the GNU Lesser General Public License.
DDO SXPath is included into SSAX-SXML package.
To download the package, go to the Download page.
Back to XML-Functional page
This document was translated from LATEX by HEVEA.