ACM SIGMOD Anthology TODS dblp.uni-trier.de

Query Processing in a System for Distributed Databases (SDD-1).

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)
@article{DBLP:journals/tods/BernsteinGWRR81,
  author    = {Philip A. Bernstein and
               Nathan Goodman and
               Eugene Wong and
               Christopher L. Reeve and
               James B. Rothnie Jr.},
  title     = {Query Processing in a System for Distributed Databases (SDD-1)},
  journal   = {ACM Trans. Database Syst.},
  volume    = {6},
  number    = {4},
  year      = {1981},
  pages     = {602-625},
  ee        = {http://doi.acm.org/10.1145/319628.319650, db/journals/tods/BernsteinGWRR81.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper describes the techniques used to optimize relational queries in the SDD-1 distributed database system. Queries are submitted to SDD-1 in a high-level procedural language called Datalanguage. Optimization begins by translating each Datalanguage query into a relational calculus form called an envelope, which is essentially an aggregate-free QUEL query. This paper is primarily concerned with the optimization of envelopes.

Envelopes are processed in two phases. The first phase executes relational operations at various sites of the distributed database in order to delimit a subset of the database that contains all data relevant to the envelope. This subset is called a reduction of the database. The second phase transmits the reduction to one designated site, and the query is executed locally at that site.

The critical optimization problem is to perform the reduction phase efficiently. Success depends on designing a good repertoire of operators to use during this phase, and an effective algorithm for deciding which of these operators to use in processing a given envelope against a given database. The principal reduction operator that we employ is called a semjoin. In this paper we define the semijoin operator, explain why semijoin is an effective reduction operator, and present an algorithm that constructs a cost-effective program of semijoins, given an envelope and a database.

Copyright © 1981 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.


Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[1]
Edward Babb: Implementing a Relational Database by Means of Specialized Hardware. ACM Trans. Database Syst. 4(1): 1-29(1979) BibTeX
[2]
Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) BibTeX
[3]
Philip A. Bernstein, Nathan Goodman: Power of Natural Semijoins. SIAM J. Comput. 10(4): 751-771(1981) BibTeX
[4]
Philip A. Bernstein, Nathan Goodman: The power of inequality semijoins. Inf. Syst. 6(4): 255-265(1981) BibTeX
[5]
Philip A. Bernstein, David W. Shipman: The Correctness of Concurrency Control Mechanisms in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 52-68(1980) BibTeX
[6]
Philip A. Bernstein, David W. Shipman, James B. Rothnie Jr.: Concurrency Control in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 18-51(1980) BibTeX
[7]
...
[8]
D. M. Chiu, Y. C. Ho: A Methodology for Interpreting Tree Queries Into Optimal Semi-Join Expressions. SIGMOD Conference 1980: 169-178 BibTeX
[9]
C. J. Date: An Introduction to Database Systems, 2nd Edition. Addison-Wesley 1977
BibTeX
[10]
Robert S. Epstein, Michael Stonebraker, Eugene Wong: Distributed Query Processing in a Relational Data Base System. SIGMOD Conference 1978: 169-180 BibTeX
[11]
...
[12]
Nathan Goodman, Oded Shmueli: Tree Queries: A Simple Class of Relational Queries. ACM Trans. Database Syst. 7(4): 653-677(1982) BibTeX
[13]
Mohamed G. Gouda, Umeshwar Dayal: Optimal Semijoin Schedules For Query Processing in Local Distributed Database Systems. SIGMOD Conference 1981: 164-175 BibTeX
[14]
Michael Hammer, David W. Shipman: Reliability Mechanisms for SDD-1: A System for Distributed Databases. ACM Trans. Database Syst. 5(4): 431-466(1980) BibTeX
[15]
...
[16]
...
[17]
Alan R. Hevner, S. Bing Yao: Query Processing in Distributed Database Systems. IEEE Trans. Software Eng. 5(3): 177-187(1979) BibTeX
[18]
...
[19]
Larry Kerschberg, Peter D. Ting, S. Bing Yao: Query Optimization in Star Computer Networks. ACM Trans. Database Syst. 7(4): 678-711(1982) BibTeX
[20]
...
[21]
Esen A. Ozkarahan, Stewart A. Schuster, Kenneth C. Sevcik: Performance Evaluation of a Relational Associative Processor. ACM Trans. Database Syst. 2(2): 175-195(1977) BibTeX
[22]
...
[23]
James B. Rothnie Jr., Philip A. Bernstein, Stephen Fox, Nathan Goodman, Michael Hammer, T. A. Landers, Christopher L. Reeve, David W. Shipman, Eugene Wong: Introduction to a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 1-17(1980) BibTeX
[24]
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
[25]
James B. Rothnie Jr., Nathan Goodman: A Survey of Research and Development in Distributed Database Management. VLDB 1977: 48-62 BibTeX
[26]
...
[27]
Patricia G. Selinger, Michel E. Adiba: Access Path Selection in Distributed Database Management Systems. ICOD 1980: 204-215 BibTeX
[28]
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX
[29]
Stanley Y. W. Su, Ahmed Emam: CASDAL: CASSM'a DAta Language. ACM Trans. Database Syst. 3(1): 57-91(1978) BibTeX
[30]
Eugene Wong: Retrieving Dispersed Data from SDD-1: A System for Distributed Databases. Berkeley Workshop 1977: 217-235 BibTeX
[31]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX
[32]
S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) BibTeX
[33]
...
[34]
...

