Direct transitive closure algorithms: design and performance evaluation

ABSTRACT

We present new algorithms for computing transitive closure of large database relations. Unlike iterative algorithms, such as the seminaive and logarithmic algorithms, the termination of our algorithms does not depend on the length of paths in the underlying graph (hence the name direct algorithms). Besides reachability computations, the proposed algorithms can also be used for solving path problems. We discuss issues related to the efficient implementation of these algorithms, and present experimental results that show the direct algorithms perform uniformly better than the iterative algorithms. A side benefit of this work is that we have proposed a new methodology for evaluating the performance of recursive queries.

REFERENCES

• 1: 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
• 2: Rakesh Agrawal, Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries, IEEE Transactions on Software Engineering, v.14 n.7, p.879-885, July 1988 [doi>10.1109/32.42731]
• 3: R. Agrawal , H. V. Jagadish, Multiprocessor transitive closure algorithms, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.56-66, December 05-07, 1988, Austin, Texas, United States
• 4: AGRAWAL, R., DAR, S., AND JAGADISH, H.V. On transitive closure problems involving path computations. Tech. Memo., AT&T Bell Laboratories, Murray Hill, N.J., 1988.
• 5: Rakesh Agrawal , H. V. Jagadish, Materialization and Incremental Update of Path Information, Proceedings of the Fifth International Conference on Data Engineering, p.374-383, February 06-10, 1989
• 6: R. Agrawal , A. Borgida , H. V. Jagadish, Efficient management of transitive relationships in large data and knowledge bases, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.253-262, June 1989, Portland, Oregon, United States
• 7: Rakesh Agrawal , Shaul Dar , H. V. Jagadish, Composition of Database Relations, Proceedings of the Fifth International Conference on Data Engineering, p.102-108, February 06-10, 1989
• 8: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 9: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• 10: BANCILHON, F. Naive evaluation of recursively defined relations. Tech Rep. DB-004-85, MCC, Austin, Tex., 1985.
• 11: Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States
• 12: BISKUP, J., RAESCH, U., AND STIEFELING, H. An extended relational query language for knowledgebase support. Tech. Rep., Institut fuer Informatik, Hildesheim, Germany, 1987.
• 13: Dina Bitton , David J. DeWitt , Carolyn Turbyfill, Benchmarking Database Systems A Systematic Approach, Proceedings of the 9th International Conference on Very Large Data Bases, p.8-19, October 31-November 02, 1983
• 14: CARRE, B. Graphs and Networks. Clarendon Press, Oxford, England, 1978.
• 15: H.-T. Chou , David J. Dewitt , Randy H. Katz , Anthony C. Klug, Design and implementation of the Wisconsin storage system, Software—Practice & Experience, v.15 n.10, p.943-962, Oct. 1985 [doi>10.1002/spe.4380151003]
• 16: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 17: DAYAL, U., AND SMITH, J.M. PROBE: A knowledge-oriented database management system. In Proceedings Islamorada Workshop on Large Scale Knowledge Base and Reasoning Systems (Islamorada, Fla., Feb. 1985). 103-137.
• 18: DEWITT, D. J. DIRECT--A multiprocessor organization for supporting relational database management systems. IEEE Trans. Comput. C-28, 6 (June 1979), 395-406.
• 19: David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 20: DEWITT, D. J., AND GERBER, R.H. Multiprocessor hash-based join algorithms. In Proceedings 11th International Conference on Very Large Data Bases (Stockholm, Aug. 1985). 151-164.
• 21: David J. DeWitt , Robert H. Gerber , Goetz Graefe , Michael L. Heytens , Krishna B. Kumar , M. Muralikrishna, GAMMA - A High Performance Dataflow Database Machine, Proceedings of the 12th International Conference on Very Large Data Bases, p.228-237, August 25-28, 1986
• 22: HELL, W. RDBM--A relational database machine: Architecture and hardware design. In Proceedings 6th Workshop on Computer Architecture for Non-Numeric Processing (June 1981).
• 23: 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
• 24: H. V. Jagadish , Rakesh Agrawal , Linda Ness, A study of transitive closure as a recursion mechanism, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.331-344, May 27-29, 1987, San Francisco, California, United States
• 25: JAGADISH, H. V. A compressed transitive closure technique for efficient fixed-point query processing. In Proceedings 2nd International Conference on Expert Database Systems (Tysons Corner, Va., April 1988).
• 26: H. V. Jagadish, Incorporating hierarchy in a relational model of data, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.78-87, June 1989, Portland, Oregon, United States
• 27: KITSUREGAWA, M., TANAKA, H., AND MOTO-OKA, T. Architecture and performance of relational algebra machine grace. Tech. Rep., Univ. of Tokyo, 1983.
• 28: 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
• 29: 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
• 30: T H Merrett, Relational Information Systems, Reston Publishing Co., Reston, VA, 1984
• 31: MISSIKOFF, M. An overview of the Project DBMAC for a relational machine. In Proceedings 6th Workshop on Computer Architecture for Non-Numeric Processing (June 1981).
• 32: PETAJAN, E., BARAFF, D., AND WEIL, J. Human hand model calibration using 3-D reconstruc-{ tion from multiple silhouette views. In Three-Dimensional Imaging and Remote Sensing Imaging, W. E. Robbins, Ed., Proc. SPIE 902, 1988, 87-91.
• 33: 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
• 34: SCHNORR, C.P. An algorithm for transitive closure with linear expected time. SIAM J. Comput. 7, 2 (May 1978), 127-133.
• 35: VALDURIEZ, P., AND BORAL, S. Evaluation of recursive queries using join indices. In Proceedings 1st International Conference on Expert Database Systems (Charleston, S.C., April 1986). 197-208.
• 36: 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]
• 37: 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]
• 38: ZLOOF, M.M. Query-by-example: Operations on the transitive closure. Res. Rep. RC 5526, IBM, Yorktown Heights, N.Y., 1975.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.0 General

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
deductive databases, query processing, transitive closure