ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

A Suitable Algorithm for Computing Partial Transitive Closures in Databases.

Bin Jiang: A Suitable Algorithm for Computing Partial Transitive Closures in Databases. ICDE 1990: 264-271
@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

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

Printed Edition

Proceedings of the Sixth International Conference on Data Engineering, February 5-9, 1990, Los Angeles, California, USA. IEEE Computer Society 1990, ISBN 0-8186-2025-0
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Rakesh Agrawal, Premkumar T. Devanbu: Moving Selections into Linear Least Fixpoint Queries. ICDE 1988: 452-461 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Rakesh Agrawal, H. V. Jagadish: Direct Algorithms for Computing the Transitive Closure of Database Relations. VLDB 1987: 255-266 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
...
[5]
...
[6]
François Bancilhon: Naive Evaluation of Recursively Defined Relations. On Knowledge Base Management Systems (Islamorada) 1985: 165-178 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Peter A. Bloniarz, Michael J. Fischer, Albert R. Meyer: A Note on the Average Time to Compute Transitive Closures. ICALP 1976: 425-434 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Umeshwar Dayal, John Miles Smith: PROBE: A Knowledge-Oriented Database Management System. On Knowledge Base Management Systems (Islamorada) 1985: 227-257 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
...
[12]
Jürgen Ebert: A Sensitive Transitive Closure Algorithm. Inf. Process. Lett. 12(5): 255-258(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
J. Eve, Reino Kurki-Suonio: On Computing the Transitive Closure of a Relation. Acta Inf. 8: 303-314(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Christos Faloutsos: Access Methods for Text. ACM Comput. Surv. 17(1): 49-74(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
Michael J. Fischer, Albert R. Meyer: Boolean Matrix Multiplication and Transitive Closure. FOCS 1971: 129-131 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
...
[17]
...
[18]
A. Goralciková, Václav Koubek: A Reduct-and-Closure Algorithm for Graphs. MFCS 1979: 301-307 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
Gösta Grahne, Seppo Sippu, Eljas Soisalon-Soininen: Efficient Evaluation for a Subset of Recursive Queries. PODS 1987: 284-293 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
Jiawei Han, Lawrence J. Henschen: Handling Redundancy in the Processing of Recursive Database Queries. SIGMOD Conference 1987: 73-81 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[22]
Jiawei Han, Ghassan Z. Qadah, Chinying Chaou: The Processing and Evaluation of Transitive Closure Queries. EDBT 1988: 49-75 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[23]
Yannis E. Ioannidis: A Time Bound on the Materialization of some Recursively Defined Views. VLDB 1985: 219-226 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
Yannis E. Ioannidis: On the Computation of the Transitive Closure of Relational Operators. VLDB 1986: 403-411 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[25]
Yannis E. Ioannidis, Raghu Ramakrishnan: Efficient Transitive Closure Algorithms. VLDB 1988: 382-394 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[26]
H. V. Jagadish, Rakesh Agrawal, Linda Ness: A Study of Transitive Closure As a Recursion Mechanism. SIGMOD Conference 1987: 331-344 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[27]
Bin Jiang: Making the Partial Transitive Closure an Elementary Database Operation. BTW 1989: 231-245 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[28]
...
[29]
...
[30]
Sanggoo Lee, Jiawei Han: Semantic Query Optimization in Recursive Databases. ICDE 1988: 444-451 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[31]
Hongjun Lu: New Strategies for Computing the Transitive Closure of a Database Relation. VLDB 1987: 267-274 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[32]
...
[33]
...
[34]
J. Ian Munro: Efficient Determination of the Transitive Closure of a Directed Graph. Inf. Process. Lett. 1(2): 56-58(1971) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[35]
Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. PODS 1986: 267-279 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[36]
Jeffrey F. Naughton: One-Sided Recursions. PODS 1987: 340-348 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[39]
Paul Walton Purdom Jr.: A Transitive Closure Algorithm. BIT 10: 76-94(1970) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[40]
Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[41]
...
[42]
Domenico Saccà, Carlo Zaniolo: Magic Counting Methods. SIGMOD Conference 1987: 49-59 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[43]
Lothar Schmitz: An improved transitive closure algorithm. Computing 30(4): 359-371(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[44]
Claus-Peter Schnorr: An Algorithm for Transitive Closure with Linear Expected Time. SIAM J. Comput. 7(2): 127-133(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[45]
Klaus Simon: An Improved Algorithm for Transitive Closure on Acyclic Digraphs. Theor. Comput. Sci. 58: 325-346(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[46]
Seppo Sippu, Eljas Soisalon-Soininen: An Optimization Strategy for Recursive Queries in Logic Databases. ICDE 1988: 470-477 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[47]
...
[48]
Robert Endre Tarjan: Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1(2): 146-160(1972) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[49]
...
[50]
Patrick Valduriez, Haran Boral: Evaluation of Recursive Queries Using Join Indices. Expert Database Conf. 1986: 271-293 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[51]
Laurent Vieille: Recursive Axioms in Deductive Databases: The Query/Subquery Approach. Expert Database Conf. 1986: 253-267 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[53]
Stephen Warshall: A Theorem on Boolean Matrices. J. ACM 9(1): 11-12(1962) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[54]
Cheong Youn, Lawrence J. Henschen, Jiawei Han: Classification of Recursive Formulas in Deductive Databases. SIGMOD Conference 1988: 320-328 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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

Copyright © Mon Nov 2 20:43:09 2009 by Michael Ley (ley@uni-trier.de)