Efficient Transitive Closure Algorithms.

Yannis E. Ioannidis, Raghu Ramakrishnan: Efficient Transitive Closure Algorithms. VLDB 1988: 382-394
  author    = {Yannis E. Ioannidis and
               Raghu Ramakrishnan},
  editor    = {Fran\c{c}ois Bancilhon and
               David J. DeWitt},
  title     = {Efficient Transitive Closure Algorithms},
  booktitle = {Fourteenth International Conference on Very Large Data Bases,
               August 29 - September 1, 1988, Los Angeles, California, USA,
  publisher = {Morgan Kaufmann},
  year      = {1988},
  isbn      = {0-934613-75-3},
  pages     = {382-394},
  ee        = {db/conf/vldb/IoannidisR88.html},
  crossref  = {DBLP:conf/vldb/88},
  bibsource = {DBLP,}


We have developed some efficient algorithms for computing the transitive closure of a directed graph. This paper presents the algorithms for the problem of reachability. The algorithms, however, can be adapted to deal with path computations and a significantly broader class of queries based on one-sided recursions. We analyze these algorithms and compare them to algorithms in the literature. The results indicate that these algorithms, in addition to their ability to deal with queries that are generalizations of transitive closure, also perform very efficiently, in particular, in the context of a disk-based database environment.

Copyright © 1988 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

François Bancilhon, David J. DeWitt (Eds.): Fourteenth International Conference on Very Large Data Bases, August 29 - September 1, 1988, Los Angeles, California, USA, Proceedings. Morgan Kaufmann 1988, ISBN 0-934613-75-3

Journal Version

Yannis E. Ioannidis, Raghu Ramakrishnan, Linda Winger: Transitive Closure Algorithms Based on Graph Traversal. ACM Trans. Database Syst. 18(3): 512-576(1993) BibTeX


[Agrawal and Jagadish 87]
Rakesh Agrawal, H. V. Jagadish: Direct Algorithms for Computing the Transitive Closure of Database Relations. VLDB 1987: 255-266 BibTeX
[Agrawal et al. 87]
[Agrawal and Jagadish 88]
[Aho et al. 74]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
[Bancilhon 85]
[Carre 79]
[Dijkstra 59]
[Eve and Kurik-Suonio 77]
J. Eve, Reino Kurki-Suonio: On Computing the Transitive Closure of a Relation. Acta Inf. 8: 303-314(1977) BibTeX
[Ioannidis 86]
Yannis E. Ioannidis: On the Computation of the Transitive Closure of Relational Operators. VLDB 1986: 403-411 BibTeX
[Ioannidis and Ramakrishnan 88]
[Lu 87]
Hongjun Lu: New Strategies for Computing the Transitive Closure of a Database Relation. VLDB 1987: 267-274 BibTeX
[Lu, Mikkilineni and Richardson 87]
Hongjun Lu, Krishna P. Mikkilineni, James P. Richardson: Design and Evaluation of Algorithms to Compute the Transitive Closure of a Database Relation. ICDE 1987: 112-119 BibTeX
[Naughton 87]
Jeffrey F. Naughton: One-Sided Recursions. PODS 1987: 340-348 BibTeX
[Rosenthal et al. 86]
Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176 BibTeX
[Schmitz 83]
[Schnorr 78]
Claus-Peter Schnorr: An Algorithm for Transitive Closure with Linear Expected Time. SIAM J. Comput. 7(2): 127-133(1978) BibTeX
[Tarjan 72]
Robert Endre Tarjan: Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1(2): 146-160(1972) BibTeX
[Valduriez and Boral 86]
Patrick Valduriez, Haran Boral: Evaluation of Recursive Queries Using Join Indices. Expert Database Conf. 1986: 271-293 BibTeX
[Warren 75]
Henry S. Warren Jr.: A Modification of Warshall's Algorithm for the Transitive Closure of Binary Relations. Commun. ACM 18(4): 218-220(1975) BibTeX
[Warshall 62]
Stephen Warshall: A Theorem on Boolean Matrices. J. ACM 9(1): 11-12(1962) BibTeX

Referenced by

  1. Ning Jing, Yun-Wu Huang, Elke A. Rundensteiner: Hierarchical Encoded Path Views for Path Query Processing: An Optimal Model and Its Performance Evaluation. IEEE Trans. Knowl. Data Eng. 10(3): 409-432(1998)
  2. Ismail H. Toroslu, Ghassan Z. Qadah: The Strong Partial Transitive-Closure Problem: Algorithms and Performance Evaluation. IEEE Trans. Knowl. Data Eng. 8(4): 617-629(1996)
  3. Sakti Pramanik, Sungwon Jung: Description and Identification of Distributed Fragments of Recursive Relations. IEEE Trans. Knowl. Data Eng. 8(6): 1002-1016(1996)
  4. Sungwon Jung, Sakti Pramanik: HiTi Graph Model of Topographical Roadmaps in Navigation Systems. ICDE 1996: 76-84
  5. Jiawei Han: Chain-Split Evaluation in Deductive Databases. IEEE Trans. Knowl. Data Eng. 7(2): 261-273(1995)
  6. Keh-Chang Guh, Clement T. Yu: Efficient Query Processing for a Subset of Linear Recursive Binary Rules. IEEE Trans. Knowl. Data Eng. 6(5): 842-849(1994)
  7. Shaul Dar, Raghu Ramakrishnan: A Performance Study of Transitive Closure Algorithms. SIGMOD Conference 1994: 454-465
  8. Qi Yang, Clement T. Yu, Chengwen Liu, Son Dao, Gaoming Wang, Tracy Pham: A Hybrid Transitive Closure Algorithm for Sequential and Parallel Processing. ICDE 1994: 498-505
  9. Jukka Teuhola: An Efficient Relational Implementation of Recursive Relationships using Path Signatures. ICDE 1994: 348-355
  10. Yannis E. Ioannidis, Raghu Ramakrishnan, Linda Winger: Transitive Closure Algorithms Based on Graph Traversal. ACM Trans. Database Syst. 18(3): 512-576(1993)
  11. Shaul Dar, Rakesh Agrawal: Extending SQL with Generalized Transitive Closure Functionality. IEEE Trans. Knowl. Data Eng. 5(5): 799-812(1993)
  12. Philippe De Smedt, Stefano Ceri, Marie-Anne Neimat, Ming-Chien Shan, Rafi Ahmed: Recursive Functions in Iris. ICDE 1993: 145-154
  13. Shashi Shekhar, Ashim Kohli, Mark Coyle: Path Computation Algorithms for Advanced Traveller Information System (ATIS). ICDE 1993: 31-39
  14. Maurice A. W. Houtsma, Peter M. G. Apers, Gideon L. V. Schipper: Data fragmentation for parallel transitive closure strategies. ICDE 1993: 447-456
  15. Keh-Chang Guh, Clement T. Yu: Efficient Management of Materialized Generalized Transitive Closure in Centralized and Parallel Environments. IEEE Trans. Knowl. Data Eng. 4(4): 371-381(1992)
  16. Håkan Jakobsson: On Tree-Based Techniques for Query Evaluation. PODS 1992: 380-392
  17. Bin Jiang: I/O-Efficiency of Shortest Path Algorithms: An Analysis. ICDE 1992: 12-19
  18. Jiawei Han: Chain-Split Evaluation in Deductive Databases. ICDE 1992: 376-384
  19. Shaul Dar, H. V. Jagadish: A Spanning Tree Transitive Closure Algorithm. ICDE 1992: 2-11
  20. Håkan Jakobsson: Mixed-Approach Algorithms for Transitive Closure. PODS 1991: 199-205
  21. Steve Taylor, Nabil I. Hachem: A Direct Algorithm for Computing the Transitive Closure of a Two-Dimensionally Structured File. MFDBS 1991: 146-159
  22. Yan-Nong Huang, Jean-Pierre Cheiney: Parallel Computation of Direct Transitive Closures. ICDE 1991: 192-199
  23. Keh-Chang Guh, Chengyu Sun, Clement T. Yu: Real Time Retrieval and Update of Materialized Transitive Closure. ICDE 1991: 690-697
  24. Sumit Ganguly, Ravi Krishnamurthy, Abraham Silberschatz: An Analysis Technique for Transitive Closure Algorithms: A Statistical Approach. ICDE 1991: 728-735
  25. Shaul Dar, Rakesh Agrawal, H. V. Jagadish: Optimization of Generalized Transitive Closure Queries. ICDE 1991: 345-354
  26. H. V. Jagadish: A Compression Technique to Materialize Transitive Closure. ACM Trans. Database Syst. 15(4): 558-598(1990)
  27. Maurice A. W. Houtsma, Peter M. G. Apers, Stefano Ceri: Distributed Transitive Closure Computations: The Disconnection Set Approach. VLDB 1990: 335-346
  28. Jean-Pierre Cheiney, Christophe de Maindreville: A Parallel Strategy for Transitive Closure usind Double Hash-Based Clustering. VLDB 1990: 347-358
  29. Rakesh Agrawal, H. V. Jagadish: Hybrid Transitive Closure Algorithms. VLDB 1990: 326-334
  30. Jeffrey D. Ullman, Mihalis Yannakakis: The Input/Output Complexity of Transitive Closure. SIGMOD Conference 1990: 44-53
  31. Mihalis Yannakakis: Graph-Theoretic Methods in Database Theory. PODS 1990: 230-242
  32. Maurice A. W. Houtsma, Peter M. G. Apers, Stefano Ceri: Complex Transitive Closure Queries on a Fragmented Graph. ICDT 1990: 470-484
  33. Mariano P. Consens, Alberto O. Mendelzon: Low Complexity Aggregation in GraphLog and Datalog. ICDT 1990: 379-394
  34. Bin Jiang: A Suitable Algorithm for Computing Partial Transitive Closures in Databases. ICDE 1990: 264-271
  35. Yuki Kusumi, Shojiro Nishio, Toshiharu Hasegawa: File Access Level Optimization Using Page Access Graph on Recursive Query Evaluation. EDBT 1990: 136-152
  36. Alberto O. Mendelzon, Peter T. Wood: Finding Regular Simple Paths in Graph Databases. VLDB 1989: 185-193
  37. Richard J. Lipton, Jeffrey F. Naughton: Estimating the Size of Generalized Transitive Closures. VLDB 1989: 165-171
  38. Rakesh Agrawal, Alexander Borgida, H. V. Jagadish: Efficient Management of Transitive Relationships in Large Data and Knowledge Bases. SIGMOD Conference 1989: 253-262
  39. Isabel F. Cruz, Theodore S. Norvell: Aggregative Closure: An Extension of Transitive Closure. ICDE 1989: 384-391
  40. Shojiro Nishio, Masatsugu Nakahata, Eric G. Manning: A New Recursive Query Evaluation Strategy Using Search History Information. DASFAA 1989: 310-319
  41. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:39 2009