Query processing in a system for distributed databases (SDD-1)

ACM Transactions on Database Systems - Tập 6 Số 4 - Trang 602-625 - 1981
Philip A. Bernstein1, Nathan Goodman1, Eugene Wong2, Christopher L. Reeve3, James B. Rothnie4
1Harvard University, Cambridge, Ma.#TAB#
2University of California at Berkeley, Berkeley
3Massachusetts Institute of Technology, Cambridge
4Computer Corp. of America, Cambridge, MA

Tóm tắt

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 semijoin . 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.

Từ khóa


Tài liệu tham khảo

10.1145/320064.320065

10.1145/322234.322238

10.1137/0210059

BERNSTEIN P.A. AN}) GOODMAN N. The power of inequality semi-joins. To appear in Inf. Syst. BERNSTEIN P.A. AN}) GOODMAN N. The power of inequality semi-joins. To appear in Inf. Syst.

10.1145/320128.320133

10.1145/320128.320131

10.1145/582250.582277

DATE , C.J. An Introduction to Database Systems . Addison-Wesley , Reading, Mass ., 1977 . DATE, C.J. An Introduction to Database Systems. Addison-Wesley, Reading, Mass., 1977.

10.1145/509252.509292

10.1145/319758.319775

10.1145/582318.582344

10.1145/320610.320621

HELD , G.D. , STONEBRAKER , M. , AND WONG , W. INGRES--A relational database management system . In Proc. AFIPS 1975 NCC , vol. 44 , AFIPS Press, Arlington, Va. , pp. 409 - 416 . HELD, G.D., STONEBRAKER, M., AND WONG, W. INGRES--A relational database management system. In Proc. AFIPS 1975 NCC, vol. 44, AFIPS Press, Arlington, Va., pp. 409-416.

HEVNER , A.R. , AND YAO , S.B. Query processing in distributed database systems. IEEE Trans. Softw. Eng. SE . 5 , 3 ( May 1979 ), 177-187. HEVNER, A.R., AND YAO, S.B. Query processing in distributed database systems. IEEE Trans. Softw. Eng. SE.5, 3 (May 1979), 177-187.

10.1137/0114108

KERSCHBERG , L. , TING , P.D. , AND YAO , S.B. Query optimization in star computer networks. Unpublished Rep., Bell Laboratories, Holmdel, N.J. , 1980 . KERSCHBERG, L., TING, P.D., AND YAO, S.B. Query optimization in star computer networks. Unpublished Rep., Bell Laboratories, Holmdel, N.J., 1980.

MARILL , T. , AND STERN , D.H. The datacomputer : A network data utility . In Proc. AFIPS 1975 NCC , vol. 44 , AFIPS Press, Arlington, Va. MARILL, T., AND STERN, D.H. The datacomputer: A network data utility. In Proc. AFIPS 1975 NCC, vol. 44, AFIPS Press, Arlington, Va.

10.1145/320544.320553

10.1145/320128.320129

ROTHNIE , J.B. , AND GOODMAN , N. An overview of the preliminary design of SDD-1 . In Proc. Berkeley Workshop Distributed Data Management and Computer Newtorks , May 1977 , pp. 39 - 57 . ROTHNIE, J.B., AND GOODMAN, N. An overview of the preliminary design of SDD-1. In Proc. Berkeley Workshop Distributed Data Management and Computer Newtorks, May 1977, pp. 39-57.

Ro ~I tN Iz, J .B., A~D GOOD , N, N . A survey of research and develoment in distributed database systems . In Proc. 3rd Int. Conf. Very Large Databases , Oct. 1977 , pp. 48 - 61 . Ro~ItNIz, J.B., A~D GOOD,N, N. A survey of research and develoment in distributed database systems. In Proc. 3rd Int. Conf. Very Large Databases, Oct. 1977, pp. 48-61.

ROTHNIE , J.B. , GOODMAN , N. , AND MARILL , T. Database architecture in a network environment . In Protocols and Techniques for Data Communication Networks , F.F. Kuo, Ed. Prentice-Hall, Englewood Cliffs , N.J. , 1980 . ROTHNIE, J.B., GOODMAN, N., AND MARILL, T. Database architecture in a network environment. In Protocols and Techniques for Data Communication Networks, F.F. Kuo, Ed. Prentice-Hall, Englewood Cliffs, N.J., 1980.

SELINGER , P.G. , AND ADIBA , M. Access path selection in distributed database management systems . In Proc. Int. Conf. Databases , Univ. Aberdeen, Aberdeen, Scotland , July 1980 . SELINGER, P.G., AND ADIBA, M. Access path selection in distributed database management systems. In Proc. Int. Conf. Databases, Univ. Aberdeen, Aberdeen, Scotland, July 1980.

10.1145/582095.582099

10.1145/320241.320246

WoNt, E. Retrieving dispersed data from SDD-1 . In Proc. Berkeley Workshop Distributed Data Management and Computer Networks , May 1977 , pp. 217 - 235 . WoNt, E. Retrieving dispersed data from SDD-1. In Proc. Berkeley Workshop Distributed Data Management and Computer Networks, May 1977, pp. 217-235.

10.1145/320473.320479

10.1145/359461.359475

Yu, C.T., AND OZSOYOOLU , M.Z. An algorithm for tree-query membership of a distributed query . In Proc. Compsac79 , IEEE Computer Society , Nov. 1979 , pp. 306 - 312 . Yu, C.T., AND OZSOYOOLU, M.Z. An algorithm for tree-query membership of a distributed query. In Proc. Compsac79, IEEE Computer Society, Nov. 1979, pp. 306-312.

Thông tin
Thông tin xuất bản

ACM Transactions on Database Systems

Tập 6 Số 4

602-625

Thông tin tác giả