Outerjoin optimization in multidatabase systems

ABSTRACT

Outerjoin is used in distributed relational multidatabase systems for integrating local schemas to a global schema. Queries against the global schema need to be modified, optimized, and decomposed into subqueries at local sites for processing. Since outerjoin combines local relations in different databases to form a global relation, it is expensive to process. In this paper, based on the structure of the query and the definition of the schemas, queries with outerjoin, join, select and project operations are optimized. Conditions where outerjoin can be avoided or be transformed into a one-side outerjoin are identified. By considering these conditions the response time for query processing can be reduced.

REFERENCES

• 1: Apers, P., A. Hevner, S.B. Yao. "Optimization algorithm for distributed queries," IEEE Transactions on Software Engineering, January 1983.
• 2: Jay Banerjee , Won Kim , Kyung-Chang Kim, Queries in Object-Oriented Databases, Proceedings of the Fourth International Conference on Data Engineering, p.31-38, February 01-05, 1988
• 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: 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]
• 5: Yuri Breitbart , Peter L. Olson , Glenn R. Thompson, Database Integration in a Distributed Heterogeneous Database System, Proceedings of the Second International Conference on Data Engineering, p.301-310, February 05-07, 1986
• 6: Stefano Ceri , Giuseppe Pelagatti, Distributed databases principles and systems, McGraw-Hill, Inc., New York, NY, 1984
• 7: Arbee L. P. Chen, A localized approach to distributed query processing, Proceedings of the international conference on extending database technology on Advances in database technology, p.188-202, March 1990, Venice, Italy
• 8: Chen, A.L.P., D. Brill, M. Templeton and C. Yu, "Distributed query processing in a multiple database system," IEEE Journal on Selected Areas in Communications, special issue on Databases in Communications Systems, Apr. 1989.
• 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: Chen, A.L.P. and V.O.K. Li, "Improvement algorithms for semijoin query processing programs in distributed database systems," IEEE Transactions on Computers, November 1984.
• 11: Arbee L. P. Chen , Victor O. K. Li, An optimal algorithm for processing distributed star queries, IEEE Transactions on Software Engineering, v.11 n.10, p.1097-1107, Oct. 1985 [doi>10.1109/TSE.1985.231857]
• 12: 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]
• 13: E. F. Codd, Extending the database relational model to capture more meaning, ACM Transactions on Database Systems (TODS), v.4 n.4, p.397-434, Dec. 1979 [doi>10.1145/320107.320109]
• 14: Bogdan D. Czejdo , Marek Rusinkiewicz , David W. Embley, An Approach to Schema Integration and Query Formulation in Federated Database Systems, Proceedings of the Third International Conference on Data Engineering, p.477-484, February 03-05, 1987
• 15: Date, C.J., "Null values in database management," Proc. Second British National Conference on Databases, 1982.
• 16: Date, C.J., "The outer join," Proc. Second International Conference on Databases, 1983.
• 17: Dayal, U., "Query processing in a multidatabase system," Query Processing in Database Systems, Kim, Reiner and Batory (editors), 1985.
• 18: Dayal, U. and H. Hwang, "View definition and generalization for database integration in multibase: a system for heterogeneous distributed databases," IEEE Trans. Sofrw. Eng.. Nov. 1984.
• 19: S. M. Deen , R. R. Amin , M. C. Taylor, Data integration in distributed databases, IEEE Transactions on Software Engineering, v.13 n.7, p.860-864, July 1987 [doi>10.1109/TSE.1987.233497]
• 20: M. Samy Gamal-Eldin , G. Thomas , R. Elmasri, Integrating relational databases with support for updates, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.202-209, December 05-07, 1988, Austin, Texas, United States
• 21: Hammer, M. and S. Zdonik. "Knowledge-based query processing," Proc. VLDB, 1980.
• 22: Hai Yann Hwang , Umeshwar Dayal , Mohamed G. Gouda, Using semiouterjoins to process queries in multidatabase systems, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588033]
• 23: Jonathan J. King, Query optimization by semantic reasoning, University of Michigan Press, Ann Arbor, MI, 1984
• 24: Sreekumar T. Shenoy , Z. Meral Ozsoyoglu, A system for semantic query optimization, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.181-195, May 27-29, 1987, San Francisco, California, United States
• 25: John Miles Smith , Philip A Bernstein , Umeshwar Dayal , Nathan Goodman , Terry Landers, Multibase—integrating heterogeneous distributed database systems, on AFIPS Conference Proceedings; vol. 55 1986 National Computer Conference, p.335-347, June 1986, Las Vegas, Nevada, United States
• 26: John Miles Smith , Diane C. P. Smith, Database abstractions: aggregation and generalization, ACM Transactions on Database Systems (TODS), v.2 n.2, p.105-133, June 1977 [doi>10.1145/320544.320546]
• 27: Michael Stonebraker, Implementation of integrity constraints and views by query modification, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500091]
• 28: Templeton, M., D. Brill, A.L.P. Chen, S. Dao, E. Lund, R. MacGregor, P. Ward, "Mermaid - a front-end to distributed heterogeneous databases," Proceedings of the IEEE, May, 1987.
• 29: 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
• 30: Clement T. Yu , C. C. Chang , Marjorie Templeton , David Brill , Eric Lund, Query processing in a fragmented relational distributed system: Mermaid, IEEE Transactions on Software Engineering, v.11 n.8, p.795-810, Aug. 1985 [doi>10.1109/TSE.1985.232528]
• 31: Clement T. Yu , Keh-Chang Guh , David Brill , Arbee L. P. Chen, Partition Strategy for Distributed Query Processing in Fast Local Networks, IEEE Transactions on Software Engineering, v.15 n.6, p.780-793, June 1989 [doi>10.1109/32.24731]
• 32: Yu, C., K. Guh and A.L.P. Chen, "An integrated algorithm for distributed query processing," Proc. IFIP Conference on Distributed Processing, 1987.
• 33: Clement T. Yu , Leszek Lilien , Keh-Chang Guh , Marjorie Templeton , David Brill , Arbee L. P. Chen, Adaptive Techniques for Distributed Query Optimization, Proceedings of the Second International Conference on Data Engineering, p.86-93, February 05-07, 1986

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Design, Theory