# zbMATH — the first resource for mathematics

Extended structural recursion and XSLT. (English) Zbl 1190.68020
Summary: We describe a simulation of a practically important fragment of XPath 1.0 and XSLT 1.0 with extended structural recursions, which in turn immediately offers us a top-down implementation strategy working in time $$O(|D|^2|Q|)$$. Here, $$|D|$$, $$|Q|$$, respectively denote the size of the data and the query. However, if the size of the variables is restricted with a constant, then the evaluation works in $$O(|D||Q|)$$ time. Structural recursions are insensitive to the order of the edges (in our XML model instead of nodes, edges represent elements); hence, in this respect, they are of a weaker expressive power than the more usual models of XML query languages. Still, a large fragment of the most frequent scenarios appearing in practice can be captured with them, which underlines their importance.
##### MSC:
 68P05 Data structures 68P15 Database theory 68R10 Graph theory (including graph drawing) in computer science
##### Keywords:
XML model; XML query languages