A Spanning Tree Transitive Closure Algorithm.

@inproceedings{DBLP:conf/icde/DarJ92,
  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, http://dblp.uni-trier.de}
}

Abstract

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

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An2-6 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[1]

Rakesh Agrawal: Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries. ICDE 1987: 580-590 BibTeX

[2]

Rakesh Agrawal, Alexander Borgida, H. V. Jagadish: Efficient Management of Transitive Relationships in Large Data and Knowledge Bases. SIGMOD Conference 1989: 253-262 BibTeX

[3]

Rakesh Agrawal, H. V. Jagadish: Hybrid Transitive Closure Algorithms. VLDB 1990: 326-334 BibTeX

[4]

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

[5]

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX

[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

[7]

...

[8]

François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX

[9]

...

[10]

Isabel F. Cruz, Theodore S. Norvell: Aggregative Closure: An Extension of Transitive Closure. ICDE 1989: 384-391 BibTeX

[11]

Jürgen Ebert: A Sensitive Transitive Closure Algorithm. Inf. Process. Lett. 12(5): 255-258(1981) BibTeX

[12]

J. Eve, Reino Kurki-Suonio: On Computing the Transitive Closure of a Relation. Acta Inf. 8: 303-314(1977) BibTeX

[13]

Yannis E. Ioannidis: On the Computation of the Transitive Closure of Relational Operators. VLDB 1986: 403-411 BibTeX

[14]

Yannis E. Ioannidis, Raghu Ramakrishnan: Efficient Transitive Closure Algorithms. VLDB 1988: 382-394 BibTeX

[15]

Giuseppe F. Italiano: Amortized Efficiency of a Path Retrieval Data Structure. Theor. Comput. Sci. 48(3): 273-281(1986) BibTeX

[16]

H. V. Jagadish, Rakesh Agrawal, Linda Ness: A Study of Transitive Closure As a Recursion Mechanism. SIGMOD Conference 1987: 331-344 BibTeX

[17]

H. V. Jagadish: A Compression Technique to Materialize Transitive Closure. ACM Trans. Database Syst. 15(4): 558-598(1990) BibTeX

[18]

Håkan Jakobsson: Mixed-Approach Algorithms for Transitive Closure. PODS 1991: 199-205 BibTeX

[19]

Bin Jiang: A Suitable Algorithm for Computing Partial Transitive Closures in Databases. ICDE 1990: 264-271 BibTeX

[20]

Hongjun Lu: New Strategies for Computing the Transitive Closure of a Database Relation. VLDB 1987: 267-274 BibTeX

[21]

Paul Walton Purdom Jr.: A Transitive Closure Algorithm. BIT 10: 76-94(1970) BibTeX

[22]

Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176 BibTeX

[23]

Lothar Schmitz: An Improved Transitive Closure Algorithm. Computing 30: 359-371(1983) BibTeX

[24]

Robert Endre Tarjan: Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1(2): 146-160(1972) BibTeX

[25]

Jeffrey D. Ullman, Mihalis Yannakakis: The Input/Output Complexity of Transitive Closure. SIGMOD Conference 1990: 44-53 BibTeX

[26]

Patrick Valduriez, Haran Boral: Evaluation of Recursive Queries Using Join Indices. Expert Database Conf. 1986: 271-293 BibTeX

[27]

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