The Input/Output Complexity of Transitive Closure.

@inproceedings{DBLP:conf/sigmod/UllmanY90,
  author    = {Jeffrey D. Ullman and
               Mihalis Yannakakis},
  editor    = {Hector Garcia-Molina and
               H. V. Jagadish},
  title     = {The Input/Output Complexity of Transitive Closure},
  booktitle = {Proceedings of the 1990 ACM SIGMOD International Conference on
               Management of Data, Atlantic City, NJ, May 23-25, 1990},
  publisher = {ACM Press},
  year      = {1990},
  pages     = {44-53},
  ee        = {http://doi.acm.org/10.1145/93597.93620, db/conf/sigmod/UllmanY90.html},
  crossref  = {DBLP:conf/sigmod/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Suppose a directed graph has its arcs stored in secondary memory, and we wish to compute its transitive closure, also storing the result in secondary memory. We assume that an amount of main memory capable of holding s "values" is available, and that s lies between n, the number of nodes of the graph, and e, the number of arcs. The cost measure we use for algorithms is the I/O complexity of Kung and Hong, where we count 1 every time a value is moved into main memory from secondary memory, or vice versa.

In the dense case, where e is close to n², we show that I/O equal to O(n³sqrt(s)) is sufficient to compute the transitive closure of an n-node graph, using main memory of size s. Moreover, it is necessary for any algorithm that is "standard," in a sense to be defined precisely in the paper. Roughly, "standard" means that paths are constructed only by concatenating arcs and previously discovered paths. This class includes the usual algorithms that work for the generalization of transitive closure to semiring problems. For the sparse case, we show that I/O equal to O(n²sqrt(e/s)) is sufficient, although the algorithm we propose meets our definition of "standard" only if the underlying graph is acyclic. We also show that Omega(n²sqrt(e/s)) is necessary for any standard algorithm in the sparse case. That settles the I/O complexity of the sparse/acyclic case, for standard algorithms. It is unknown whether this complexity can be achieved in the sparse, cyclic case, by a standard algorithm, and it is unknown whether the bound can be beaten by nonstandard algorithms.

We then consider a special kind of standard algorithm, in which paths are constructed only by concatenating arcs and old paths, never by concatenating two old paths. This restriction seems essential if we are to take advantage of sparseness. Unfortunately, we show that almost another factor of n I/O is necessary. That is, there is an algorithm in this class using I/O O(n³sqrt(e/s)) for arbitrary sparse graphs, including cyclic ones. Moreover, every algorithm in the restricted class must use Omega(n³sqrt(e/s)/ log³ n) I/O, on some cyclic graphs.

Copyright © 1990 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

• 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/smod7592 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

Online Edition: ACM Digital Library

References

[Agrawal, Jagadish 1987]

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

[Aho, Hopcroft, Ullman 1974]

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

[Benes 1965]

...

[Coppersmith, Winograd 1987]

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

[Hong, Kung 1980]

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

[Hopcroft, Tarjan 1973]

John E. Hopcroft, Robert Endre Tarjan: Efficient Algorithms for Graph Manipulation [H] (Algorithm 447). Commun. ACM 16(6): 372-378(1973) BibTeX

[Ioannidis, Ramakrishnan 1988]

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

[Lovasz 1979]

...

[McKellar, Coffman 1969]

...

[Ullman 1988]

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

[Ullman 1989]

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

[Warren 1975]

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

[Warshall 1962]

Stephen Warshall: A Theorem on Boolean Matrices. J. ACM 9(1): 11-12(1962) 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. Shaul Dar, Raghu Ramakrishnan: A Performance Study of Transitive Closure Algorithms. SIGMOD Conference 1994: 454-465
3. 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
4. Ouri Wolfson, Aya Ozeri: Parallel and Distributed Processing of Rules by Data Reduction. IEEE Trans. Knowl. Data Eng. 5(3): 523-530(1993)
5. Shaul Dar, Rakesh Agrawal: Extending SQL with Generalized Transitive Closure Functionality. IEEE Trans. Knowl. Data Eng. 5(5): 799-812(1993)
6. Håkan Jakobsson: On Tree-Based Techniques for Query Evaluation. PODS 1992: 380-392
7. Vinay S. Pai, Peter J. Varman: Prefetching with Multiple Disks for External Mergesort: Simulation and Analysis. ICDE 1992: 273-282
8. Shaul Dar, H. V. Jagadish: A Spanning Tree Transitive Closure Algorithm. ICDE 1992: 2-11
9. Steve Taylor, Nabil I. Hachem: A Direct Algorithm for Computing the Transitive Closure of a Two-Dimensionally Structured File. MFDBS 1991: 146-159
10. Shaul Dar, Rakesh Agrawal, H. V. Jagadish: Optimization of Generalized Transitive Closure Queries. ICDE 1991: 345-354
11. Chris Clifton, Hector Garcia-Molina: Indexing in a Hypertext Database. VLDB 1990: 36-49
12. Rakesh Agrawal, H. V. Jagadish: Hybrid Transitive Closure Algorithms. VLDB 1990: 326-334
13. Mihalis Yannakakis: Graph-Theoretic Methods in Database Theory. PODS 1990: 230-242