Augmenting databases with generalized transitive closure
Shaul Dar · Minds at UW (University of Wisconsin) · 1993
The need to compute the generalized transitive closure (GTC) of a graph arises in diverse database applications such as finding the cheapest flight sequence between two cities, or computing the bill-of-materials of a complex part; however, current database systems do not support GTC queries. We develop a framework for augmenting databases with generalized transitive closure functionality. This framework includes an algebraic model, language extensions, optimization techniques and efficient algorithms for the formulation and evaluation of GTC queries. The algebraic query model supports both path enumeration and path aggregation queries and allows selections on arcs, paths and sets of paths. The SQL/TC language extends SQL with the ability to express such queries in a declarative and concise fashion. The answer to a query may include the sequence of arcs in a path, or the aggregation of information for different paths between the same endpoints. We illustrate the expressive power of SQL/TC through many examples and contrast it with earlier proposals, including the proposed extension to ANSI/SQL. We investigate the optimization of GTC queries involving selections and label computations, and describe techniques to reduce both the number of paths generated and the space required to store these paths. We present a taxonomy of path problems based on algebraic properties of the label computation functions, and identify characteristics of transitive closure algorithms that make them suitable for solving path problems. We survey the field of transitive closure algorithms proposed in the database literature. We start with reachability algorithms and then explore how these algorithms may be extended to evaluate general and partial transitive closure queries. We perform a comprehensive performance study of reachability algorithms for the computation of the complete and partial transitive closures of large graphs. We identify the factors that influence the I/O behavior of the algorithms in this spectrum of queries. We also take a critical look at the evaluation methodology for transitive closure algorithms; we demonstrate that cost metrics based on tuple or successor list operations, used in many previous studies, cannot be reliably used to understand the performance of the algorithms when I/O cost is at a premium.