On the Computation of the Transitive Closure of Relational Operators.

Yannis E. Ioannidis: On the Computation of the Transitive Closure of Relational Operators. VLDB 1986: 403-411
  author    = {Yannis E. Ioannidis},
  editor    = {Wesley W. Chu and
               Georges Gardarin and
               Setsuo Ohsuga and
               Yahiko Kambayashi},
  title     = {On the Computation of the Transitive Closure of Relational Operators},
  booktitle = {VLDB'86 Twelfth International Conference on Very Large Data Bases,
               August 25-28, 1986, Kyoto, Japan, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1986},
  isbn      = {0-934613-18-4},
  pages     = {403-411},
  ee        = {db/conf/vldb/Ioannidis86.html},
  crossref  = {DBLP:conf/vldb/86},
  bibsource = {DBLP,}


Query processing in the presence of recursively defined views usually involves some form of iteration. For example, computing the transitive closure of a tree involves iterating N times, where N is the depth of the tree, each time computing pairs of vertices that are one edge further apart than the pairs produced in the previous iteration. Applying a divide and conquer technique we devise algorithms that need a logarithmic number of iterations. Assuming that we are looking for complete materializations of the recursively defined relations we show both through analytical and experimental results that this approach is in many cases superior in performance than the N-iteration algorithm.

Copyright © 1986 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

Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, Yahiko Kambayashi (Eds.): VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan, Proceedings. Morgan Kaufmann 1986, ISBN 0-934613-18-4
Contents BibTeX


Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 BibTeX
David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8 BibTeX
Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984) BibTeX
Antonin Guttman: New Features for Relational Database Systems to Support CAD Applications. Ph.D. thesis, University of California, Berkeley 1984
Jiawei Han, Hongjun Lu: Some Performance Results on Recursive Query Processing in Relational Database Systems. ICDE 1986: 533-541 BibTeX
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
Yannis E. Ioannidis, Eugene Wong: An Algebraic Approach to Recursive Inference. Expert Database Conf. 1986: 295-309 BibTeX
Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176 BibTeX
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX
Patrick Valduriez, Haran Boral: Evaluation of Recursive Queries Using Join Indices. Expert Database Conf. 1986: 271-293 BibTeX
Laurent Vieille: Recursive Axioms in Deductive Databases: The Query/Subquery Approach. Expert Database Conf. 1986: 253-267 BibTeX

