Subject: Computational complexity of XSL processing From: korolkm@xxxxxxxxxxxxxxxxxxxx Date: Mon, 22 Feb 1999 11:02:22 +0300 |
Hi, The question is about computational complexity of XSL processing. I have not seen any information or even hints on this subject. Nevertheless understanding of this issue is vital. Probably I do not know about some information source or have missed a valuable discussion in the past, but still: - What is the penalty for processing of different XSL language constructs? - To which extent complexity of XSL processing depends on processor implementation, to which extent it is inherent to the language itself? - What is complexity of first application of a stylesheet to an unparsed XML document? How could a gain of preprocessing an XML document be estimated? For example, will application of the following template <xsl:template match="section[@title='Some sub-section']> ... do something ... </xsl:template> to a DOM tree of an XML document will be as complex as N or even NlnN (here N is a number of nodes in the document)? Will to the contrary application of something like the following: <xsl:for-each select="/book/section[@title='First-level subsection 1']/ section[@title='Some sub-section']"> ... do something ... </xsl:template> be as complex as lnN? Will some preprocessing of the input document (like building an index of all nodes) improve situation in the first example down to lnN? Is it possible that any improvements to a processor will make complexity of the second example depend not on number of nodes in a document but just on length of "select" string? My present understanding of complexity of XSL processing pressures me to move from nicely declarative constructs like that in my first example to dangerously procedural ones like in the second example. This can spoil the good idea of making XSL a declarative language. From the other hand efforts of processor developers could probably diminish this complexity gap between declarative and procedural constructs. From the next hand these efforts will make XSL processors to be tightly integrated with XML processors and will reduce openness of XML processing tools in general. From the final hand future "DOM level 3" could introduce standard interface to indexes and other efficiency-boosting technologies, and save the future of XML/XSL. These are just my fantasies. Could somebody tell what is an actual situation with computational complexity in XSL world? Thanks Michael XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: XTech '99 starts in two weeks, Paul Prescod | Thread | RE: Computational complexity of XSL, Gavin Thomas Nicol |
XTech '99 starts in two weeks, Jon Bosak | Date | Re: CSS/XML in IE5b2 - generated co, Guy_Murphy |
Month |