A Spanning Tree Transitive Closure Algorithm.

Shaul Dar, H. V. Jagadish: A Spanning Tree Transitive Closure Algorithm. ICDE 1992: 2-11
  author    = {Shaul Dar and
               H. V. Jagadish},
  editor    = {Forouzan Golshani},
  title     = {A Spanning Tree Transitive Closure Algorithm},
  booktitle = {Proceedings of the Eighth International Conference on Data Engineering,
               February 3-7, 1992, Tempe, Arizona},
  publisher = {IEEE Computer Society},
  year      = {1992},
  isbn      = {0-8186-2545-7},
  pages     = {2-11},
  ee        = {db/conf/icde/DarJ92.html},
  crossref  = {DBLP:conf/icde/92},
  bibsource = {DBLP,}


Copyright © 1992 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 6, ICDE 1984-1995" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Forouzan Golshani (Ed.): Proceedings of the Eighth International Conference on Data Engineering, February 3-7, 1992, Tempe, Arizona. IEEE Computer Society 1992, ISBN 0-8186-2545-7
Contents BibTeX


Rakesh Agrawal: Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries. ICDE 1987: 580-590 BibTeX
Rakesh Agrawal, Alexander Borgida, H. V. Jagadish: Efficient Management of Transitive Relationships in Large Data and Knowledge Bases. SIGMOD Conference 1989: 253-262 BibTeX
Rakesh Agrawal, H. V. Jagadish: Hybrid Transitive Closure Algorithms. VLDB 1990: 326-334 BibTeX
Rakesh Agrawal, Shaul Dar, H. V. Jagadish: Direct Transitive Closure Algorithms: Design and Performance Evaluation. ACM Trans. Database Syst. 15(3): 427-458(1990) BibTeX
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
Hassan Aït-Kaci, Robert S. Boyer, Patrick Lincoln, Roger Nasr: Efficient Implementation of Lattice Operations. ACM Trans. Program. Lang. Syst. 11(1): 115-146(1989) BibTeX
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
Isabel F. Cruz, Theodore S. Norvell: Aggregative Closure: An Extension of Transitive Closure. ICDE 1989: 384-391 BibTeX
Jürgen Ebert: A Sensitive Transitive Closure Algorithm. Inf. Process. Lett. 12(5): 255-258(1981) BibTeX
J. Eve, Reino Kurki-Suonio: On Computing the Transitive Closure of a Relation. Acta Inf. 8: 303-314(1977) BibTeX
Yannis E. Ioannidis: On the Computation of the Transitive Closure of Relational Operators. VLDB 1986: 403-411 BibTeX
Yannis E. Ioannidis, Raghu Ramakrishnan: Efficient Transitive Closure Algorithms. VLDB 1988: 382-394 BibTeX
Giuseppe F. Italiano: Amortized Efficiency of a Path Retrieval Data Structure. Theor. Comput. Sci. 48(3): 273-281(1986) BibTeX
H. V. Jagadish, Rakesh Agrawal, Linda Ness: A Study of Transitive Closure As a Recursion Mechanism. SIGMOD Conference 1987: 331-344 BibTeX
H. V. Jagadish: A Compression Technique to Materialize Transitive Closure. ACM Trans. Database Syst. 15(4): 558-598(1990) BibTeX
Håkan Jakobsson: Mixed-Approach Algorithms for Transitive Closure. PODS 1991: 199-205 BibTeX
Bin Jiang: A Suitable Algorithm for Computing Partial Transitive Closures in Databases. ICDE 1990: 264-271 BibTeX
Hongjun Lu: New Strategies for Computing the Transitive Closure of a Database Relation. VLDB 1987: 267-274 BibTeX
Paul Walton Purdom Jr.: A Transitive Closure Algorithm. BIT 10: 76-94(1970) BibTeX
Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176 BibTeX
Lothar Schmitz: An Improved Transitive Closure Algorithm. Computing 30: 359-371(1983) BibTeX
Robert Endre Tarjan: Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1(2): 146-160(1972) BibTeX
Jeffrey D. Ullman, Mihalis Yannakakis: The Input/Output Complexity of Transitive Closure. SIGMOD Conference 1990: 44-53 BibTeX
Patrick Valduriez, Haran Boral: Evaluation of Recursive Queries Using Join Indices. Expert Database Conf. 1986: 271-293 BibTeX
Stephen Warshall: A Theorem on Boolean Matrices. J. ACM 9(1): 11-12(1962) BibTeX

Referenced by

  1. Shashi Shekhar, Duen-Ren Liu: CCAM: A Connectivity-Clustered Access Method for Networks and Network Computations. IEEE Trans. Knowl. Data Eng. 9(1): 102-119(1997)
  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. Shashi Shekhar, Duen-Ren Liu: CCAM: A Connectivity-Clustered Access Method for Aggregate Queries on Transportation Networks: A Summary of Results. ICDE 1995: 410-419
  4. Shaul Dar, Raghu Ramakrishnan: A Performance Study of Transitive Closure Algorithms. SIGMOD Conference 1994: 454-465
  5. 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
  6. Jukka Teuhola: An Efficient Relational Implementation of Recursive Relationships using Path Signatures. ICDE 1994: 348-355
  7. Shaul Dar, Rakesh Agrawal: Extending SQL with Generalized Transitive Closure Functionality. IEEE Trans. Knowl. Data Eng. 5(5): 799-812(1993)
  8. Ismail H. Toroslu, Ghassan Z. Qadah: The Efficient Computation of Strong Partial Transitive-Closures. ICDE 1993: 530-537
  9. Shashi Shekhar, Ashim Kohli, Mark Coyle: Path Computation Algorithms for Advanced Traveller Information System (ATIS). ICDE 1993: 31-39
  10. Håkan Jakobsson: On Tree-Based Techniques for Query Evaluation. PODS 1992: 380-392
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ICDE Proceedings: Copyright © by IEEE,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:18:01 2009