Decomposition—a strategy for query processing

ACM Transactions on Database Systems - Tập 1 Số 3 - Trang 223-241 - 1976
Eugene Wong1, Karel Youssefi1
1Univ. of California, Berkeley, Berkeley

Tóm tắt

Strategy for processing multivariable queries in the database management system INGRES is considered. The general procedure is to decompose the query into a sequence of one-variable queries by alternating between (a) reduction: breaking off components of the query which are joined to it by a single variable, and (b) tuple substitution: substituting for one of the variables a tuple at a time. Algorithms for reduction and for choosing the variable to be substituted are given. In most cases the latter decision depends on estimation of costs; heuristic procedures for making such estimates are outlined.

Từ khóa


Tài liệu tham khảo

ALLMAN , E. , AND STONE }BR AKER , M. Embedding a relational data sub-language in a general purpose programming language. ERL Mem. No. M564 , Electronics l~esearch Lab., U. of California , Berkeley, Calif ., Oct. 1974 . ALLMAN, E., AND STONE}BRAKER, M. Embedding a relational data sub-language in a general purpose programming language. ERL Mem. No. M564, Electronics l~esearch Lab., U. of California, Berkeley, Calif., Oct. 1974.

10.1145/361020.361215

CODD , E.F. Seven steps to rendezvous with the casual user . Proc. IFIP TC-2 Working Conf. on Data Base Management Systems , Cargese, Corsica , April 1974 . CODD, E.F. Seven steps to rendezvous with the casual user. Proc. IFIP TC-2 Working Conf. on Data Base Management Systems, Cargese, Corsica, April 1974.

HELD , G.D. , STONEBRAKER , M. , AND WONG , E. INGRES--a relational data base management system . Proc. AFIPS 1975 NCC , Vol. 44 , AFIPS Press, Montvale, N.J. , pp. 409 - 416 . HELD, G.D., STONEBRAKER, M., AND WONG, E. INGRES--a relational data base management system. Proc. AFIPS 1975 NCC, Vol. 44, AFIPS Press, Montvale, N.J., pp. 409-416.

Mc DONALD , N. , AND STONEBRAKER , M. Cupid--the friendly query language. ERL Mem. No. M487 , Electronics Research Lab., U. of California , Berkeley, Calif ., Oct. 1974 . McDONALD, N., AND STONEBRAKER, M. Cupid--the friendly query language. ERL Mem. No. M487, Electronics Research Lab., U. of California, Berkeley, Calif., Oct. 1974.

PALERMO , E.P. A data base search problem . Proc. 4th Int. Symp. on Computers and Information Science, Miami Beach, Fla. , Dec. 1972 . PALERMO, E.P. A data base search problem. Proc. 4th Int. Symp. on Computers and Information Science, Miami Beach, Fla., Dec. 1972.

PECH~R~R , R.M. Efficient evaluation of expressions in a relational algebra . Proc. ACM Pacific 75 Conf. , April 1975 , pp. 44 -- 49 . PECH~R~R, R.M. Efficient evaluation of expressions in a relational algebra. Proc. ACM Pacific 75 Conf., April 1975, pp. 44--49.

10.1145/361011.361061

RITCHIE , D.M. C Reference Manual. UNIX Programmer's Manual , Bell Telephone Labs , Murray Hill , N.J. , July 1974 . RITCHIE, D.M. C Reference Manual. UNIX Programmer's Manual, Bell Telephone Labs, Murray Hill, N.J., July 1974.

10.1145/800296.811517

ROTHNIE , J.B. Evaluating inter-entry retrieval expressions in a relational data base management system . Proc. AFIPS 1975 NCC , Vol. 44 , AFIPS Press, Montvale, N.J. , pp. 417 - 423 . ROTHNIE, J.B. Evaluating inter-entry retrieval expressions in a relational data base management system. Proc. AFIPS 1975 NCC, Vol. 44, AFIPS Press, Montvale, N.J., pp. 417- 423.

10.1145/361020.361025

10.1145/320473.320476

10.1145/1282480.1282546

Tsic~m TZ i S, D . A network framework for relational implementation. Rep. CSRG-51 , Computer Systems Research Group , U. of Toronto, Toronto, Ont., Canada, Feb. 1975 . Tsic~mTZiS, D. A network framework for relational implementation. Rep. CSRG-51, Computer Systems Research Group, U. of Toronto, Toronto, Ont., Canada, Feb. 1975.