A state transition model for distributed query processing

ABSTRACT

A state transition model for the optimization of query processing in a distributed database system is presented. The problem is parameterized by means of a state describing the amount of processing that has been performed at each site where the database is located. A state transition occurs each time a new join or semijoin is executed. Dynamic programming is used to compute recursively the costs of the states and the globally optimal solution, taking into account communication and local processing costs. The state transition model is general enough to account for the possibility of parallel processing among the various sites, as well as for redundancy in the database. The model also permits significant reductions of the necessary computations by taking advantage of simple additivity and site-uniformity properties of a cost model, and of clever strategies that improve on the basic dynamic programming algorithm.

REFERENCES

• 1: APERS, P. G. M., HEVNER, A. R., AND YAO, S.B. Optimization algorithms for distributed queries. IEEE Trans. So/tw. Eng. SE-9, 1 (Jan. 1983), 57-68.
• 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. Power of natural semijoin. SIAM. J. Comput. 10, 4 (Nov. 1981), 751-771.
• 4: BERNSTEIN, P. A., AND GOODMAN, N. The power of inequality semijoins. Inf. Syst. 6, 4 (1981), 255-265.
• 5: 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]
• 6: BLASGEN, M. W., AND ESWARAN, K.P. On the evaluation of queries in a relational database system. Res. Rep. RJ 1745, IBM Research Laboratory, San Jose, Calif., Apr. 1976.
• 7: CAREY, M. J., AND Lu, H. Some experimental results on distributed join algorithms in a local network. Computer Science Rep. 587, Univ. of Wisconsin. Also in the Proceedings of the 11th Conference on Very Large Data Bases (Stockholm, 1985).
• 8: Stefano Ceri , Giuseppe Pelagatti, Distributed databases principles and systems, McGraw-Hill, Inc., New York, NY, 1984
• 9: Arbee L. P. Chen , Victor O. K. Li, Optimizing Star Queries in a Distributed Database System, Proceedings of the 10th International Conference on Very Large Data Bases, p.429-438, August 27-31, 1984
• 10: Dah-Ming Chiu , Philip A. Bernstein , Yu-Chi Ho, Optimizing chain queries in a distributed database system., SIAM Journal on Computing, v.13 n.1, p.116-134, Feb. 1984 [doi>10.1137/0213009]
• 11: 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]
• 12: CHu, W. W., AND HURLEY, P. Optimal query processing for distributed database systems. IEEE Trans. Comput. C-31, 9 (Sept. 1982), 835-850.
• 13: 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]
• 14: 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]
• 15: HEVNER, A. R., aND YAO, S.B. Query processing in distributed database systems. IEEE Trans. Softw. Eng. SE-5, 3 (May 1979), 177-187.
• 16: IOANNtDIS, Y. A time bound on the materialization of some recursively defined views. In Proceedings of the 11th Conference on Very Large Data Bases (Stockholm, 1985).
• 17: LAFORTUNE, S. Distributed information and distributed control: Cases from stochastic systems and database mangement. Ph.D. dissertation, Univ. of California, Berkeley, May 1986.
• 18: LOHMAN, G. M., MOHAN, C., HAAS, L. M., LINDSAY, B. G., SELINGER, P. G., WILMS, P. F., AND DANIELS, D. Query processing in R*. Res. Rep. RJ 4272, IBM Research Laboratory, San Jose, Calif., Apr. I984.
• 19: Elaine Rich, Artificial intelligence, McGraw-Hill, Inc., New York, NY, 1983
• 20: SEL{NGER, P. G., AND ADIBA, M. Access path selection in distributed database management systems. Res. Rep. RJ 2883, IBM Research Laboratory, San Jose, Calif., Aug. 1980.
• 21: SELINGER, P. G., ASTRAHAN, M. M., CHAMBERLIN, D. D., LORIE, R. A., AND PRICE, T.G. Access path selection in a relational database management system. Res. Rep. RJ 2429, IBM Research Laboratory, San Jose, Calif., Jan. 1979.
• 22: Patrick Valduriez , Georges Gardarin, Join and Semijoin Algorithms for a Multiprocessor Database Machine, ACM Transactions on Database Systems (TODS), v.9 n.1, p.133-161, March 1984 [doi>10.1145/348.318590]
• 23: WoNo, E. Retrieving dispersed data from SDD-I: A system for distributed databases. In Proceedings of the 2nd Berkeley Workshop on Distributed Data Management and Computer Networks (Lawrence Berkeley Laboratory, May 25-27, 1977), 217-235.
• 24: WON6, E. Dynamic rematerialization: Processing distributed queries using redundant data. IEEE Trans. Softw. Eng. SE-9, 3 (May 1983), 228-232.
• 25: 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]
• 26: Yu, C. T., A~D OZSOYOGLU, M.Z. On determining tree query membership of a distributed query. Can. J. Oper. Res. Inf. Process. 22, 3 (Aug. 1984), 261-268.
• 27: Clement T. Yu , Z. Meral Ozsoyoglu , K. Lam, Optimization of distributed tree queries, Journal of Computer and System Sciences, v.29 n.3, p.409-445, Dec. 1984 [doi>10.1016/0022-0000(84)90007-2]

INDEX TERMS

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

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing; Distributed databases

General Terms:
Algorithms, Design, Performance, Theory