Referenced by

  1. 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)
  2. Rakesh Agrawal, H. V. Jagadish: Algorithms for Searching Massive Graphs. IEEE Trans. Knowl. Data Eng. 6(2): 225-238(1994)
  3. Yannis E. Ioannidis, Raghu Ramakrishnan, Linda Winger: Transitive Closure Algorithms Based on Graph Traversal. ACM Trans. Database Syst. 18(3): 512-576(1993)
  4. Shaul Dar, Rakesh Agrawal: Extending SQL with Generalized Transitive Closure Functionality. IEEE Trans. Knowl. Data Eng. 5(5): 799-812(1993)
  5. Maurice A. W. Houtsma, Annita N. Wilschut, Jan Flokstra: Implementation and Performance Evaluation of a Parallel Transitive Closure Algorithm on PRISMA/DB. VLDB 1993: 206-217
  6. Shashi Shekhar, Ashim Kohli, Mark Coyle: Path Computation Algorithms for Advanced Traveller Information System (ATIS). ICDE 1993: 31-39
  7. Shaul Dar, H. V. Jagadish: A Spanning Tree Transitive Closure Algorithm. ICDE 1992: 2-11
  8. Steve Taylor, Nabil I. Hachem: A Direct Algorithm for Computing the Transitive Closure of a Two-Dimensionally Structured File. MFDBS 1991: 146-159
  9. Keh-Chang Guh, Chengyu Sun, Clement T. Yu: Real Time Retrieval and Update of Materialized Transitive Closure. ICDE 1991: 690-697
  10. Sumit Ganguly, Ravi Krishnamurthy, Abraham Silberschatz: An Analysis Technique for Transitive Closure Algorithms: A Statistical Approach. ICDE 1991: 728-735
  11. Shaul Dar, Rakesh Agrawal, H. V. Jagadish: Optimization of Generalized Transitive Closure Queries. ICDE 1991: 345-354
  12. H. V. Jagadish: A Compression Technique to Materialize Transitive Closure. ACM Trans. Database Syst. 15(4): 558-598(1990)
  13. Rakesh Agrawal, Shaul Dar, H. V. Jagadish: Direct Transitive Closure Algorithms: Design and Performance Evaluation. ACM Trans. Database Syst. 15(3): 427-458(1990)
  14. Maurice A. W. Houtsma, Peter M. G. Apers, Stefano Ceri: Distributed Transitive Closure Computations: The Disconnection Set Approach. VLDB 1990: 335-346
  15. Rakesh Agrawal, H. V. Jagadish: Hybrid Transitive Closure Algorithms. VLDB 1990: 326-334
  16. Mihalis Yannakakis: Graph-Theoretic Methods in Database Theory. PODS 1990: 230-242
  17. Maurice A. W. Houtsma, Peter M. G. Apers, Stefano Ceri: Complex Transitive Closure Queries on a Fragmented Graph. ICDT 1990: 470-484
  18. Bin Jiang: A Suitable Algorithm for Computing Partial Transitive Closures in Databases. ICDE 1990: 264-271
  19. Stefano Ceri, Georg Gottlob, Letizia Tanca: What you Always Wanted to Know About Datalog (And Never Dared to Ask). IEEE Trans. Knowl. Data Eng. 1(1): 146-166(1989)
  20. Richard J. Lipton, Jeffrey F. Naughton: Estimating the Size of Generalized Transitive Closures. VLDB 1989: 165-171
  21. Yannis E. Ioannidis: Commutativity and its Role in the Processing of Linear Recursion. VLDB 1989: 155-163
  22. Rakesh Agrawal, Alexander Borgida, H. V. Jagadish: Efficient Management of Transitive Relationships in Large Data and Knowledge Bases. SIGMOD Conference 1989: 253-262
  23. W. Yan, Nelson Mendonça Mattos: Transitive Closure and the LOGA+-Strategy for its Efficient Evaluation. MFDBS 1989: 415-428
  24. Georg Gottlob, Michael Schrefl, Markus Stumptner: On the Interaction between Transitive Closure and Functional Dependencies. MFDBS 1989: 187-206
  25. Isabel F. Cruz, Theodore S. Norvell: Aggregative Closure: An Extension of Transitive Closure. ICDE 1989: 384-391
  26. Rakesh Agrawal, H. V. Jagadish: Materialization and Incremental Update of Path Information. ICDE 1989: 374-383
  27. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
  28. Yannis E. Ioannidis, Raghu Ramakrishnan: Efficient Transitive Closure Algorithms. VLDB 1988: 382-394
  29. Seppo Sippu, Eljas Soisalon-Soininen: A Generalized Transitive Closure for Relational Queries. PODS 1988: 325-332
  30. Kyu-Young Whang, Stephen Brady: A Framework for Optimization in Expert System - DBMS Interface. ICDE 1988: 126-133
  31. Kyu-Young Whang, Shamkant B. Navathe: An Extended Disjunctive Normal Form Approach for Optimizing Recursive Logic Queries in Loosely Coupled Environments. VLDB 1987: 275-287
  32. Wolfgang Nejdl: Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy. VLDB 1987: 43-50
  33. Hongjun Lu: New Strategies for Computing the Transitive Closure of a Database Relation. VLDB 1987: 267-274
  34. Rakesh Agrawal, H. V. Jagadish: Direct Algorithms for Computing the Transitive Closure of Database Relations. VLDB 1987: 255-266
  35. Timos K. Sellis: Efficiently Supporting Procedures in Relational Database Systems. SIGMOD Conference 1987: 278-291
  36. H. V. Jagadish, Rakesh Agrawal, Linda Ness: A Study of Transitive Closure As a Recursion Mechanism. SIGMOD Conference 1987: 331-344
  37. Yannis E. Ioannidis, Eugene Wong: Query Optimization by Simulated Annealing. SIGMOD Conference 1987: 9-22
  38. Paris C. Kanellakis: Logic Programming and Parallel Complexity. ICDT 1986: 1-30
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:32 2009