Rule-based query optimization in IRIS

ABSTRACT

In this paper we present the design and initial performance results of a rule-based query optimizer used in Iris, an object-oriented database system [3]. Query optimization methods are expressed as rules and the entire query process is carried out in a way analogous to the operation of production systems in AI. Two kinds of rules are used: the first kind transform a query, represented as a relational algebra expression, into an equivalent, but simpler, query; the second kind add information to the relational algebra representation to specify join order and data access methods. Preliminary results show that the speed of the query optimizer and the performance of the execution plans generated are comparable to those in a traditional relational database system.

REFERENCES

• 1: "Database language - SQL", ANSI X3.135, American National Standards Institute, Inc., New York, New York, 1986.
• 2: Johann Christoph Freytag, A rule-based view of query optimization, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.173-180, May 27-29, 1987, San Francisco, California, United States
• 3: Fishman, D. et. al., "Iris: An Object Oriented Database Management System", ACM Trans. on Office Information Systems, Vol 5, No. 1, January 1987.
• 4: Goetz Graefe , David J. DeWitt, The EXODUS optimizer generator, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.160-172, May 27-29, 1987, San Francisco, California, United States
• 5: Robert B. Hagmann, An Observation on Database Buffering Performance Metrics, Proceedings of the 12th International Conference on Very Large Data Bases, p.289-293, August 25-28, 1986
• 6: Hall, P., "Optimization of Single Expressions in a Relational Data Base System", IBM J. Res. Develop, May 1976.
• 7: Nguyen, G., Ferrat, L., and Galy, H., "A high-level user interface for a local network database system", Proc. IEEE Infocom, 1982.
• 8: Gregory Piatetsky-Shapiro , Charles Connell, Accurate estimation of the number of tuples satisfying a condition, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 9: Rosenthal, A., Dayal, U., and Reiner, D., "Fast Query Optimization over a Large Strategy Space: The Pilot Pass Approach", Unpublished manuscript, 1986.
• 10: Ryan, T., and Cate, H., "Performance evaluations of Iris/OSQL and HP-SQL', Persona} communication, 1987.
• 11: Ravi Sethi, Testing for the Church-Rosser Property, Journal of the ACM (JACM), v.21 n.4, p.671-679, Oct. 1974 [doi>10.1145/321850.321862]
• 12: Ming-Chien Shan, Optimal Plan Search in a Rule-Based Query Optimizer, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.92-112, March 14-18, 1988
• 13: Shan, M. and Lu, H., "B++-Access Method supporting Point Computation of a Recursive Proc. of Int. Computer Science 88, Hong Kong, December, 1988.
• 14: Shan, M., and Neimat, M., "Recursive Support in a Relational Framework", Packard Research Report, May, 15. Shan, M.,
• 15: Shan M. "Redundant join elimination", Packard Research Report, (In 16.
• 16: John Miles Smith , Philip Yen-Tang Chang, Optimizing the performance of a relational algebra database interface, Communications of the ACM, v.18 n.10, p.568-579, Oct. 1975 [doi>10.1145/361020.361025]
• 17: Ullman, 3., "Principles of Database 2nd edition, Computer Science land, 1982.
• 18: Patrick Henry Winston, Artificial intelligence (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representations (procedural and rule-based)

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Performance