Optimization of generalized transitive closure queries
Shahid Shafi Dar, Rakesh Agrawal, H. V. Jagadish · 2002
Two complementary techniques for optimizing generalized transitive closure queries are presented: (i) selections on paths are applied during the closure computation, so that paths that are not in the result and that are not needed to compute the result are pruned as early as possible and (ii) paths that are in the result, or needed to compute the result, are represented in a condensed form. The condensed representation holds the minimal information that is necessary for the specified label computations and selections to be performed. The combined impact of these techniques is that the number of paths generated during the closure computation and the storage required for each such path are both greatly reduced.>