×

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
PDF BibTeX XML Cite