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

@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}
}

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

• 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/An3-1 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/aDVD2 or /dvd

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]

...