Graph-Theoretic Methods in Database Theory.

@inproceedings{DBLP:conf/pods/Yannakakis90,
  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        = {http://doi.acm.org/10.1145/298514.298576, db/conf/pods/Yannakakis90.html},
  crossref  = {DBLP:conf/pods/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

• 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
• UNIX/LINUX/Mac: use mount point /pods8298/... 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
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[AP]

Foto N. Afrati, Christos H. Papadimitriou: The Parallel Complexity of Simple Chain Queries. PODS 1987: 210-213 BibTeX

[AAK]

Alok Aggarwal, Richard J. Anderson, Ming-Yang Kao: Parallel Depth-First Search in General Directed Graphs (Preliminary Version). STOC 1989: 297-308 BibTeX

[ACS]

Alok Aggarwal, Ashok K. Chandra, Marc Snir: Hierarchical Memory with Block Transfer. FOCS 1987: 204-216 BibTeX

[A]

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

[AJ]

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

[AHU]

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

[ASU]

Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Compilers: Princiles, Techniques, and Tools. Addison-Wesley 1986, ISBN 0-201-10088-6
BibTeX

[AU]

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

[A+]

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

[BMSU]

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

[BR]

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

[BKBR]

Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. PODS 1987: 214-226 BibTeX

[BR]

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

[BS]

Joachim Biskup, Holger Stiefeling: Transitive Closure Algorithms for Very Large Databases. WG 1988: 122-147 BibTeX

[BFM]

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

[BKV]

...

[C]

...

[CW]

Don Coppersmith, Shmuel Winograd: Matrix Multiplication via Arithmetic Progressions. STOC 1987: 1-6 BibTeX

[CK]

Stavros S. Cosmadakis, Paris C. Kanellakis: Parallel Evaluation of Recursive Rule Queries. PODS 1986: 280-293 BibTeX

[CMW]

Isabel F. Cruz, Alberto O. Mendelzon, Peter T. Wood: A Graphical Query Language Supporting Recursion. SIGMOD Conference 1987: 323-330 BibTeX

[DKS]

Cynthia Dwork, Paris C. Kanellakis, Larry J. Stockmeyer: Parallel Algorithms for Term Matching. SIAM J. Comput. 17(4): 711-731(1988) BibTeX

[FHW]

Steven Fortune, John E. Hopcroft, James Wyllie: The Directed Subgraph Homeomorphism Problem. Theor. Comput. Sci. 10: 111-121(1980) BibTeX

[GM]

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

[GS]

Nathan Goodman, Oded Shmueli: The Tree Property is Fundamental for Query Processing. PODS 1982: 40-48 BibTeX

[GSS]

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

[HaN]

Ramsey W. Haddad, Jeffrey F. Naughton: Counting Methods for Cyclic Relations. PODS 1988: 333-340 BibTeX

[NeN]

Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX

[Ho]

Gerard J. Holzmann: An Improved Protocol Reachability Analysis Technique. Softw., Pract. Exper. 18(2): 137-161(1988) BibTeX

[HK]

Jia-Wei Hong, H. T. Kung: I/O Complexity: The Red-Blue Pebble Game. STOC 1981: 326-333 BibTeX

[HSU]

Harry B. Hunt III, Thomas G. Szymanski, Jeffrey D. Ullman: Operations on Sparse Relations. Commun. ACM 20(3): 171-176(1977) BibTeX

[IK]

Toshihide Ibaraki, Naoki Katoh: On-Line Computation of Transitive Closures of Graphs. Inf. Process. Lett. 16(2): 95-97(1983) BibTeX

[I]

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

[IR]

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

[It1]

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

[It2]

Giuseppe F. Italiano: Finding Paths and Deleting Edges in Directed Acyclic Graphs. Inf. Process. Lett. 28(1): 5-11(1988) BibTeX

[Im]

Neil Immerman: Nondeterministic Space is Closed Under Complementation. SIAM J. Comput. 17(5): 935-938(1988) BibTeX

[JAN]

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

[K]

...

[KS]

Ming-Yang Kao, Gregory E. Shannon: Local Reorientation, Global Order, and Planar Topology (Preliminary Version). STOC 1989: 286-296 BibTeX

[LN]

Richard J. Lipton, Jeffrey F. Naughton: Estimating the Size of Generalized Transitive Closures. VLDB 1989: 165-171 BibTeX

[L]

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

[MPS]

Alberto Marchetti-Spaccamela, Antonella Pelaggi, Domenico Saccà: Worst-case Complexity Analysis of Methods for Logic Query Implementation. PODS 1987: 294-301 BibTeX

[MC]

...

[MW]

Alberto O. Mendelzon, Peter T. Wood: Finding Regular Simple Paths in Graph Databases. VLDB 1989: 185-193 BibTeX

[N]

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

[NRSU]

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

[RS]

...

[SZ1]

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

[SZ2]

Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. Theor. Comput. Sci. 62(1-2): 187-220(1988) BibTeX

[S]

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

[SeV]

Robert Sedgewick, Jeffrey Scott Vitter: Shortest Paths in Euclidean Graphs (Extended Abstract). FOCS 1984: 417-424 BibTeX

[SV]

Yossi Shiloach, Uzi Vishkin: An O(log n) Parallel Connectivity Algorithm. J. Algorithms 3(1): 57-67(1982) BibTeX

[Sh]

Oded Shmueli: Dynamic Cycle Detection. Inf. Process. Lett. 17(4): 185-188(1983) BibTeX

[Si]

Klaus Simon: An Improved Algorithm for Transitive Closure on Acyclic Digraphs. ICALP 1986: 376-386 BibTeX

[SS1]

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

[SS2]

Seppo Sippu, Eljas Soisalon-Soininen: A Generalized Transitive Closure for Relational Queries. PODS 1988: 325-332 BibTeX

[Sz]

...

[SU]

Thomas G. Szymanski, Jeffrey D. Ullman: Evaluating Relational Expressions with Dense and Sparse Arguments. SIAM J. Comput. 6(1): 109-122(1977) BibTeX

[T1]

Robert Endre Tarjan: A Unified Approach to Path Problems. J. ACM 28(3): 577-593(1981) BibTeX

[T2]

Robert Endre Tarjan: Fast Algorithms for Solving Path Problems. J. ACM 28(3): 594-614(1981) BibTeX

[TY]

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

[To]

Martin Tompa: Two Familiar Transitive Closure Algorithms which Admit No Polynomial Time, Sublinear Space Implementations. STOC 1980: 333-338 BibTeX

[U1]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX

[U2]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX

[UV]

Jeffrey D. Ullman, Allen Van Gelder: Parallel Complexity of Logical Query Programs. FOCS 1986: 438-454 BibTeX

[UY1]

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

[UY2]

Jeffrey D. Ullman, Mihalis Yannakakis: High-Probability Parallel Transitive-Closure Algorithms. SIAM J. Comput. 20(1): 100-125(1991) BibTeX

[VK]

...

[V]

Leslie G. Valiant: General Context-Free Recognition in Less than Cubic Time. J. Comput. Syst. Sci. 10(2): 308-315(1975) BibTeX

[W1]

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

[W2]

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

[Z]

...

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