Eugene Wong
Abstract
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.
- 1 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.Google Scholar
- 2 ASTRAHAN, M.M., AND CHAMBEaLIN, D.D. Implementation of a structured English query language. Comm. ACM 18, 10 (Oct. 1975), 580-588. Google ScholarDigital Library
- 3 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.Google Scholar
- 4 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.Google Scholar
- 5 McDONALD, N., AND STONEBRAKER, M. Cupid--the friendly query language. ERL Mem. No. M487, Electronics Research Lab., U. of California, Berkeley, Calif., Oct. 1974.Google Scholar
- 6 PALERMO, E.P. A data base search problem. Proc. 4th Int. Symp. on Computers and Information Science, Miami Beach, Fla., Dec. 1972.Google Scholar
- 7 PECH~R~R, R.M. Efficient evaluation of expressions in a relational algebra. Proc. ACM Pacific 75 Conf., April 1975, pp. 44--49.Google Scholar
- 8 RITCHIE, D., AND THOMPSON, K. The UNIX time sharing system. Comm. ACM 17, 7 (July 1974), 365-375. Google ScholarDigital Library
- 9 RITCHIE, D.M. C Reference Manual. UNIX Programmer's Manual, Bell Telephone Labs, Murray Hill, N.J., July 1974.Google Scholar
- 10 ROTHNIE, J.B. An approach to implementing a relational data base management system. Proc. 1974 ACM-SIGFIDET Workshop on Data Description, Access and Control, Ann Arbor, Mich., May 1974. Google ScholarDigital Library
- 11 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.Google Scholar
- 12 SMITH, J.M., AND CHANG, P.Y.T. Optimizing the performance of a relational algebra database interface. Comm. ACM 18, 10 (Oct. 1975), 568-579. Google ScholarDigital Library
- 13 STON~BRAKER, M., WONG, E., KREPS, P., AND HELD, G. The design and implementation of INGRES. ACM Trans. on Database Systems I, 3 (Sept. 1976), 189-222 (this issue). Google ScholarDigital Library
- 14 TODD, S. PRTV: An efficient implementation for large relational data bases. Proc. Int. Conf. on Very Large Data Bases, Framingham, Mass., Sept. 1975, pp. 554-556. (Available from ACM, New York).Google ScholarDigital Library
- 15 Tsic~mTZiS, D. A network framework for relational implementation. Rep. CSRG-51, Computer Systems Research Group, U. of Toronto, Toronto, Ont., Canada, Feb. 1975.Google Scholar
Index Terms
- Decomposition—a strategy for query processing
Recommendations
Combining Joint and Semi-Join Operations for Distributed Query Processing
The application of a combination of join and semi-join operations to minimize the amount of data transmission required for distributed query processing is discussed. Specifically, two important concepts that occur with the use of join operations as ...
Interleaving a Join Sequence with Semijoins in Distributed Query Processing
The problem of combining join and semijoin reducers for distributed query processing is studied. An approach based on interleaving a join sequence with beneficial semijoins is proposed. A join sequence is mapped into a join sequence tree first. The join ...
Approximate Query Processing with Error Guarantees
Big-Data-Analytics in Astronomy, Science, and EngineeringAbstractIn recent years, with the increase of data and the sophistication of analysis requirements, query processing in databases has become more important. Recently, approximate query processing (AQP) was proposed for efficiently executing database ...
Comments