On the design of a query processing strategy in a distributed database environment

ABSTRACT

An algorithm is given to process a given query in a fragmented distributed data base environment. Unlike previous algorithms, it has the following desired features.(1) It makes use of redundant relations to reduce communication cost;(2) a copy of each relation referenced by the query is selected so that the set of relations are contained in the minimum number of sites;(3) an efficient algorithm to process fragments is provided;(4) all relations that need not be sent to the assembly site to produce the answer are identified. Thus, unnecessary sending of these relations across sites and processing on these relations, which are common in earlier algorithms, are avoided;(5) useless semi-joins are discarded and "worse" semi-joins are replaced by better ones;(6) a process to estimate the cost and the benefit of a semi-join, based on dynamic execution of semi-joins is introduced. It is expected that the new process is more accurate than earlier estimation process.The algorithm is easy to implement and is operational.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Catriel Beeri , Ronald Fagin , David Maier , Alberto Mendelzon , Jeffrey Ullman , Mihalis Yannakakis, Properties of acyclic database schemes, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.355-362, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802489]
• 3: 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]
• 4: {BeGo} Bernstein P.A., and Goodman N. "The theory of semi-join", Technical Report, CCA, Nov. 1979.
• 5: {BlLu} Black, P.A. and Luk W.S. "A New Heuristic for Generating Semi-join Programs for Distributed Query Processing", IEEE COMPSAC, 1982.
• 6: Jo-Mei Chang, A Heuristic Approach to Distributed Query Processing, Proceedings of the 8th International Conference on Very Large Data Bases, p.54-61, September 08-10, 1982
• 7: {Chan2} Chang J.M. "Query Processing in a fragmented database environment" Bell Lab. Technical Report, 1982.
• 8: {Chiu} Chiu, D-M.W. "Optimal Query Interpretation for Distributed Databases", Ph.D. thesis, Harvard Uni. 1979.
• 9: 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]
• 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: C. J. Date, An Introduction to Database Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 12: {FaMU} Fagin, R., Mendelzon, A. and Ullman, J., "A simplified universal relation assumption and its properties", IBM technical report, 1980.
• 13: N. Goodman , O. Shmueli, The tree property is fundamental for query processing, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588119]
• 14: {Grah} Graham, M.H., "On the universal relstion", TR, Univ. of Toronto, sept. 1979.
• 15: {HeYa} Hevner, A. and Yao, S.B. "Query Processing in Distributed Database Systems", IEEE trans. on Software Engineering, Vol. SE-5, No. 3, (May 1979), pp. 177--187.
• 16: {Hevn} Hevner, A. "Query Optimization in distributed database system" Ph.D. thesis, Purdue University, 1979.
• 17: {KeYa} Kerschberg, L. and Yao, S.B. "Optimal Distributed Query Processing", Bell Telephone, Holmdel, 1980.
• 18: {Luk1} Luk, W.S. and Black, P.A. "On Cost Estimation in Processing a Query in a Distributed Database System", IEEE COMPSAC, 1981.
• 19: {Luk2} Luk, W.S. and Luk, L. "Optimizing Query Processing strategies in a distributed Database System", Simon Fraser Univ, Burnaby B.C., Canada.
• 20: {SDD1V1} Goodman, N., Bernstein, P.A., Wong, K., Reeve, C. and Rothnie, J.B., "Query Processing in a system for Distributed Databases", CCA Technical Report, 1979.
• 21: 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]
• 22: {WDHL} Williams, R., el.ta., "R*: An Overview of the Architecture", IBM Research, San Jose, California, USA.
• 23: {Wong} Wong, E., "Retrieving Dispersed Data from SDD-1: A system for distributed Databases", Berkeley Workshop on Distributed Data Management and Computer Networks, Berkeley, 1977.
• 24: 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]
• 25: {YuOz} Yu, C.T., Ozsoyoglu, M.Z. "An algorithm for tree-query membership of a distributed query". IEEE COMPSAC 1979, pp. 306--312.
• 26: {YuLO} Yu, C.T., Lam, K. and Ozsoyoglu, M.Z. "Distributed Query Optimization for tree Queries", Dept. of Information Engineering, U. of Illinois at Chicago Circle, I1, 1979.
• 27: {YLCC} Yu, C.T., Lam, K., Chang, C.C., Chang, S.k. "A Promising Approach to Distributed Query Processing", Berkeley Conference on Distributed Data Base, Feb., 1982, pp. 363--390.
• 28: {YuCC} Yu, C.T., Chang, C.C. and Chang, Y.C. "Two Surprising Results in Processing Simple Queries in distributed Databases", IEEE COMPSAC, Nov., 1982.