Distributed Query Processing in a Relational Data Base System.

@inproceedings{DBLP:conf/sigmod/EpsteinSW78,
  author    = {Robert S. Epstein and
               Michael Stonebraker and
               Eugene Wong},
  editor    = {Eugene I. Lowenthal and
               Nell B. Dale},
  title     = {Distributed Query Processing in a Relational Data Base System},
  booktitle = {Proceedings of the 1978 ACM SIGMOD International Conference on
               Management of Data, Austin, Texas, May 31 - June 2, 1978},
  publisher = {ACM},
  year      = {1978},
  pages     = {169-180},
  ee        = {http://doi.acm.org/10.1145/509252.509292, db/conf/sigmod/EpsteinSW78.html},
  crossref  = {DBLP:conf/sigmod/78},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper we present a new algorithm for retrieving and updating data from a distributed relational data base. Within such a data base, any number of relations can be distributed over any number of sites. Moreover, a user supplied distribution criteria can optionally be used to specify what site a tuple belongs to.

The algorithm is an efficient way to process any query by "breaking" the qualification into separate "pieces" using a few simple heuristics. The cost criteria considered are minimum response time and minimum communications traffic. In addition, the algorithm can optimize separately for two models of a communication network representing respectively ARPANET and ETHERNET like networks. This algorithm is being implemented as part of the INGRES data base system.

Copyright © 1978 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

[CHAM76]

Donald D. Chamberlin: Relational Data-Base Management Systems. ACM Comput. Surv. 8(1): 43-66(1976) BibTeX

[CHU76]

...

[CODD70]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[HELD75]

...

[LAMP76]

Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565(1978) BibTeX

[METC76]

Robert Metcalfe, David Boggs: Ethernet: Distributed Packet Switching for Local Computer Networks. Commun. ACM 19(7): 395-404(1976) BibTeX

[ROBE70]

...

[ROTH77]

James B. Rothnie Jr., Nathan Goodman: An Overview of the Preliminary Design of SDD-1: A System for Distributed Databases. Berkeley Workshop 1977: 39-57 BibTeX

[STON75]

Michael Stonebraker: Implementation of Integrity Constraints and Views by Query Modification. SIGMOD Conference 1975: 65-78 BibTeX

[STON76]

Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX

[STON77]

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

[THOM75]

...

[WONG76]

Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX

[WONG77]

Eugene Wong: Retrieving Dispersed Data from SDD-1: A System for Distributed Databases. Berkeley Workshop 1977: 217-235 BibTeX

[YOUS78]

...

Referenced by

1. Damianos Chatziantoniou, Kenneth A. Ross: Groupwise Processing of Relational Queries. VLDB 1997: 476-485
2. Chengwen Liu, Hao Chen: A Hash Partition Strategy for Distributed Query Processing. EDBT 1996: 373-387
3. Marjorie Templeton, Herbert Henley, Edward Maros, Darrel J. Van Buer: InterViso: Dealing With the Complexity of Federated Database Access. VLDB J. 4(2): 287-317(1995)
4. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
   Contents
5. Michael Stonebraker, Paul M. Aoki, Robert Devine, Witold Litwin, Michael A. Olson: Mariposa: A New Architecture for Distributed Data. ICDE 1994: 54-65
6. Jörg Liebeherr, Edward Omiecinski, Ian F. Akyildiz: The Effect of Index Partitioning Schemes on the Performance of Distributed Query Processing. IEEE Trans. Knowl. Data Eng. 5(3): 510-522(1993)
7. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
8. Ambuj Shatdal, Jeffrey F. Naughton: Using Shared Virtual Memory for Parallel Join Processing. SIGMOD Conference 1993: 119-128
9. Michael Stonebraker: The Integration of Rule Systems and Database Systems. IEEE Trans. Knowl. Data Eng. 4(5): 415-423(1992)
10. David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider, S. Seshadri: Practical Skew Handling in Parallel Joins. VLDB 1992: 27-40
11. Clement T. Yu, Chengwen Liu: Experiences with Distributed Query Processing. ICDE 1990: 192-199
12. Arbee L. P. Chen: A Localized Approach to Distributed Query Processing. EDBT 1990: 188-202
13. Sreekumar T. Shenoy, Z. Meral Özsoyoglu: Design and Implementation of a Semantic Query Optimizer. IEEE Trans. Knowl. Data Eng. 1(3): 344-361(1989)
14. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
15. Peter M. G. Apers: Data Allocation in Distributed Database Systems. ACM Trans. Database Syst. 13(3): 263-304(1988)
16. Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27
17. Fang Li, Lawrence V. Saxton: Two-Way Join Optimization in Partitioned Database Systems. ICDT 1988: 191-204
18. Sreekumar T. Shenoy, Z. Meral Özsoyoglu: A System for Semantic Query Optimization. SIGMOD Conference 1987: 181-195
19. Yannis E. Ioannidis, Eugene Wong: Query Optimization by Simulated Annealing. SIGMOD Conference 1987: 9-22
20. Arie Segev: Optimization of Join Operations in Horizontally Partitioned Database Systems. ACM Trans. Database Syst. 11(1): 48-80(1986)
21. Giovanni Maria Sacco: Fragmentation: A Technique for Efficient Query Processing. ACM Trans. Database Syst. 11(2): 113-133(1986)
22. Stéphane Lafortune, Eugene Wong: A State Transition Model for Distributed Query Processing. ACM Trans. Database Syst. 11(3): 294-322(1986)
23. Bezalel Gavish, Arie Segev: Set Query Optimization in Distributed Database Systems. ACM Trans. Database Syst. 11(3): 265-293(1986)
24. Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Distributed Queries. VLDB 1986: 149-159
25. Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Local Queries. SIGMOD Conference 1986: 84-95
26. Michael J. Carey, Hongjun Lu: Load Balancing in a Locally Distributed Database System. SIGMOD Conference 1986: 108-119
27. Clement T. Yu, Leszek Lilien, Keh-Chang Guh, Marjorie Templeton, David Brill, Arbee L. P. Chen: Adaptive Techniques for Distributed Query Optimization. ICDE 1986: 86-93
28. Marjorie Templeton, David Brill, Arbee L. P. Chen, Son Dao, Eric Lund: Mermaid - Experiences with Network Operation. ICDE 1986: 292-300
29. Thomas W. Page Jr., Matthew J. Weinstein, Gerald J. Popek: Genesis: A Distributed Database Operating System. SIGMOD Conference 1985: 374-387
30. Thomas W. Page Jr., Gerald J. Popek: Distributed Management in Local Area Networks. PODS 1985: 135-142
31. Clement T. Yu, C. C. Chang: Distributed Query Processing. ACM Comput. Surv. 16(4): 399-433(1984)
32. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
33. Guy M. Lohman, Dean Daniels, Laura M. Haas, Ruth Kistler, Patricia G. Selinger: Optimization of Nested Queries in a Distributed Relational Database. VLDB 1984: 403-415
34. S. Misbah Deen, R. R. Amin, Malcolm C. Taylor: A Strategy for Decomposing Complex Queries in a Heterogeneous DDB. VLDB 1984: 397-400
35. Hai-Yann Hwang, Umeshwar Dayal, Mohamed G. Gouda: Using Semiouterjoins to Process Queries in Multidatabase Systems. PODS 1984: 153-162
36. Giovanni Maria Sacco: Distributed Query Evaluation in Local Area Networks. ICDE 1984: 510-516
37. David Brill, Marjorie Templeton, Clement T. Yu: Distributed Query Processing Strategies in Mermaid, A Frontend to Data Management Systems. ICDE 1984: 211-218
38. Stefano Ceri, Giuseppe Pelagatti: Correctness of Query Execution Strategies in Distributed Databases. ACM Trans. Database Syst. 8(4): 577-607(1983)
39. Umeshwar Dayal: Processing Queries Over Generalization Hierarchies in a Multidatabase System. VLDB 1983: 342-353
40. David Maier, Jeffrey D. Ullman: Fragments of Relations. SIGMOD Conference 1983: 15-22
41. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
42. Larry Kerschberg, Peter D. Ting, S. Bing Yao: Query Optimization in Star Computer Networks. ACM Trans. Database Syst. 7(4): 678-711(1982)
43. Nathan Goodman, Oded Shmueli: Tree Queries: A Simple Class of Relational Queries. ACM Trans. Database Syst. 7(4): 653-677(1982)
44. 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)
45. Philippe Richard: Evaluation of the Size of a Query Expressed in Relational Algebra. SIGMOD Conference 1981: 155-163
46. R. McCord: Sizing and Data Distribution for a Distributed Database Machine. SIGMOD Conference 1981: 198-204
47. Michael Stonebraker: Retrospection on a Database System. ACM Trans. Database Syst. 5(2): 225-240(1980)
48. Robert S. Epstein, Michael Stonebraker: Analysis of Distributed Data Base Processing Strategies. VLDB 1980: 92-101
49. Won Kim: Relational Database Systems. ACM Comput. Surv. 11(3): 187-211(1979)
50. Clement T. Yu, K. Lam, M. K. Siu, Z. Meral Özsoyoglu: Performance Analysis of three Related Assignment Problems. SIGMOD Conference 1979: 82-92