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

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

REFERENCES

• 1: E. Babb, Implementing a relational database by means of specialzed hardware, ACM Transactions on Database Systems (TODS), v.4 n.1, p.1-29, March 1979 [doi>10.1145/320064.320065]
• 2: Philip A. Bernstein , Dah-Ming W. Chiu, Using Semi-Joins to Solve Relational Queries, Journal of the ACM (JACM), v.28 n.1, p.25-40, Jan. 1981 [doi>10.1145/322234.322238]
• 3: BERNSTEIN, P.A., AND GOODMAN, N. The power of natural semijoins. SIAM J. Comput. 10, 4 (Nov. 1981).
• 4: BERNSTEIN, P.A., AN}) GOODMAN, N. The power of inequality semi-joins. To appear in Inf. Syst.
• 5: Philip A. Bernstein , David W. Shipman, The correctness of concurrency control mechanisms in a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.5 n.1, p.52-68, March 1980 [doi>10.1145/320128.320133]
• 6: Philip A. Bernstein , David W. Shipman , James B. Rothnie, Jr., Concurrency control in a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.5 n.1, p.18-51, March 1980 [doi>10.1145/320128.320131]
• 7: CHIU, D.M. Optimal query interpretation for distributed databases. Ph.D. Dissertation, Harvard Univ., Cambridge, Mass., Dec. 1979.
• 8: D. M. Chiu , Y. C. Ho, A methodology for interpreting tree queries into optimal semi-join expressions, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California [doi>10.1145/582250.582277]
• 9: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 10: Robert Epstein , Michael Stonebraker , Eugene Wong, Distributed query processing in a relational data base system, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509292]
• 11: GOODMAN, N., BERNSTEIN, P.A., WONG, W., REEVE, C. L., AND ROTHNIE, JR., J.B. Query processing in SDD-1. Tech. Rep. CCA-79-06, Computer Corp. of America, Cambridge, Mass., Oct. 1979.
• 12: Nathan Goodman , Oded Shmueli, Tree queries: a simple class of relational queries, ACM Transactions on Database Systems (TODS), v.7 n.4, p.653-677, Dec. 1982 [doi>10.1145/319758.319775]
• 13: Mohamed G. Gouda , Umeshwar Dayal, Optimal semijoin schedules for query processing in local distributed database systems, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582344]
• 14: Micael Hammer , David Shipman, Reliability mechanisms for SDD-1: a system for distributed databases, ACM Transactions on Database Systems (TODS), v.5 n.4, p.431-466, Dec. 1980 [doi>10.1145/320610.320621]
• 15: 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.
• 16: Alan Raymond Hevner, The optimization of query processing on distributed database systems, 1979
• 17: HEVNER, A.R., AND YAO, S.B. Query processing in distributed database systems. IEEE Trans. Softw. Eng. SE.5, 3 (May 1979), 177-187.
• 18: KARP, R.M., AND MILLER, R.E. Properties of a model for parallel computation: Determinary, termination, queueing. SIAM J. Appl. Math. 14 (Nov. 1966), 1390-1411.
• 19: KERSCHBERG, L., TING, P.D., AND YAO, S.B. Query optimization in star computer networks. Unpublished Rep., Bell Laboratories, Holmdel, N.J., 1980.
• 20: MARILL, T., AND STERN, D.H. The datacomputer: A network data utility. In Proc. AFIPS 1975 NCC, vol. 44, AFIPS Press, Arlington, Va.
• 21: E. A. Ozkarahan , S. A. Schuster , K. C. Sevcik, Performance evaluation of a relational associative processor, ACM Transactions on Database Systems (TODS), v.2 n.2, p.175-195, June 1977 [doi>10.1145/320544.320553]
• 22: ROTHNIE, J.B. Private communication. See also: A distributed database management system for command and control applications: Semiannual technical report 2. Tech. Rep. CCA-80-03, Computer Corp. of America, Cambridge, Mass., Jan. 1980.
• 23: J. B. Rothnie, Jr. , P. A. Bernstein , S. Fox , N. Goodman , M. Hammer , T. A. Landers , C. Reeve , D. W. Shipman , E. Wong, Introduction to a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.5 n.1, p.1-17, March 1980 [doi>10.1145/320128.320129]
• 24: 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.
• 25: 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.
• 26: 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.
• 27: 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.
• 28: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 29: Stanley Y. W. Su , Ahmed Emam, CASDAL: CASSM's DAta Language, ACM Transactions on Database Systems (TODS), v.3 n.1, p.57-91, March 1978 [doi>10.1145/320241.320246]
• 30: WoNt, E. Retrieving dispersed data from SDD-1. In Proc. Berkeley Workshop Distributed Data Management and Computer Networks, May 1977, pp. 217-235.
• 31: Eugene Wong , Karel Youssefi, Decomposition—a strategy for query processing, ACM Transactions on Database Systems (TODS), v.1 n.3, p.223-241, Sept. 1976 [doi>10.1145/320473.320479]
• 32: S. B. Yao, Approximating block accesses in database organizations, Communications of the ACM, v.20 n.4, p.260-261, April 1977 [doi>10.1145/359461.359475]
• 33: 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.
• 34: Yu, C.T., AND OZSOYOGLU, M.Z. On determining tree query membership of a distributed query. Tech. Rep. TR80-1, Dep. Computing Science, Univ. Alberta, Edmonton, Alta., Canada, Jan. 1980.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases; Distributed databases

General Terms:
Algorithms, Design

Keywords:
distributed databases, query optimization, query processing, relational databases, semijoins