Rule-based optimization and query processing in an extensible geometric database system

ABSTRACT

Gral is an extensible database system, based on the formal concept of a many-sorted relational algebra. Many-sorted algebra is used to define any application's query language, its query execution language, and its optimiztion rules. In this paper we describe Gral's optimization component. It provides (1) a sophisticated rule language—rules are transformations of abstract algebra expressions, (2) a general optimization framework under which more specific optimization algorithms can be implemented, and (3) several control mechanisms for the application of rules. An optimization algorithm can be specified as a series of steps. Each step is defined by its own collection of rules together with a selected control strategy. The general facilities are illustrated by the complete design of an example optimizer—in the form of a rule file—for a small nonstandard query language and an associated execution language. The query language includes selection, join, ordering, embedding derived values, aggregate functions, and several geometric operations. The example shows in particular how the special processing techniques of a geometric database systems, such as spatial join methods and geometric index structures, can be integrated into query processing and optimization of a relational database system. A similar, though larger, optimizer is fully functional within the geometric database system implemented as a Gral prototype.

REFERENCES

• 1: Don S. Batory, A Molecular Database Systems Technology, University of Texas at Austin, Austin, TX, 1987
• 2: D. S. Batory , J. R. Barnett , J. F. Garza , K. P. Smith , K. Tsukuda , C. Twichell , T. E. Wise, GENESIS: An Extensible Database Management System, IEEE Transactions on Software Engineering, v.14 n.11, p.1711-1730, November 1988 [doi>10.1109/32.9057]
• 3: Michael J. Carey , David J. DeWitt , Daniel Frank , M. Muralikrishna , Goetz Graefe , Joel E. Richardson , Eugene J. Shekita, The architecture of the EXODUS extensible DBMS, Proceedings on the 1986 international workshop on Object-oriented database systems, p.52-65, September 23-26, 1986, Pacific Grove, California, United States
• 4: DAYAL, U., MANOLA, F., BUCHMAN, A., CHAKRAVARTHY, U., GOLDHIRSCH, D., HEILER, S., ORENSTEIN, J., AND ROSENTHAL, A. Simplifying complex objects: The PROBE approach to modelling and querying them. In Proceedings of BTW 87, H. J. Schek and G. Schlageter, Eds., (Springer 1987), pp. 17-37.
• 5: N. Derrett , M.-C. Shan, Rule-based query optimization in IRIS, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.78-86, February 21-23, 1989, Louisville, Kentucky [doi>10.1145/75427.75435]
• 6: Klaus R. Dittrich, Object-oriented database systems (extended abstract): the notions and the issues, Proceedings on the 1986 international workshop on Object-oriented database systems, p.2-4, September 23-26, 1986, Pacific Grove, California, United States
• 7: 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
• 8: Johann Christoph Freytag , Nathan Goodman, On the translation of relational queries into iterative programs, ACM Transactions on Database Systems (TODS), v.14 n.1, p.1-27, March 1989 [doi>10.1145/62032.62033]
• 9: GOGUEN, J A., T~ATCH~R, J. W., AXD WAGNER, E.G. An initial algebra approach to the specification, correctness, and implementation of abstract data types. In Current Trends in Programming Methodology, Vol. IV. R. Yeh, Ed., Prentice-Hall 1978, 80-149.
• 10: 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
• 11: Ralf Hartmut Güting, Geo-Relational Algebra: A Model and Query Language for Geometric Database Systems, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.506-527, March 14-18, 1988
• 12: R. H. Güting, Gral: an extensible relational database system for geometric applications, Proceedings of the 15th international conference on Very large data bases, p.33-44, July 1989, Amsterdam, The Netherlands
• 13: G~T~NG, R.H. Modeling non-standard database systems by many-sorted algebras. Universit~t Dortmund, Fachbereich Informatik, Report 255, 1988.
• 14: G(~TING, R.H. Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles. Acta Inf. 21 (1984), 271-291.
• 15: Ralf Harmut Güting , Werner Schilling, A practical divide-and-conquer algorithm for the rectangle intersection problem, Information Sciences: an International Journal, v.42 n.2, p.95-112, July 1987 [doi>10.1016/0020-0255(87)90018-1]
• 16: Ralf Hartmut Güting , Roberto Zicari , David M. Choy, An algebra for structured office documents, ACM Transactions on Information Systems (TOIS), v.7 n.2, p.123-157, April 1989 [doi>10.1145/65935.65939]
• 17: HAAS, L. M., CODY, W. F., FREYTAG, J. C., LAPIS, G., LINDSAY, B. G., LEHMAN, G. M., ONe, K., AND PIRAHESH, H. An extensible processor for an extended relational query language. IBM Almaden Research Center, Report RJ6182, 1988.
• 18: L. M. Haas , J. C. Freytag , G. M. Lohman , H. Pirahesh, Extensible query processing in starburst, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.377-388, June 1989, Portland, Oregon, United States
• 19: HASAN, W., AND PmA~ES~, H. Query rewrite optimization in starburst. IBM Almaden Research Center, Report RJ 6367, 1988.
• 20: HXI~DER, T., AND REUTER, A Architektur yon Datenbanksystemen fur Non-Standard- Anwendungen (Architecture of database systems for non-standard applications). In Proceedings of the Conference on "Datenbanksysteme in Biiro, Tech,ik, and Wissenschaft", A Blaser, and P. Pistor Eds (Karlsruhe 1985), pp 253-286
• 21: A. Henrich , H. -W. Six , P. Widmayer, The LSD tree: spatial access to multidimensional and non-point objects, Proceedings of the 15th international conference on Very large data bases, p.45-53, July 1989, Amsterdam, The Netherlands
• 22: Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984 [doi>10.1145/356924.356928]
• 23: Mavis K. Lee , Johann Christoph Freytag , Guy M. Lohman, Implementing an Interpreter for Functional Rules in a Query Optimizer, Proceedings of the 14th International Conference on Very Large Data Bases, p.218-229, August 29-September 01, 1988
• 24: Bruce Lindsay , John McPherson , Hamid Pirahesh, A data management extension architecture, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.220-226, May 27-29, 1987, San Francisco, California, United States
• 25: Volker Linnemann , Klaus Küspert , Peter Dadam , Peter Pistor , R. Erbe , Alfons Kemper , Norbert Südkamp , Georg Walch , Mechtild Wallrath, Design and Implementation of an Extensible Database Management System Supporting User Defined Data Types and Functions, Proceedings of the 14th International Conference on Very Large Data Bases, p.294-305, August 29-September 01, 1988
• 26: Guy M. Lohman, Grammar-like functional rules for representing query optimization alternatives, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.18-27, June 01-03, 1988, Chicago, Illinois, United States
• 27: LEHMAN, G.M. Personal communication, 1990.
• 28: C. Mohan , Don Haderle , Yun Wang , Josephine Cheng, Single table access using multiple indexes: optimization, execution, and concurrency control techniques, Proceedings of the international conference on extending database technology on Advances in database technology, p.29-43, March 1990, Venice, Italy
• 29: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• 30: N. J. Nilsson, Principles of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1980
• 30a: ONe, K., AND LEHMAN, G.M. Extensible enumeration of feasible joins for relational query optimization. IBM Almaden Research Center, Report RJ6625, 1988.
• 31: Sylvia L. Osborn , T. E. Heaven, The design of a relational database system with abstract data types for domains, ACM Transactions on Database Systems (TODS), v.11 n.3, p.357-373, Sept. 1986 [doi>10.1145/6314.6461]
• 32: H. B. Paul , H. J. Schek , M. H. Scholl, Architecture and implementation of the Darmstadt database kernel system, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.196-207, May 27-29, 1987, San Francisco, California, United States
• 33: ROSENTHAL A., AND HELMAN, P. Understanding and extending transformation-based optimizers. IEEE Database Eng. 10, 4 (1987), 220-227.
• 34: P. Schwarz , W. Chang , J. C. Freytag , G. Lohman , J. McPherson , C. Mohan , H. Pirahesh, Extensibility in the Starburst database system, Proceedings on the 1986 international workshop on Object-oriented database systems, p.85-92, September 23-26, 1986, Pacific Grove, California, United States
• 35: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 36: Michael Stonebraker , Lawrence A. Rowe, The design of POSTGRES, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.340-355, May 28-30, 1986, Washington, D.C., United States
• 37: STONEBRAKER, M., RUBENSTEIN, B., AND GUTTMANN, A. Application of Abstract Data Types and Abstract Indices to CAD Databases. In Proceedings 1983 ACM Engineering Design Applications, pp. 107-114.
• 38: TESCHNER, J. Vergleich von Methoden zur Ausffihrung des Inside-Join in einem Geo- Datenbanksystem (Comparison of methods for performing the inside join in a geometric database system). Universit~t Dortmund, Fachbereich Informatik, Diplomarbeit, 1989.
• 39: WmMS, P. F., SCUWARZ, P. M., SCHEK, H.-J., AND HAAS, L.M. Incorporating Data Types in an Extensible Database Architecture. In Proceedings of the 3rd International Conference on Data and Knowledge Bases (Jerusalem, June 1988), pp. 180-192.
• 40: Eugene Wong , Karel Youssefi, Decomposition—a strategy for query processing, ACM Transactions on Database Systems (TODS), v.1 n.3, p.223-241, Sept. 1976 [doi>10.1145/320473.320479]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.3 Languages
          Subjects: Query languages

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms, Languages

Keywords:
extensibility, geometric query processing, many-sorted algebra, optimization, relational algebra, rule-based optimization