Forward vs. reverse traversal in path expression query processing

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publication Proceedings of the 1998 Conference on Technology of Object-Oriented Languages
PublisherIEEE, Institute of Electrical and Electronics Engineers
Pages127-140
Number of pages14
Publication statusPublished - 1998
EventProceedings of the 1998 Conference on Technology of Object-Oriented Languages - Melbourne, Australia
Duration: 23 Nov 199826 Nov 1998

Conference

ConferenceProceedings of the 1998 Conference on Technology of Object-Oriented Languages
CountryAustralia
CityMelbourne
Period23/11/9826/11/98

Cite this