ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Distributed Transitive Closure Computations: The Disconnection Set Approach.

Maurice A. W. Houtsma, Peter M. G. Apers, Stefano Ceri: Distributed Transitive Closure Computations: The Disconnection Set Approach. VLDB 1990: 335-346
@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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Dennis McLeod, Ron Sacks-Davis, Hans-Jörg Schek (Eds.): 16th International Conference on Very Large Data Bases, August 13-16, 1990, Brisbane, Queensland, Australia, Proceedings. Morgan Kaufmann 1990, ISBN 1-55860-149-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Rakesh Agrawal, Alexander Borgida, H. V. Jagadish: Efficient Management of Transitive Relationships in Large Data and Knowledge Bases. SIGMOD Conference 1989: 253-262 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Rakesh Agrawal, H. V. Jagadish: Efficient Search in Very Large Databases. VLDB 1988: 407-418 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Rakesh Agrawal, H. V. Jagadish: Multiprocessor Transitive Closure Algorithms. DPDS 1988: 56-66 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Peter M. G. Apers, Maurice A. W. Houtsma, Frank Brandse: Processing Recursive Queries in Relational Algebra. DS-2 1986: 17-39 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Peter M. G. Apers, Martin L. Kersten, Hans Oerlemans: PRISMA Database Machine: A Distributed, Main-Memory Approach. EDBT 1988: 590-593 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
...
[9]
Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Stefano Ceri, Georg Gottlob, Letizia Tanca: Logic Programming and Databases. Springer 1990, ISBN 3-540-51728-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
...
[17]
Guy Hulin: Parallel Processing of Recursive Queries in Distributed Architectures. VLDB 1989: 87-96 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
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
[19]
Yannis E. Ioannidis, Raghu Ramakrishnan: Efficient Transitive Closure Algorithms. VLDB 1988: 382-394 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
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
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[22]
...
[23]
Per-Åke Larson, Vinay Deshpande: A File Structure Supporting Traversal Recursion. SIGMOD Conference 1989: 243-252 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
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
[25]
Louiqa Raschid, Stanley Y. W. Su: A Parallel Processing Strategy for Evaluating Recursive Queries. VLDB 1986: 412-419 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[26]
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
[27]
Michael Stonebraker, Erich J. Neuhold: A Distributed Database Version of INGRES. Berkeley Workshop 1977: 19-36 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[28]
Tandem Database Group - NonStop SQL: A Distributed, High-Performance, High-Availability Implementation of SQL. HPTS 1987: 60-104 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[29]
Ouri Wolfson: Sharing the Load of Logic-Program Evaluation. DPDS 1988: 46-55 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:22:01 2010 by Michael Ley (ley@uni-trier.de)