An analysis technique for transitive closure algorithms: a statistical approach

A novel experimental procedure, based on a standard statistical estimation procedure, is presented to estimate the performance of transitive closure algorithms. This experimental procedure has been exemplified in three contexts: (1) comparison of a suite of algorithms: (2) analysis of one particular algorithm; and (3) analysis of the transitive closure problem itself. It is shown that the number of duplicate edges generated (by most algorithms) can be more than ten times the size of the transitive closure, even for small graphs. The majority of these duplicates are due to the existence of strongly connected components in the graph. This experimental approach can be generalized to estimate various performance metrics for a large class of database queries. It is both simple and general and provides the necessary ingredients for a guess-and-verify paradigm of testing hypotheses