Decomposition—a strategy for query processing

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.

REFERENCES

• 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.
• 2: M. M. Astrahan , D. D. Chamberlin, Implementation of a structured English query language, Communications of the ACM, v.18 n.10, p.580-588, Oct. 1975 [doi>10.1145/361020.361215]
• 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.
• 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.
• 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.
• 6: PALERMO, E.P. A data base search problem. Proc. 4th Int. Symp. on Computers and Information Science, Miami Beach, Fla., Dec. 1972.
• 7: PECH~R~R, R.M. Efficient evaluation of expressions in a relational algebra. Proc. ACM Pacific 75 Conf., April 1975, pp. 44--49.
• 8: Dennis M. Ritchie , Ken Thompson, The UNIX time-sharing system, Communications of the ACM, v.17 n.7, p.365-375, July 1974 [doi>10.1145/361011.361061]
• 9: RITCHIE, D.M. C Reference Manual. UNIX Programmer's Manual, Bell Telephone Labs, Murray Hill, N.J., July 1974.
• 10: James B. Rothnie, Jr., An approach to implementing a relational data management system, Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, p.277-294, May 01-03, 1974, Ann Arbor, Michigan [doi>10.1145/800296.811517]
• 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.
• 12: John Miles Smith , Philip Yen-Tang Chang, Optimizing the performance of a relational algebra database interface, Communications of the ACM, v.18 n.10, p.568-579, Oct. 1975 [doi>10.1145/361020.361025]
• 13: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
• 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).
• 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.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Design, Languages

Keywords:
connected query, decomposition, detachment, irreducible query, joining (overlapping) variable, query processing, relational database, tuple substitution, variable selection