Technology of Object-Oriented Languages and Systems
Forward vs. Reverse Traversal in Path Expression Query Processing
Melbourne, Australia
November 23-November 26
ISBN: 0-7695-0053-6
Path traversals have been recognised as one of the strengths of object-oriented query processing, as information retrieval can be achieved through pointer navigation. There are two existing path traversal methods, namely "forward" and "reverse traversal". In this paper, we analyse and compare the two traversal methods. Our results show that forward traversal is suitable for path expression queries involving selection operations on the start of the path expression, as the selection operations provide a filtering mechanism. Furthermore, redundant accesses to the associated objects may also be avoided indirectly through filtering. In contrast, reverse traversal is suitable for path expression queries involving selection operations at the end of path expression, since the problem of redundant accesses to the associated objects may be avoided. From our analysis, we formulated two lemmas on path traversals. These lemmas are anticipated to be used as a foundation for future query optimization of general path expression queries involving an arbitrary number of classes connected in relationships.
Index Terms:
Forward Traversals, Reverse Traversals, Object-Oriented Query Processing, Path Expression Queries, and Performance Evaluation.
Citation:
David Taniar, "Forward vs. Reverse Traversal in Path Expression Query Processing," tools, pp.127, Technology of Object-Oriented Languages and Systems, 1998