Graph-Theoretic Methods in Database Theory.

Mihalis Yannakakis: Graph-Theoretic Methods in Database Theory. PODS 1990: 230-242
  author    = {Mihalis Yannakakis},
  title     = {Graph-Theoretic Methods in Database Theory},
  booktitle = {Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee},
  publisher = {ACM Press},
  year      = {1990},
  isbn      = {0-89791-352-3},
  pages     = {230-242},
  ee        = {, db/conf/pods/Yannakakis90.html},
  crossref  = {DBLP:conf/pods/90},
  bibsource = {DBLP,}
Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee. ACM Press 1990, ISBN 0-89791-352-3
Contents BibTeX

Online Edition: ACM Digital Library


Foto N. Afrati, Christos H. Papadimitriou: The Parallel Complexity of Simple Chain Queries. PODS 1987: 210-213 BibTeX
Alok Aggarwal, Richard J. Anderson, Ming-Yang Kao: Parallel Depth-First Search in General Directed Graphs (Preliminary Version). STOC 1989: 297-308 BibTeX
Alok Aggarwal, Ashok K. Chandra, Marc Snir: Hierarchical Memory with Block Transfer. FOCS 1987: 204-216 BibTeX
Rakesh Agrawal: Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries. ICDE 1987: 580-590 BibTeX
Rakesh Agrawal, H. V. Jagadish: Direct Algorithms for Computing the Transitive Closure of Database Relations. VLDB 1987: 255-266 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
Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Compilers: Princiles, Techniques, and Tools. Addison-Wesley 1986, ISBN 0-201-10088-6
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, Charles Rackoff: Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems. FOCS 1979: 218-223 BibTeX
François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 BibTeX
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. PODS 1987: 214-226 BibTeX
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 BibTeX
Joachim Biskup, Holger Stiefeling: Transitive Closure Algorithms for Very Large Databases. WG 1988: 122-147 BibTeX
Peter A. Bloniarz, Michael J. Fischer, Albert R. Meyer: A Note on the Average Time to Compute Transitive Closures. ICALP 1976: 425-434 BibTeX
Don Coppersmith, Shmuel Winograd: Matrix Multiplication via Arithmetic Progressions. STOC 1987: 1-6 BibTeX
Stavros S. Cosmadakis, Paris C. Kanellakis: Parallel Evaluation of Recursive Rule Queries. PODS 1986: 280-293 BibTeX
Isabel F. Cruz, Alberto O. Mendelzon, Peter T. Wood: A Graphical Query Language Supporting Recursion. SIGMOD Conference 1987: 323-330 BibTeX
Cynthia Dwork, Paris C. Kanellakis, Larry J. Stockmeyer: Parallel Algorithms for Term Matching. SIAM J. Comput. 17(4): 711-731(1988) BibTeX
Steven Fortune, John E. Hopcroft, James Wyllie: The Directed Subgraph Homeomorphism Problem. Theor. Comput. Sci. 10: 111-121(1980) BibTeX
Hillel Gazit, Gary L. Miller: An Improved Parallel Algorithm that Computes the BFS Numbering of a Directed Graph. Inf. Process. Lett. 28(2): 61-65(1988) BibTeX
Nathan Goodman, Oded Shmueli: The Tree Property is Fundamental for Query Processing. PODS 1982: 40-48 BibTeX
Gösta Grahne, Seppo Sippu, Eljas Soisalon-Soininen: Efficient Evaluation for a Subset of Recursive Queries. PODS 1987: 284-293 BibTeX
Ramsey W. Haddad, Jeffrey F. Naughton: Counting Methods for Cyclic Relations. PODS 1988: 333-340 BibTeX
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
Gerard J. Holzmann: An Improved Protocol Reachability Analysis Technique. Softw., Pract. Exper. 18(2): 137-161(1988) BibTeX
Jia-Wei Hong, H. T. Kung: I/O Complexity: The Red-Blue Pebble Game. STOC 1981: 326-333 BibTeX
Harry B. Hunt III, Thomas G. Szymanski, Jeffrey D. Ullman: Operations on Sparse Relations. Commun. ACM 20(3): 171-176(1977) BibTeX
Toshihide Ibaraki, Naoki Katoh: On-Line Computation of Transitive Closures of Graphs. Inf. Process. Lett. 16(2): 95-97(1983) 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
Giuseppe F. Italiano: Finding Paths and Deleting Edges in Directed Acyclic Graphs. Inf. Process. Lett. 28(1): 5-11(1988) BibTeX
Neil Immerman: Nondeterministic Space is Closed Under Complementation. SIAM J. Comput. 17(5): 935-938(1988) BibTeX
H. V. Jagadish, Rakesh Agrawal, Linda Ness: A Study of Transitive Closure As a Recursion Mechanism. SIGMOD Conference 1987: 331-344 BibTeX
Ming-Yang Kao, Gregory E. Shannon: Local Reorientation, Global Order, and Planar Topology (Preliminary Version). STOC 1989: 286-296 BibTeX
Richard J. Lipton, Jeffrey F. Naughton: Estimating the Size of Generalized Transitive Closures. VLDB 1989: 165-171 BibTeX
Hongjun Lu: New Strategies for Computing the Transitive Closure of a Database Relation. VLDB 1987: 267-274 BibTeX
Alberto Marchetti-Spaccamela, Antonella Pelaggi, Domenico Saccà: Worst-case Complexity Analysis of Methods for Logic Query Implementation. PODS 1987: 294-301 BibTeX
Alberto O. Mendelzon, Peter T. Wood: Finding Regular Simple Paths in Graph Databases. VLDB 1989: 185-193 BibTeX
Jeffrey F. Naughton: One-Sided Recursions. PODS 1987: 340-348 BibTeX
Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules. SIGMOD Conference 1989: 235-242 BibTeX
Domenico Saccà, Carlo Zaniolo: Magic Counting Methods. SIGMOD Conference 1987: 49-59 BibTeX
Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. Theor. Comput. Sci. 62(1-2): 187-220(1988) BibTeX
Claus-Peter Schnorr: An Algorithm for Transitive Closure with Linear Expected Time. SIAM J. Comput. 7(2): 127-133(1978) BibTeX
Robert Sedgewick, Jeffrey Scott Vitter: Shortest Paths in Euclidean Graphs (Extended Abstract). FOCS 1984: 417-424 BibTeX
Yossi Shiloach, Uzi Vishkin: An O(log n) Parallel Connectivity Algorithm. J. Algorithms 3(1): 57-67(1982) BibTeX
Oded Shmueli: Dynamic Cycle Detection. Inf. Process. Lett. 17(4): 185-188(1983) BibTeX
Klaus Simon: An Improved Algorithm for Transitive Closure on Acyclic Digraphs. ICALP 1986: 376-386 BibTeX
Seppo Sippu, Eljas Soisalon-Soininen: An Optimization Strategy for Recursive Queries in Logic Databases. ICDE 1988: 470-477 BibTeX
Seppo Sippu, Eljas Soisalon-Soininen: A Generalized Transitive Closure for Relational Queries. PODS 1988: 325-332 BibTeX
Thomas G. Szymanski, Jeffrey D. Ullman: Evaluating Relational Expressions with Dense and Sparse Arguments. SIAM J. Comput. 6(1): 109-122(1977) BibTeX
Robert Endre Tarjan: A Unified Approach to Path Problems. J. ACM 28(3): 577-593(1981) BibTeX
Robert Endre Tarjan: Fast Algorithms for Solving Path Problems. J. ACM 28(3): 594-614(1981) BibTeX
Robert Endre Tarjan, Mihalis Yannakakis: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. SIAM J. Comput. 13(3): 566-579(1984) BibTeX
Martin Tompa: Two Familiar Transitive Closure Algorithms which Admit No Polynomial Time, Sublinear Space Implementations. STOC 1980: 333-338 BibTeX
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
Jeffrey D. Ullman, Allen Van Gelder: Parallel Complexity of Logical Query Programs. FOCS 1986: 438-454 BibTeX
Jeffrey D. Ullman, Mihalis Yannakakis: The Input/Output Complexity of Transitive Closure. SIGMOD Conference 1990: 44-53 BibTeX
Jeffrey D. Ullman, Mihalis Yannakakis: High-Probability Parallel Transitive-Closure Algorithms. SIAM J. Comput. 20(1): 100-125(1991) BibTeX
Leslie G. Valiant: General Context-Free Recognition in Less than Cubic Time. J. Comput. Syst. Sci. 10(2): 308-315(1975) BibTeX
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
Stephen Warshall: A Theorem on Boolean Matrices. J. ACM 9(1): 11-12(1962) BibTeX

Referenced by

  1. Sergio Flesca, Sergio Greco: Querying Graph Databases. EDBT 2000: 510-524
  2. Shaul Dar, Raghu Ramakrishnan: A Performance Study of Transitive Closure Algorithms. SIGMOD Conference 1994: 454-465
  3. Håkan Jakobsson: On Tree-Based Techniques for Query Evaluation. PODS 1992: 380-392
  4. Inderpal Singh Mumick, Hamid Pirahesh: Overbound and Right-Linear Queries. PODS 1991: 127-141
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:34:00 2009