Computational complexity of XSL processing

Subject: Computational complexity of XSL processing
From: korolkm@xxxxxxxxxxxxxxxxxxxx
Date: Mon, 22 Feb 1999 11:02:22 +0300

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
-	What is the penalty for processing of different XSL language
-	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

For example, will application of the following template
	<xsl:template match="section[@title='Some sub-section']>
		... do something ...
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 ...
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?



 XSL-List info and archive:

Current Thread