Cost-Sensitive Reordering of Navigational Primitives Carl-Christian Kanne, Matthias Brantner, and Guido Moerkotte   View Paper (PDF)   Return to Graph and Tree-Structured Data (Research) Abstract We present a method to evaluate path queries based on the novel concept of partial path instances. Our method (1) maximizes performance by means of sequential scans or asynchronous I/O, (2) does not require a special storage format, (3) relies on simple navigational primitives on trees, and (4) can be complemented by existing logical and physical optimizations such as duplicate elimination, duplicate prevention and path rewriting. We use a physical algebra which separates those navigation operations that require I/O from those that do not. All I/O operations necessary for the evaluation of a path are isolated in a single operator, which may employ efficient I/O scheduling strategies such as sequential scans or asynchronous I/O. Performance results for queries from the XMark benchmark show that reordering the navigation operations can increase performance up to a factor of four. ©2006 Association for Computing Machinery