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. 1 BABB, E. Implementing a relational database by means of specialized hardware. A CM Trans. Database Syst. 4, I (March 1979), 1-29.
2. 2 BEI~NSTEIN, P.A., AND Cmu, D.W. Using semijoins to solve relational queries. J. A CM. 28, 1 (Jan. 1981), 25-40.
3. 3 BERNSTEIN, P.A., AND GOODMAN, N. The power of natural semijoins. SIAM J. Comput. 10, 4 (Nov. 1981).
4. 4 BERNSTEIN, P.A., AN}) GOODMAN, N. The power of inequality semi-joins. To appear in Inf. Syst.
5. 5 BERNSTEIN, P.A., AND SHIPMAN, D.W. The correctness of concurrency control mechanisms in a system for distributed databases (SDD-1). ACM Trans. Database Syst. 5, 1 (March 1980), 52-68.
6. 6 BERNSTEIN, P.A., SHIPMAN, D.W., AND ROTHNIE, JR., J.B. Concurrency control in a system for distributed databases (SDD-1). ACM Trans. Database Syst. 5, 1 (March 1980), 18-51.
7. 7 CHIU, D.M. Optimal query interpretation for distributed databases. Ph.D. Dissertation, Harvard Univ., Cambridge, Mass., Dec. 1979.
8. 8 CHUI, D.M., AND HO, Y.C. A methodology for interpreting tree queries into optimal semi-join expressions. In Proc. ACM-SICMOD Conf., May 1980.
9. 9 DATE, C.J. An Introduction to Database Systems. Addison-Wesley, Reading, Mass., 1977.
10. 10 EPSTEIN, R., STONEBRAKER, M., AND WONG, E. Distributed query processing in a relational database system. In Proc. ACM-SIGMOD Conf., June 1978, pp. 169-180.
11. 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. 12 GOODMAN, N., AND SHMUELI, O. Tree queries: A simple class of relational queries. To appear in A CM Trans. Database Syst.
13. 13 GROUDA, M.G., AND DAYAL, U. Optimal semijoin schedules for query processing in local distributed database systems. In Proc. ACM-SIGMOD Conf., April 1981, pp. 164-175.
14. 14 HAMMER, M.M., AND SHIPMAN, D.W. Reliability mechanisms for SDD-I: A system for distributed databases. ACM Trans. Database Syst. 5, 4 (Dec. 1980), 431-466.
15. 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. 16 HEVNER, A.R. Optimization of query processing in distributed databases. Ph.D. Dissertation, Purdue Univ., Lafayette, Ind., Sept. 1979.
17. 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. 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. 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. 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. 21 OZKARAHAN, E.A., SCHUSTER, S.A., AND SEVCIK, K.C. Performance evaluation of a relational associative processor. ACM Trans Database Syst. 2, 2 (June 1977), 175-195.
22. 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. 23 ROTHNIE, JR., J.B., BERNS~EIN, P.A., Fox, S.A., GOODMAN, N., HAMMER, M.M., LANDERS, T.A., REEVE, C.L., SHIPMAN, D.W., AND WONG, E. A system for distributed databases (SDD-1). ACM Trans. Database Syst. 5, 1 (March 1980), 1-17.
24. 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. 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. 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. 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. 28 SELINGER, P.G., ASTRAHAN, M.M., CHAMBERHN, D.D., LORIE, R.A., AND PRICE, T.G. Access path selection in a relational database management system. In Proc. ACM-SIGMOD Conf., June 1979, pp. 23-34.
29. 29 Su, S.Y.W., AND EMAM, A. CASDAL: CASSM's data language. ACM Trans. Database Syst. 3, 1 (March 1978), 57-91.
30. 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. 31 WONG, E., AND YOUSSEFI, K. Decomposition--A strategy for query processing. ACM Trans. Database Syst. 1, 3 (Sept. 1976), 223-241.
32. 32 YAO, S.B. Approximating block accesses in database organizations. Commun. ACM 20, 4 (Apr. 1977), 260-261.
33. 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. 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

• Information systems

  • Data management systems

    • Database design and models

      • Relational database model

    • Database management system engines

      • Database query processing

      • Parallel and distributed DBMSs

    • Query languages

      • Relational database query languages

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory

      • Database query processing and optimization (theory)