Querying virtual hierarchies using virtual prefix-based numbers
Curtis Dyreson, Sourav Saha Bhowmick, Ryan Grapp · 2014
Prefix-based numbering is a popular method for numbering nodes in a hierarchy. But prefix-based numbering breaks down when a node's location within a hierarchy changes, such as when XML data is queried after being transformed by an XSLT program or when data is reformatted in the return clause of an inner FLWR expression in a nested XQuery program. A query on transformed data cannot be evaluated as efficiently since the extant prefix-based node numbers cannot be used (unless the data is materialized and then renumbered, which can be expensive). In this paper we present a novel strategy to virtually transform the data without instantiating and renumbering. Our method, which we call virtual prefix-based numbering, couples each prefix-based node number with a level array that locates the node in the numbering space of the virtual hierarchy. The virtual numbering space preserves the property that location-based relationships between nodes can be determined by comparing (virtual) numbers.