Referenced by

  1. Ramana Yerneni, Chen Li, Jeffrey D. Ullman, Hector Garcia-Molina: Optimizing Large Join Queries in Mediation Systems. ICDT 1999: 348-364
  2. Gunter Saake, Andreas Heuer: Datenbanken: Implementierungstechniken. MITP-Verlag 1999, ISBN 3-8266-0513-6
    Contents
  3. Weiyi Meng, Clement T. Yu, Wei Wang, Naphtali Rishe: Performance Analysis of Three Text-Join Algorithms. IEEE Trans. Knowl. Data Eng. 10(3): 477-492(1998)
  4. Michael J. Carey, Donald Kossmann: Reducing the Braking Distance of an SQL Query Engine. VLDB 1998: 158-169
  5. Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998: 34-43
  6. Hubert Naacke, Georges Gardarin, Anthony Tomasic: Leveraging Mediator Cost Models with Heterogeneous Data Sources. ICDE 1998: 351-360
  7. Richard Hull: Managing Semantic Heterogeneity in Databases: A Theoretical Perspective. PODS 1997: 51-61
  8. Michael Stonebraker, Paul M. Aoki, Witold Litwin, Avi Pfeffer, Adam Sah, Jeff Sidell, Carl Staelin, Andrew Yu: Mariposa: A Wide-Area Distributed Database System. VLDB J. 5(1): 48-63(1996)
  9. Chihping Wang, Ming-Syan Chen: On the Complexity of Distributed Query Optimization. IEEE Trans. Knowl. Data Eng. 8(4): 650-662(1996)
  10. Praveen Seshadri, Joseph M. Hellerstein, Hamid Pirahesh, T. Y. Cliff Leung, Raghu Ramakrishnan, Divesh Srivastava, Peter J. Stuckey, S. Sudarshan: Cost-Based Optimization for Magic: Algebra and Implementation. SIGMOD Conference 1996: 435-446
  11. 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)
  12. Michael Steinbrunn, Klaus Peithner, Guido Moerkotte, Alfons Kemper: Bypassing Joins in Disjunctive Queries. VLDB 1995: 228-238
  13. Surajit Chaudhuri, Umeshwar Dayal, Tak W. Yan: Join Queries with External Text Sources: Execution and Optimization Techniques. SIGMOD Conference 1995: 410-422
  14. Zhe Li, Kenneth A. Ross: PERF Join: An Alternative to Two-way Semijoin and Bloomjoin. CIKM 1995: 137-144
  15. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  16. Ming-Syan Chen, Philip S. Yu: A Graph Theoretical Approach to Determine a Join Reducer Sequence in Distributed Query Processing. IEEE Trans. Knowl. Data Eng. 6(1): 152-165(1994)
  17. Michael Stonebraker, Paul M. Aoki, Robert Devine, Witold Litwin, Michael A. Olson: Mariposa: A New Architecture for Distributed Data. ICDE 1994: 54-65
  18. Peter Scheuermann, Eugene Inseok Chong: Role-based Query Processing in Multidatabase Systems. EDBT 1994: 95-108
  19. Wolfgang Nejdl, Stefano Ceri, Gio Wiederhold: Evaluating Recursive Queries in Distributed Databases. IEEE Trans. Knowl. Data Eng. 5(1): 104-121(1993)
  20. 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)
  21. Ming-Syan Chen, Philip S. Yu: Combining Join and Semi-Join Operations for Distributed Query Processing. IEEE Trans. Knowl. Data Eng. 5(3): 534-542(1993)
  22. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  23. Wouter B. Teeuw, Christian Rich, Marc H. Scholl, Henk M. Blanken: An Evaluation of Physical Disk I/Os for Complex Object Processing. ICDE 1993: 363-371
  24. Peter Bodorik, J. Spruce Riordon, James S. Pyra: Deciding on Correct Distributed Query Processing. IEEE Trans. Knowl. Data Eng. 4(3): 253-265(1992)
  25. Dennis Shasha, Jason Tsong-Li Wang: Optimizing Equijoin Queries In Distributed Databases Where Relations Are Hash Partitioned. ACM Trans. Database Syst. 16(2): 279-308(1991)
  26. Nick Roussopoulos, Hyunchul Kang: A Pipeline N-way Join Algorithm Based on the 2-way Semijoin Program. IEEE Trans. Knowl. Data Eng. 3(4): 486-495(1991)
  27. Arie Segev, J. Leon Zhao: Data Management for Large Rule Systems. VLDB 1991: 297-307
  28. Chihping Wang, Victor O. K. Li, Arbee L. P. Chen: Distributed Query Optimization by One-Shot Fixed-Precision Semi-Join Execution. ICDE 1991: 756-763
  29. Arie Segev, J. Leon Zhao: Evaluation of Rule Processing Strategies In Expert Databases. ICDE 1991: 404-412
  30. A. Y. Lu, Phillip C.-Y. Sheu: Processing of Multiple Queries in Distributed Databases. ICDE 1991: 42-49
  31. Sumit Ganguly, Ravi Krishnamurthy, Abraham Silberschatz: An Analysis Technique for Transitive Closure Algorithms: A Statistical Approach. ICDE 1991: 728-735
  32. Ming-Syan Chen, Philip S. Yu: Determining Beneficial Semijoins for a Join Sequence in Distributed Query Processing. ICDE 1991: 50-58
  33. HweeHwa Pang, Hongjun Lu, Beng Chin Ooi: Query Processing in OODB. DASFAA 1991: 1-10
  34. Won Kim, Jorge F. Garza, Nat Ballou, Darrell Woelk: Architecture of the ORION Next-Generation Database System. IEEE Trans. Knowl. Data Eng. 2(1): 109-124(1990)
  35. Maurice A. W. Houtsma, Peter M. G. Apers, Stefano Ceri: Distributed Transitive Closure Computations: The Disconnection Set Approach. VLDB 1990: 335-346
  36. Arie Segev, Weiping Fang: Currency-Based Updates to Distributed Materialized Views. ICDE 1990: 512-520
  37. Henk M. Blanken, Alle IJbema, Paul Meek, Bert van den Akker: The Generalized Grid File: Description and Performance Aspects. ICDE 1990: 380-388
  38. Arbee L. P. Chen: A Localized Approach to Distributed Query Processing. EDBT 1990: 188-202
  39. Sheau-Dong Lang, James R. Driscoll, Jiann H. Jou: A Unified Analysis of Batched Searching of Sequential and Tree-Structured Files. ACM Trans. Database Syst. 14(4): 604-618(1989)
  40. Hyuck Yoo, Stéphane Lafortune: An Intelligent Search Method for Query Optimization by Semijoins. IEEE Trans. Knowl. Data Eng. 1(2): 226-237(1989)
  41. Sreekumar T. Shenoy, Z. Meral Özsoyoglu: Design and Implementation of a Semantic Query Optimizer. IEEE Trans. Knowl. Data Eng. 1(3): 344-361(1989)
  42. Silvio Salza, Mario Terranova: Evaluating the Size of Queries on Relational Databases with non Uniform Distribution and Stochastic Dependence. SIGMOD Conference 1989: 8-14
  43. David A. Bell, D. H. O. Ling, Sally I. McClean: Pragmatic Estimation of Join Sizes and Attribute Correlations. ICDE 1989: 76-84
  44. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  45. Peter M. G. Apers: Data Allocation in Distributed Database Systems. ACM Trans. Database Syst. 13(3): 263-304(1988)
  46. Michael V. Mannino, Paicheng Chu, Thomas Sager: Statistical Profile Estimation in Database Systems. ACM Comput. Surv. 20(3): 191-221(1988)
  47. M. Muralikrishna, David J. DeWitt: Optimization of Multiple-Relation Multiple-Disjunct Queries. PODS 1988: 263-275
  48. Don S. Batory: Concepts for a Database System Compiler. PODS 1988: 184-192
  49. Fang Li, Lawrence V. Saxton: Two-Way Join Optimization in Partitioned Database Systems. ICDT 1988: 191-204
  50. Peter Bodorik, J. Spruce Riordon: Distributed Query Processing Optimization Objectives. ICDE 1988: 320-329
  51. Ming-Chien Shan: Optimal Plan Search in a Rule-Based Query Optimizer. EDBT 1988: 92-112
  52. Giovanni Maria Sacco: Index Access with a Finite Buffer. VLDB 1987: 301-309
  53. Mark Blakey: Basis of a Partially Informed Distributed Database. VLDB 1987: 381-388
  54. Sreekumar T. Shenoy, Z. Meral Özsoyoglu: A System for Semantic Query Optimization. SIGMOD Conference 1987: 181-195
  55. Yannis E. Ioannidis, Eugene Wong: Query Optimization by Simulated Annealing. SIGMOD Conference 1987: 9-22
  56. Hyunchul Kang, Nick Roussopoulos: Using 2-way Semijoins in Distributed Query Processing. ICDE 1987: 644-651
  57. Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986)
  58. Arie Segev: Optimization of Join Operations in Horizontally Partitioned Database Systems. ACM Trans. Database Syst. 11(1): 48-80(1986)
  59. Giovanni Maria Sacco, Mario Schkolnick: Buffer Management in Relational Database Systems. ACM Trans. Database Syst. 11(4): 473-498(1986)
  60. Stéphane Lafortune, Eugene Wong: A State Transition Model for Distributed Query Processing. ACM Trans. Database Syst. 11(3): 294-322(1986)
  61. Bezalel Gavish, Arie Segev: Set Query Optimization in Distributed Database Systems. ACM Trans. Database Syst. 11(3): 265-293(1986)
  62. Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Distributed Queries. VLDB 1986: 149-159
  63. Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Local Queries. SIGMOD Conference 1986: 84-95
  64. Michael J. Carey, Hongjun Lu: Load Balancing in a Locally Distributed Database System. SIGMOD Conference 1986: 108-119
  65. 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
  66. C. P. Wang, Victor O. K. Li: The Relation-Partitioning Approach to Processing Star Queries in Distributed Databases. ICDE 1986: 21-28
  67. Marjorie Templeton, David Brill, Arbee L. P. Chen, Son Dao, Eric Lund: Mermaid - Experiences with Network Operation. ICDE 1986: 292-300
  68. Alle IJbema, Henk M. Blanken: Estimating Bucket Accesses: A Practical Approach. ICDE 1986: 30-37
  69. Clement T. Yu, C. H. Chen: Adaptive Information System Design: One Query at a Time. SIGMOD Conference 1985: 280-290
  70. Thomas W. Page Jr., Gerald J. Popek: Distributed Management in Local Area Networks. PODS 1985: 135-142
  71. Shamkant B. Navathe, Stefano Ceri, Gio Wiederhold, Jinglie Dou: Vertical Partitioning Algorithms for Database Design. ACM Trans. Database Syst. 9(4): 680-710(1984)
  72. Clement T. Yu, C. C. Chang: Distributed Query Processing. ACM Comput. Surv. 16(4): 399-433(1984)
  73. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
  74. 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
  75. Ravi Krishnamurthy, Stephen P. Morgan: Query Processing on Personal Computers: A Pragmatic Approach (Extended Abstract). VLDB 1984: 26-29
  76. Arbee L. P. Chen, Victor O. K. Li: Optimizing Star Queries in a Distributed Database System. VLDB 1984: 429-438
  77. Matthias Jarke, James Clifford, Yannis Vassiliou: An Optimizing Prolog Front-End to a Relational Query System. SIGMOD Conference 1984: 296-306
  78. Huei-Huang Chen, Sharon McCure Kuck: Combining Relational and Network Retrieval Methods. SIGMOD Conference 1984: 131-142
  79. Hai-Yann Hwang, Umeshwar Dayal, Mohamed G. Gouda: Using Semiouterjoins to Process Queries in Multidatabase Systems. PODS 1984: 153-162
  80. Giovanni Maria Sacco: Distributed Query Evaluation in Local Area Networks. ICDE 1984: 510-516
  81. David Brill, Marjorie Templeton, Clement T. Yu: Distributed Query Processing Strategies in Mermaid, A Frontend to Data Management Systems. ICDE 1984: 211-218
  82. Stefano Ceri, Giuseppe Pelagatti: Correctness of Query Execution Strategies in Distributed Databases. ACM Trans. Database Syst. 8(4): 577-607(1983)
  83. Clement T. Yu, M. K. Siu, K. Lam, C. H. Chen: File Allocation in Distributed Databases with Interaction between Files. VLDB 1983: 248-259
  84. Umeshwar Dayal: Processing Queries Over Generalization Hierarchies in a Multidatabase System. VLDB 1983: 342-353
  85. Arvola Chan, Umeshwar Dayal, Stephen Fox, Daniel R. Ries: Supporting a Semantic Data Model in a Distributed Database System. VLDB 1983: 354-363
  86. Clement T. Yu, C. C. Chang: On the Design of a Query Processing Strategy in a Distributed Database Environment. SIGMOD Conference 1983: 30-39
  87. Stavros Christodoulakis: Estimating Block Transfers and Join Sizes. SIGMOD Conference 1983: 40-54
  88. Arvola Chan, Umeshwar Dayal, Stephen Fox, Nathan Goodman, Daniel R. Ries, Dale Skeen: Overview of an Ada Compatible Distributed Database Manager. SIGMOD Conference 1983: 228-237
  89. Umeshwar Dayal: Processing Queries with Quantifiers: A Horticultural Approach. PODS 1983: 125-136
  90. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
  91. Nathan Goodman, Oded Shmueli: Tree Queries: A Simple Class of Relational Queries. ACM Trans. Database Syst. 7(4): 653-677(1982)
  92. Jo-Mei Chang: A Heuristic Approach to Distributed Query Processing. VLDB 1982: 54-61
  93. Yahiko Kambayashi, Masatoshi Yoshikawa, Shuzo Yajima: Query Processing for Distributed Databases Using Generalized Semi-Joins. SIGMOD Conference 1982: 151-160
  94. Matthias Jarke, Joachim W. Schmidt: Query Processing Strategies in the PASCAL/R Relational Database Management System. SIGMOD Conference 1982: 256-264
  95. Umeshwar Dayal, Nathan Goodman: Query Optimization for CODASYL Database Systems. SIGMOD Conference 1982: 138-150
  96. Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981)
  97. James B. Rothnie Jr., Philip A. Bernstein, Stephen Fox, Nathan Goodman, Michael Hammer, T. A. Landers, Christopher L. Reeve, David W. Shipman, Eugene Wong: Introduction to a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 1-17(1980)
  98. Michael Hammer, David W. Shipman: Reliability Mechanisms for SDD-1: A System for Distributed Databases. ACM Trans. Database Syst. 5(4): 431-466(1980)
  99. Philip A. Bernstein, David W. Shipman, James B. Rothnie Jr.: Concurrency Control in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 18-51(1980)
  100. Robert S. Epstein, Michael Stonebraker: Analysis of Distributed Data Base Processing Strategies. VLDB 1980: 92-101
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:38:47 2008