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.
68P05 Data structures
68P15 Database theory
68R10 Graph theory (including graph drawing) in computer science