Stochastic query optimization in distributed databases

ABSTRACT

Many algorithms have been devised for minimizing the costs associated with obtaining the answer to a single, isolated query in a distributed database system. However, if more than one query may be processed by the system at the same time and if the arrival times of the queries are unknown, the determination of optimal query-processing strategies becomes a stochastic optimization problem. In order to cope with such problems, a theoretical state-transition model is presented that treats the system as one operating under a stochastic load. Query-processing strategies may then be distributed over the processors of a network as probability distributions, in a manner which accommodates many queries over time. It is then shown that the model leads to the determination of optimal query-processing strategies as the solution of mathematical programming problems, and analytical results for several examples are presented. Furthermore, a divide-and-conquer approach is introduced for decomposing stochastic query optimization problems into distinct subproblems for processing queries sequentially and in parallel.

REFERENCES

• 1: Rakesh Agrawal , Michael J. Carey , Miron Livny, Concurrency control performance modeling: alternatives and implications, ACM Transactions on Database Systems (TODS), v.12 n.4, p.609-654, Dec. 1987 [doi>10.1145/32204.32220]
• 2: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 3: ARBm, M.A. Theories of Abstract Automata. Prentice-Hall, Englewood Cliffs, N.J., 1969. Ch. 9, p. 324.
• 4: 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]
• 5: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 6: BHARATH-KUMAR, K. Discrete-time queueing systems and networks. IEEE Trans. COM-28, 2 (Feb. 1980), 260-263.
• 7: Daniel Brand , Pitro Zafiropulo, On Communicating Finite-State Machines, Journal of the ACM (JACM), v.30 n.2, p.323-342, April 1983 [doi>10.1145/322374.322380]
• 8: Stefano Ceri , Giuseppe Pelagatti, Distributed databases principles and systems, McGraw-Hill, Inc., New York, NY, 1984
• 9: CHEN, P. P., AND AKOKA, J. Optimal design of distributed information systems. IEEE Trans. COM-29, 12 (1980), 1068-1080.
• 10: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 11: COFFMAN, E. G., JR. (ED.). Computer and Job-Shop Scheduling Theory. Wiley, New York, 1976.
• 12: COFFMAN, E. G., GELENBE, E., AND PLATEAU, B. Optimization of the number of copies in a distributed database. IEEE Trans. SE-7, 1 (Jan. 1981), 78 84.
• 13: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 14: DREMCK, P. E., AND DRENICK a.F. A design theory for multi-processing computing systems. Large ~qcale Syst. 12 (1907), 155 172.
• 15: Philip E. Drenick, Stochastic query optimization in distributed databases, Polytechnic University, Brooklyn, NY, 1988
• 16: DRENICK, R.F. A Mathematical Organzzatton Theory. Elsevier, New York, 1986.
• 17: GELENBE, E., AND MITRANI, I. Analysts and Synthesis of Computer Systems. Academic Press, New York, 1980.
• 18: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 19: HART~XTIS, J., AND STEARNS, R. E. Algebraic Structure Theory of Sequenttal Machines. Prentice-Hall, Englewood Cliffs, N J, 1966.
• 20: HEVNEU, A. R., AND YAO, S.B. Query processing on a distributed database. In Proceedtngs of the 3rd Workshop on Distributed Databases and Computer Networks. 1978.
• 21: Frederick S. Hillier , Gerald J. Lieberman, Introduction to operations research, 4th ed., Holden-Day, Inc., San Francisco, CA, 1986
• 22: JAEOBY, S. L. S., KOWALIK, J. S., AND PIzzo, J T. Iteratlve Methods for Nonlinear Optimtzatlon Problems. Prentice-Hall, Englewood Cliffs, N.J., 1972
• 23: KLE~NR~C~<, L. Queueing Systems, Voh I Wfiey, New York, 1975.
• 24: KOBAYASHt, H. Discrete-time queueing systems. In Probabtlzty Theoh~ arTd Computer Science, G Louchard and G. Latouche, Eds. Academic Press, New York, 1983~ pp. 58-85.
• 25: KOItAVI, Z. Swttchlng and Ftntte Automata Theory McGraw-Hill, New York, 1970, p. 386
• 26: KOZLOV, A. The Karmarkar algorithm' Is ~t for real?. SIAM Newsl. 18, 6 (Nov. 1985), 1.
• 27: Stéphane Lafortune , Eugene Wong, A state transition model for distributed query processing, ACM Transactions on Database Systems (TODS), v.11 n.3, p.294-322, Sept. 1986 [doi>10.1145/6314.6460]
• 28: L^RSON, H. J. Introductzon to Probabzlttv Theory and Statzsttcal Inference. Wiley, New York, 1969
• 29: L~ND~EY, D. V The theory of queues with a single server. Proc. Cambrtdge Phtl. Soc. 48 (1952), 277 289.
• 30: Michael J. Carey , Hongjun Lu, Load balancing in a locally distributed DB system, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.108-119, May 28-30, 1986, Washington, D.C., United States
• 31: L~NBERGER~ D G. Introductzon to Ltnear and Nonlinear Programming. Addison-Wesley, Waltham, Mass., 1973, p. 318.
• 32: Lothar F. Mackert , Guy M. Lohman, R* Optimizer Validation and Performance Evaluation for Distributed Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.149-159, August 25-28, 1986
• 33: T H Merrett, Relational Information Systems, Reston Publishing Co., Reston, VA, 1984
• 34: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 35: SEN, P. Adaptive channels and human decision-making IEEE Trans. SMC-14, 5 (1984), 120-131
• 36: Ushio Sumita , Olivia R. Liu Sheng, Analysis of query processing in distributed database systems with fully replicated files: hierarchical approach, Performance Evaluation, v.8 n.3, p.223-238, June 1988 [doi>10.1016/0166-5316(88)90005-3]
• 37: Y. C. Tay, Locking performance in centralized databases, Academic Press Professional, Inc., San Diego, CA, 1988
• 38: WAGNER, H.M. On the optnnality of pure strategies. Manage. Sci. 6, 3 (Apr 1960).
• 39: Allan D. Waren , Ming S. Hung , Leon S. Lasdon, The status of nonlinear programming software: an update, Operations Research, v.35 n.4, p.489-503, July/August 1987 [doi>10.1287/opre.35.4.489]
• 40: WONG, E. Dynamic rematenalization: Processing distributed queries using redundant data. IEEE Trans. SE-9, 3 (May 1983), 228 232.
• 41: 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]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

Additional 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: Distributed databases; Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

General Terms:
Algorithms, Performance, Theory

Keywords:
distributed query processing, state-transition model, stochastic query optimization