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

[2]

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

[3]

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

[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)

[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

[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)

[7]

...

[8]

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

[9]

...

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

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

[21]

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

[22]

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

[23]

Lothar Schmitz: An improved transitive closure algorithm. Computing 30(4): 359-371(1983)

[24]

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

[25]

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

[26]

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

[27]

Stephen Warshall: A Theorem on Boolean Matrices. J. ACM 9(1): 11-12(1962)