A Suitable Algorithm for Computing Partial Transitive Closures in Databases.

@inproceedings{DBLP:conf/icde/Jiang90,
  author    = {Bin Jiang},
  title     = {A Suitable Algorithm for Computing Partial Transitive Closures
               in Databases},
  booktitle = {Proceedings of the Sixth International Conference on Data Engineering,
               February 5-9, 1990, Los Angeles, California, USA},
  publisher = {IEEE Computer Society},
  year      = {1990},
  isbn      = {0-8186-2025-0},
  pages     = {264-271},
  ee        = {db/conf/icde/Jiang90.html},
  crossref  = {DBLP:conf/icde/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1990 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, Premkumar T. Devanbu: Moving Selections into Linear Least Fixpoint Queries. ICDE 1988: 452-461 BibTeX

[2]

Rakesh Agrawal, H. V. Jagadish: Direct Algorithms for Computing the Transitive Closure of Database Relations. VLDB 1987: 255-266 BibTeX

[3]

Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX

[4]

...

[5]

...

[6]

François Bancilhon: Naive Evaluation of Recursively Defined Relations. On Knowledge Base Management Systems (Islamorada) 1985: 165-178 BibTeX

[7]

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

[8]

Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 BibTeX

[9]

Peter A. Bloniarz, Michael J. Fischer, Albert R. Meyer: A Note on the Average Time to Compute Transitive Closures. ICALP 1976: 425-434 BibTeX

[10]

Umeshwar Dayal, John Miles Smith: PROBE: A Knowledge-Oriented Database Management System. On Knowledge Base Management Systems (Islamorada) 1985: 227-257 BibTeX

[11]

...

[12]

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

[13]

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

[14]

Christos Faloutsos: Access Methods for Text. ACM Comput. Surv. 17(1): 49-74(1985) BibTeX

[15]

Michael J. Fischer, Albert R. Meyer: Boolean Matrix Multiplication and Transitive Closure. FOCS 1971: 129-131 BibTeX

[16]

...

[17]

...

[18]

A. Goralciková, Václav Koubek: A Reduct-and-Closure Algorithm for Graphs. MFCS 1979: 301-307 BibTeX

[19]

Gösta Grahne, Seppo Sippu, Eljas Soisalon-Soininen: Efficient Evaluation for a Subset of Recursive Queries. PODS 1987: 284-293 BibTeX

[20]

Ulrich Güntzer, Werner Kießling, Rudolf Bayer: On the Evaluation of Recursion in (Deductive) Database Systems by Efficient Differential Fixpoint Iteration. ICDE 1987: 120-129 BibTeX

[21]

Jiawei Han, Lawrence J. Henschen: Handling Redundancy in the Processing of Recursive Database Queries. SIGMOD Conference 1987: 73-81 BibTeX

[22]

Jiawei Han, Ghassan Z. Qadah, Chinying Chaou: The Processing and Evaluation of Transitive Closure Queries. EDBT 1988: 49-75 BibTeX

[23]

Yannis E. Ioannidis: A Time Bound on the Materialization of some Recursively Defined Views. VLDB 1985: 219-226 BibTeX

[24]

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

[25]

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

[26]

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

[27]

Bin Jiang: Making the Partial Transitive Closure an Elementary Database Operation. BTW 1989: 231-245 BibTeX

[28]

...

[29]

...

[30]

Sanggoo Lee, Jiawei Han: Semantic Query Optimization in Recursive Databases. ICDE 1988: 444-451 BibTeX

[31]

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

[32]

...

[33]

...

[34]

J. Ian Munro: Efficient Determination of the Transitive Closure of a Directed Graph. Inf. Process. Lett. 1(2): 56-58(1971) BibTeX

[35]

Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. PODS 1986: 267-279 BibTeX

[36]

Jeffrey F. Naughton: One-Sided Recursions. PODS 1987: 340-348 BibTeX

[37]

Patrick E. O'Neil, Elizabeth J. O'Neil: A Fast Expected Time Algorithm for Boolean Matrix Multiplication and Transitive Closure. Information and Control 22(2): 132-138(1973) BibTeX

[38]

H.-Bernhard Paul, Hans-Jörg Schek, Marc H. Scholl, Gerhard Weikum, Uwe Deppisch: Architecture and Implementation of the Darmstadt Database Kernel System. SIGMOD Conference 1987: 196-207 BibTeX

[39]

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

[40]

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

[41]

...

[42]

Domenico Saccà, Carlo Zaniolo: Magic Counting Methods. SIGMOD Conference 1987: 49-59 BibTeX

[43]

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

[44]

Claus-Peter Schnorr: An Algorithm for Transitive Closure with Linear Expected Time. SIAM J. Comput. 7(2): 127-133(1978) BibTeX

[45]

Klaus Simon: An Improved Algorithm for Transitive Closure on Acyclic Digraphs. Theor. Comput. Sci. 58: 325-346(1988) BibTeX

[46]

Seppo Sippu, Eljas Soisalon-Soininen: An Optimization Strategy for Recursive Queries in Logic Databases. ICDE 1988: 470-477 BibTeX

[47]

...

[48]

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

[49]

...

[50]

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

[51]

Laurent Vieille: Recursive Axioms in Deductive Databases: The Query/Subquery Approach. Expert Database Conf. 1986: 253-267 BibTeX

[52]

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

[53]

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

[54]

Cheong Youn, Lawrence J. Henschen, Jiawei Han: Classification of Recursive Formulas in Deductive Databases. SIGMOD Conference 1988: 320-328 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. Sakti Pramanik, Sungwon Jung: Description and Identification of Distributed Fragments of Recursive Relations. IEEE Trans. Knowl. Data Eng. 8(6): 1002-1016(1996)
3. Sungwon Jung, Sakti Pramanik: HiTi Graph Model of Topographical Roadmaps in Navigation Systems. ICDE 1996: 76-84
4. Sungwon Jung, Sakti Pramanik: An Efficient Representation of Distributed Fragments of Recursive Relations. DASFAA 1995: 397-404
5. Jiawei Han: Constraint-Based Query Evaluation in Deductive Databases. IEEE Trans. Knowl. Data Eng. 6(1): 96-107(1994)
6. Shaul Dar, Raghu Ramakrishnan: A Performance Study of Transitive Closure Algorithms. SIGMOD Conference 1994: 454-465
7. 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
8. Yannis E. Ioannidis, Raghu Ramakrishnan, Linda Winger: Transitive Closure Algorithms Based on Graph Traversal. ACM Trans. Database Syst. 18(3): 512-576(1993)
9. Shaul Dar, Rakesh Agrawal: Extending SQL with Generalized Transitive Closure Functionality. IEEE Trans. Knowl. Data Eng. 5(5): 799-812(1993)
10. 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
11. Ismail H. Toroslu, Ghassan Z. Qadah: The Efficient Computation of Strong Partial Transitive-Closures. ICDE 1993: 530-537
12. Shashi Shekhar, Ashim Kohli, Mark Coyle: Path Computation Algorithms for Advanced Traveller Information System (ATIS). ICDE 1993: 31-39
13. Rakesh Agrawal, Jerry Kiernan: An Access Structure for Generalized Transitive Closure Queries. ICDE 1993: 429-438
14. Håkan Jakobsson: On Tree-Based Techniques for Query Evaluation. PODS 1992: 380-392
15. Håkan Jakobsson: On Materializing Views and On-Line Queries. ICDT 1992: 407-420
16. Bin Jiang: I/O-Efficiency of Shortest Path Algorithms: An Analysis. ICDE 1992: 12-19
17. Shaul Dar, H. V. Jagadish: A Spanning Tree Transitive Closure Algorithm. ICDE 1992: 2-11
18. Jiawei Han: Compilation-Based List Processing in Deductive Databases. EDBT 1992: 104-119
19. Hans-Jörg Schek, Marc H. Scholl, Gerhard Weikum: The Background of the DASDBS & COSMOS Projects. MFDBS 1991: 377-388
20. Shaul Dar, Rakesh Agrawal, H. V. Jagadish: Optimization of Generalized Transitive Closure Queries. ICDE 1991: 345-354
21. Rakesh Agrawal, H. V. Jagadish: Hybrid Transitive Closure Algorithms. VLDB 1990: 326-334