Set query optimization in distributed database systems

ABSTRACT

This paper addresses the problem of optimizing queries that involve set operations (set queries) in a distributed relational database system. A particular emphasis is put on the optimization of such queries in horizontally partitioned database systems. A mathematical programming model of the set query problem is developed and its NP-completeness is proved. Solution procedures are proposed and computational results presented. One of the main results of the computational experiments is that, for many queries, the solution procedures are not sensitive to errors in estimating the size of results of set operations.

REFERENCES

• 1: APERS, P. M.G. Distributed query processing=. Minimum response time schedules for relations. IR 53, Vrije Univ., Amsterdam, Nov. 1979.
• 2: APERS, P. M. G., HEVNER, A. R., AND YAO, S. B. Optimization algorithms for distributed queries. IEEE Trans. Softw. Eng. SE-9, l (Jan. 1983), 57-68.
• 3: Philip A. Bernstein , Nathan Goodman , Eugene Wong , Christopher L. Reeve , James B. Rothnie, Jr., Query processing in a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.6 n.4, p.602-625, Dec. 1981 [doi>10.1145/319628.319650]
• 4: CORNUEJOLS, G., FISHER, M. L., AND NEMHAUSER, G.L. Location of bank accounts to optimize float. Manage. Sci. 23, 8 (Apr. 1977), 789-810.
• 5: DANIELS, D. Query compilation in a distributed database system. IBM Res. Rep. RJ3423, Mar. 1982.
• 6: DANIELS, D., SELINGER, P., HAAS, L., LINDSAY, B., MOHAN, C., WALKER, A., AND WILMS, P. An introduction to distributed query compilation in R*. IBM Res. Rep. RJ3497, June 1982.
• 7: EPSTEIN, R. S., STONEBRAKER, M., AND WONG, E. Distributed query processing in a relational database system. In Proceedings ACM-SIGMOD (May 1979), 169-180.
• 8: EPSTEIN, R. S., AND STONEBRAKER~ M. Analysis of query processing strategies for distributed database systems. In Proceedings of the 6th International Conference on Very Large Data Bases (1980).
• 9: ERLENKOTTER, D. A dual based procedure for uncapacitated facility location. Oper. Res. 26, 1 (1978), 992-1009.
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: GAVISH, B. Topological design of centralized computer networks--Formulations and algorithms. Networks 12 (1982), 355-377.
• 12: GAVlSH, B., AND SE(}EV, A. Set query optimization in horizontally partitioned distributed database systems. Working Paper QM 8304, Graduate School of Management, Univ. of Rochester, Rochester, N.Y., 1983.
• 13: HELD, G. D., STONEnRAKER, M., AND WONG, E. INGRES--a relational DBMS. In Proceedings of AFIPS 1975 National Computer Conference (Arlington, Va., 1975), 409-416.
• 14: HEVNER, A. R., AND YAO, S.B. Query processing in distributed database systems. IEEE Trans. Softw, Eng. SE-5, 3 (May 1979), 177-187.
• 15: Ellis Horowitz , Sartaj Sahni, Fundamentals of Computer Alori, W. H. Freeman & Co., New York, NY, 1978
• 16: PAIK, I. S., AND DELOBEL, C. A strategy for optimizing the distributed query processing. In Proceedings of the 1st International Conference on Distributed Computing Systems (Huntsville, Ala., Oct. 1979).
• 17: PEEBLES, R. W., AND MANNING, E.D. A computer architecture for large (distributed) databases. In Proceedings o{ the Con{erence on Very Large Data Bases (Framingham, Mass., Sept. 1975).
• 18: PELA6ATTI, G., AND SCHREInER, F.A. A model of an access strategy in a distributed database system. In Proceedings of the IFIP-TC2, Database Architecture (Venice, 1979).
• 19: ROTHNIE, J. B., AND GOODMAN, N. A survey of R&D in distributed database management. In Proceedings of the International Con{erence on Very Large Data Bases (Tokyo, Oct. 1977).
• 20: Arie Segev, Optimization of join operations in horizontally partitioned database systems, ACM Transactions on Database Systems (TODS), v.11 n.1, p.48-80, March 1986 [doi>10.1145/5236.5241]
• 21: SELINGER, P. G., AND ADIBA, M.E. Access path selection in distributed data base management systems. In Proceedings of the International Conference on Databases (July 1980), 204-215.
• 22: STONHBR^KER, M., AND NEUHOLD, E. A distributed database version of INGRES. In Proceedings of the 3rd Berkeley Workshop on Distributed Data Management and Computer Networks (May 1977).
• 23: WILLIAMS, R., ET AL. R*. An overview of the architecture. IBM Res. Rep. RJ3325, Dec. 198i.
• 24: WONG, E. Retrieving dispersed data from SDD-I: A system for distributed databases. In Proceedings of the 3rd Berkeley Workshop on Distributed Data Management and Computer Networks (May 1977), 217-235.
• 25: C. T. Yu , C. C. Chang, On the design of a query processing strategy in a distributed database environment, Proceedings of the 1983 ACM SIGMOD international conference on Management of data, May 23-26, 1983, San Jose, California
• 26: C. T. Yu , C. C. Chang, Distributed query processing, ACM Computing Surveys (CSUR), v.16 n.4, p.399-433, Dec. 1984 [doi>10.1145/3872.3874]
• 27: ZLOOF, M.M. Query-By-Example. IBM Syst. J. 4 (1977), 324-343.

INDEX TERMS

Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Languages, Theory