Transitive closure algorithms based on graph traversal

ABSTRACT

Several graph-based algorithms have been proposed in the literature to compute the transitive closure of a directed graph. We develop two new algorithms (Basic_TC and Gobal_DFTC) and compare the performance of their implementations in a disk-based environment with a well-known graph-based algorithm proposed by Schmitz. Our algorithms use depth-first search to traverse a graph and a technique called marking to avoid processing some of the arcs in the graph. They compute the closure by processing nodes in reverse topological order, building descendent sets by adding the descendent sets of children. While the details of these algorithms differ considerably, one important difference among them is the time at which descendent set additions are performed. Basic_TC, results in superior performance. The first reason is that early additions result in larger descendent set sizes on the average over the duration of the execution, thereby causing more I/O; very often this turns out to more than offset the gains of not having to fetch certain sets again to add them. The second reason is that information collected in the first pass can be used to apply several optimizations in the second pass. To the extent possible, we also adapt these algorithms to perform path computations. Again, our performance comparison confirms the trends seen in reachability queries. Taken in conjunction with another performance study our results indicate that all graph-based algorithms significantly outperform other types of algorithms such as Seminaive and Warren.

REFERENCES

• 1: Rakesh Agrawal , Shaul Dar , H. V. Jagadish, Direct transitive closure algorithms: design and performance evaluation, ACM Transactions on Database Systems (TODS), v.15 n.3, p.427-458, Sept. 1990 [doi>10.1145/88636.88888]
• 2: Rakesh Agrawal , H. V. Jagadish, Direct Algorithms for Computing the Transitive Closure of Database Relations, Proceedings of the 13th International Conference on Very Large Data Bases, p.255-266, September 01-04, 1987
• 3: Rakesh Agrawal , H. V. Jagadish, Hybrid transitive closure algorithms, Proceedings of the sixteenth international conference on Very large databases, p.326-334, September 1990, Brisbane, Australia
• 4: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 5: Francois Bancilhon, Naive evaluation of recursively defined relations, On knowledge base management systems: integrating artificial intelligence and d atabase technologies, Springer-Verlag New York, Inc., New York, NY, 1986
• 6: CARRE, B. Graphs and Networks. Clarendon Press, Oxford, England, 1979.
• 7: Isabel F. Cruz , Theodore S. Norvell, Aggregative Closure: An Extension of Transitive Closure, Proceedings of the Fifth International Conference on Data Engineering, p.384-391, February 06-10, 1989
• 8: DAR, S. Ph.D. thesis, Univ. of Wisconsin-Madison, Aug. 1993.
• 9: DIJKSTRA, E.W. A note on two problems in connection with graphs. Numer. Math. 1 (1959), 269-271.
• 10: EBERT, J. A sensitive transitive closure algorithm. Inf. Process. Lett. 12, 5 (1981).
• 11: EVE, J., AND KURKI-SUONIO, R. On computing the transitive closure of a relation. Acta Inf. (1977), 303-314.
• 12: Yannis E. Ioannidis, On the Computation of the Transitive Closure of Relational Operators, Proceedings of the 12th International Conference on Very Large Data Bases, p.403-411, August 25-28, 1986
• 13: Yannis E. Ioannidis , Raghu Ramakrishnan, Efficient Transitive Closure Algorithms, Proceedings of the 14th International Conference on Very Large Data Bases, p.382-394, August 29-September 01, 1988
• 14: Bin Jiang, A Suitable Algorithm for Computing Partial Transitive Closures in Databases, Proceedings of the Sixth International Conference on Data Engineering, p.264-271, February 05-09, 1990
• 15: Bin Jiang, I/O-Efficiency of Shortest Path Algorithms: An Analysis, Proceedings of the Eighth International Conference on Data Engineering, p.12-19, February 03-07, 1992
• 16: Robert Kabler , Yannis E. Ioannidis , Michael J. Carey, Performance evaluation of algorithms for transitive closure, Information Systems, v.17 n.5, p.415-441, Sept. 1992 [doi>10.1016/0306-4379(92)90035-L]
• 17: R-M Kung , E Hanson , Y Ioannidis , T Sellis , L Shapiro , M Stonebraker, Heuristic search in database systems, Proceedings from the first international workshop on Expert database systems, p.537-548, January 1986, Kiawah Island, South Carolina, United States
• 18: Hongjun Lu, New Strategies for Computing the Transitive Closure of a Database Relation, Proceedings of the 13th International Conference on Very Large Data Bases, p.267-274, September 01-04, 1987
• 19: Hongjun Lu , Krishna P. Mikkilineni , James P. Richardson, Design and Evaluation of Algorithms to Compute the Transitive Closure of a Database Relation, Proceedings of the Third International Conference on Data Engineering, p.112-119, February 03-05, 1987
• 20: PURDOM, P. A transitive closure algorithm. BIT, 10 (1970), 76 94.
• 21: J. F. Naughton, One-sided recursions, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.340-348, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28695]
• 22: Ghassan Z. Qadah , Lawrence J. Henschen , Jung J. Kim, Efficient Algorithms for the Instantiated Transitive Closure Queries, IEEE Transactions on Software Engineering, v.17 n.3, p.296-309, March 1991 [doi>10.1109/32.75418 ]
• 23: Elaine Rich, Artificial intelligence, McGraw-Hill, Inc., New York, NY, 1983
• 24: Arnon Rosenthal , Sandra Heiler , Umeshwar Dayal , Frank Manola, Traversal recursion: a practical approach to supporting recursive applications, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.166-176, May 28-30, 1986, Washington, D.C., United States
• 25: SCHMITZ, L. An improved transitive closure algorithm. Computing 30 (1983), 359 371.
• 26: TARJAN, R.E. Depth-first search and linear graph algorithms. SIAM J. Comput. 1, 2 (1972), 146 160.
• 27: VALDURmZ, P., AND BORAL, H. Evaluation ofrecursive queries using join indices. In Proceedings of the 1st International Expert Database Systems Conference (Charleston, S. C., April 1986), 197-208.
• 28: Henry S. Warren, Jr., A modification of Warshall's algorithm for the transitive closure of binary relations, Communications of the ACM, v.18 n.4, p.218-220, April 1975 [doi>10.1145/360715.360746]
• 29: Stephen Warshall, A Theorem on Boolean Matrices, Journal of the ACM (JACM), v.9 n.1, p.11-12, Jan. 1962 [doi>10.1145/321105.321107]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Recursion
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Swapping**; Secondary storage; Main memory

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees; Graphs and networks

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Performance

Keywords:
depth-first search, node reachability, path computations, transitive closure