Distributed Transitive Closure Computations: The Disconnection Set Approach.

@inproceedings{DBLP:conf/vldb/HoutsmaAC90,
  author    = {Maurice A. W. Houtsma and
               Peter M. G. Apers and
               Stefano Ceri},
  editor    = {Dennis McLeod and
               Ron Sacks-Davis and
               Hans-J{\"o}rg Schek},
  title     = {Distributed Transitive Closure Computations: The Disconnection
               Set Approach},
  booktitle = {16th International Conference on Very Large Data Bases, August
               13-16, 1990, Brisbane, Queensland, Australia, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1990},
  isbn      = {1-55860-149-X},
  pages     = {335-346},
  ee        = {db/conf/vldb/HoutsmaAC90.html},
  crossref  = {DBLP:conf/vldb/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper deals with one of the most common and important types of recursion:transitive closure. Since many real world problems reduce to generalized transitive closure computations, efficient computation is essential. To gain a significant speedup in processing, we consider distributed (i.e. parallel) computation.

By fragmenting the data beforehand according to rules stemming from the application domain, queries can be split into several independent subqueries. These subqueries are computed in parallel on only a part of the data and are more specialized in the sense that extra selections are applied on each fragment. The disconnection set approach introduced in this paper takes benefit from such a fragmentation; it is applicable to several queries that are based on transitive closure, such as connectivity, shortest path, and bill of materials. Moreover, it may be generalized to work for other application domains. Since we consider real world problems to deal with a large updatable volume ofdata, we take an algebraic approach to computation of queries. Our proposal is such that updates will, in general, not affect the fragmentation. This is also explained in the paper.

Some preliminary simulations are included in the paper as well. They show that our approach leads to a speedup that is almost proportional to the number of processors, without significant overhead.

Copyright © 1990 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

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/vldb8997 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: Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries. IEEE Trans. Software Eng. 14(7): 879-885(1988)

[2]

Rakesh Agrawal, Alexander Borgida, H. V. Jagadish: Efficient Management of Transitive Relationships in Large Data and Knowledge Bases. SIGMOD Conference 1989: 253-262

[3]

Rakesh Agrawal, H. V. Jagadish: Efficient Search in Very Large Databases. VLDB 1988: 407-418

[4]

Rakesh Agrawal, H. V. Jagadish: Multiprocessor Transitive Closure Algorithms. DPDS 1988: 56-66

[5]

Peter M. G. Apers, Maurice A. W. Houtsma, Frank Brandse: Processing Recursive Queries in Relational Algebra. DS-2 1986: 17-39

[6]

Peter M. G. Apers, Martin L. Kersten, Hans Oerlemans: PRISMA Database Machine: A Distributed, Main-Memory Approach. EDBT 1988: 590-593

[7]

Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie Jr.: Query Processing in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 6(4): 602-625(1981)

[8]

...

[9]

Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3

[10]

Stefano Ceri, Georg Gottlob, Letizia Tanca: Logic Programming and Databases. Springer 1990, ISBN 3-540-51728-6

[11]

David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8

[12]

...

[13]

...

[14]

...

[15]

Maurice A. W. Houtsma, Peter M. G. Apers, Stefano Ceri: Complex Transitive Closure Queries on a Fragmented Graph. ICDT 1990: 470-484

[16]

...

[17]

Guy Hulin: Parallel Processing of Recursive Queries in Distributed Architectures. VLDB 1989: 87-96

[18]

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

[19]

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

[20]

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

[21]

Martin L. Kersten, Peter M. G. Apers, Maurice A. W. Houtsma, Erik J. A. van Kuyk, Rob L. W. van de Weg: A Distributed, Main-Memory Database Machine. IWDM 1987: 353-369

[22]

...

[23]

Per-Åke Larson, Vinay Deshpande: A File Structure Supporting Traversal Recursion. SIGMOD Conference 1989: 243-252

[24]

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

[25]

Louiqa Raschid, Stanley Y. W. Su: A Parallel Processing Strategy for Evaluating Recursive Queries. VLDB 1986: 412-419

[26]

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

[27]

Michael Stonebraker, Erich J. Neuhold: A Distributed Database Version of INGRES. Berkeley Workshop 1977: 19-36

[28]

Tandem Database Group - NonStop SQL: A Distributed, High-Performance, High-Availability Implementation of SQL. HPTS 1987: 60-104

[29]

Ouri Wolfson: Sharing the Load of Logic-Program Evaluation. DPDS 1988: 46-55