Forward vs. reverse traversal in path expression query processing

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.