An extended preorder index for optimising XPath expressions
O'Connor, Martin F. and Bellahsène, Zohra and Roantree, Mark (2005) An extended preorder index for optimising XPath expressions. In: XSym 2005 - Third International XML Database Symposium, 28-29 August, 2005, Trondheim, Norway. ISBN 978-3-540-28583-0
Full text available as:
Many of the problems with native XML databases relate to
query performance and subsequently, it can be difficult to convince traditional database users of the benefits of using semi- or unstructured databases. Presently, there still lacks an index structure providing efficient support for structural queries and the traditional data-centric and
content queries. This paper presents an extended index structure based on the preorder traversal rank and the level (or depth) rank of each node in a document tree. The extended index fully supports the navigation of all XPath axes while efficiently supporting data-centric queries. The ability to start path traversals from arbitrary nodes in a document tree also enables the extended index to support the evaluation of path traversals embedded in XQuery expressions. Furthermore, an encoding technique is presented where properties of the level ranking may be exploited to provide efficient and optimised level-based XPath evaluations.
Archive Staff Only: edit this record