Rule-Based Optimization and Query Processing in an Extensible Geometric Database System.

@article{DBLP:journals/tods/BeckerG92,
  author    = {Ludger Becker and
               Ralf Hartmut G{\"u}ting},
  title     = {Rule-Based Optimization and Query Processing in an Extensible
               Geometric Database System},
  journal   = {ACM Trans. Database Syst.},
  volume    = {17},
  number    = {2},
  year      = {1992},
  pages     = {247-303},
  ee        = {http://doi.acm.org/10.1145/128903.128905, db/journals/tods/BeckerG92.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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.

Copyright © 1992 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-2 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

Online Edition: ACM Digital Library

References

[1]

...

[2]

Don S. Batory, J. R. Barnett, J. F. Garza, K. P. Smith, K. Tsukuda, B. C. Twichell, T. E. Wise: GENESIS: An Extensible Database Management System. IEEE Trans. Software Eng. 14(11): 1711-1730(1988) BibTeX

[3]

Michael J. Carey, David J. DeWitt, Daniel Frank, Goetz Graefe, M. Muralikrishna, Joel E. Richardson, Eugene J. Shekita: The Architecture of the EXODUS Extensible DBMS. OODBS 1986: 52-65 BibTeX

[4]

Umeshwar Dayal, Frank Manola, Alejandro P. Buchmann, Upen S. Chakravarthy, David Goldhirsch, Sandra Heiler, Jack A. Orenstein, Arnon Rosenthal: Simplifying Complex Objects: The PROBE Approach to Modelling and Querying Them. BTW 1987: 17-37 BibTeX

[5]

...

[6]

Klaus R. Dittrich: Object-Oriented Database Systems: The Notion and the Issue. OODBS 1986: 2-4 BibTeX

[7]

Johann Christoph Freytag: A Rule-Based View of Query Optimization. SIGMOD Conference 1987: 173-180 BibTeX

[8]

Johann Christoph Freytag, Nathan Goodman: On the Translation of Relational Queries into Iterative Programs. ACM Trans. Database Syst. 14(1): 1-27(1989) BibTeX

[9]

...

[10]

Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172 BibTeX

[11]

Ralf Hartmut Güting: Geo-Relational Algebra: A Model and Query Language for Geometric Database Systems. EDBT 1988: 506-527 BibTeX

[12]

Ralf Hartmut Güting: Gral: An Extensible Relational Database System for Geometric Applications. VLDB 1989: 33-44 BibTeX

[13]

...

[14]

Ralf Hartmut Güting: Optimal Divide-and-Conquer to Compute Measure and Contour for a Set of Iso-Rectangles. Acta Inf. 21: 271-291(1984) BibTeX

[15]

...

[16]

Ralf Hartmut Güting, Roberto Zicari, David M. Choy: An Algebra for Structured Office Documents. ACM Trans. Inf. Syst. 7(2): 123-157(1989) BibTeX

[17]

...

[18]

Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388 BibTeX

[19]

...

[20]

Theo Härder, Andreas Reuter: Architektur von Datenbanksystemen für Non-Standard-Anwendungen. BTW 1985: 253-286 BibTeX

[21]

Andreas Henrich, Hans-Werner Six, Peter Widmayer: The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects. VLDB 1989: 45-53 BibTeX

[22]

Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984) BibTeX

[23]

Mavis K. Lee, Johann Christoph Freytag, Guy M. Lohman: Implementing an Interpreter for Functional Rules in a Query Optimizer. VLDB 1988: 218-229 BibTeX

[24]

Bruce G. Lindsay, John McPherson, Hamid Pirahesh: A Data Management Extension Architecture. SIGMOD Conference 1987: 220-226 BibTeX

[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. VLDB 1988: 294-305 BibTeX

[26]

Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27 BibTeX

[27]

...

[28]

C. Mohan, Donald J. Haderle, Yun Wang, Josephine M. Cheng: Single Table Access Using Multiple Indexes: Optimization, Execution, and Concurrency Control Techniques. EDBT 1990: 29-43 BibTeX

[29]

Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX

[30]

...

[30a]

...

[31]

Sylvia L. Osborn, T. E. Heaven: The Design of a Relational Database System with Abstract Data Types for Domains. ACM Trans. Database Syst. 11(3): 357-373(1986) BibTeX

[32]

H.-Bernhard Paul, Hans-Jörg Schek, Marc H. Scholl, Gerhard Weikum, Uwe Deppisch: Architecture and Implementation of the Darmstadt Database Kernel System. SIGMOD Conference 1987: 196-207 BibTeX

[33]

Arnon Rosenthal, Paul Helman: Understanding and Extending Transformation-Based Optimizers. IEEE Database Eng. Bull. 9(4): 44-51(1986) BibTeX

[34]

Peter M. Schwarz, Walter Chang, Johann Christoph Freytag, Guy M. Lohman, John McPherson, C. Mohan, Hamid Pirahesh: Extensibility in the Starburst Database System. OODBS 1986: 85-92 BibTeX

[35]

Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX

[36]

Michael Stonebraker, Lawrence A. Rowe: The Design of Postgres. SIGMOD Conference 1986: 340-355 BibTeX

[37]

Michael Stonebraker, W. Bradley Rubenstein, Antonin Guttman: Application of Abstract Data Types and Abstract Indices to CAD Data Bases. Engineering Design Applications 1983: 107-113 BibTeX

[38]

...

[39]

Paul F. Wilms, Peter M. Schwarz, Hans-Jörg Schek, Laura M. Haas: Incorporating Data Types in an Extensible Database Architecture. JCDKB 1988: 180-192 BibTeX

[40]

Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX

Referenced by

1. Navin Kabra, David J. DeWitt: OPT++: An Object-Oriented Implementation for Extensible Database Query Optimization. VLDB J. 8(1): 55-78(1999)
2. Gísli R. Hjaltason, Hanan Samet: Distance Browsing in Spatial Databases. ACM Trans. Database Syst. 24(2): 265-318(1999)
3. Ho-Hyun Park, Chan-Gun Lee, Yong-Ju Lee, Chin-Wan Chung: Early Separation of Filter and Refinement Steps in Spatial Query Optimization. DASFAA 1999: 161-168
4. Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter: Scalable Sweeping-Based Spatial Join. VLDB 1998: 570-581
5. Mitch Cherniack, Stanley B. Zdonik: Changing the Rules: Transformations for Rule-Based Optimizers. SIGMOD Conference 1998: 61-72
6. Hamid Pirahesh, T. Y. Cliff Leung, Waqar Hasan: A Rule Engine for Query Transformation in Starburst and IBM DB2 C/S DBMS. ICDE 1997: 391-400
7. Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Parallel Processing of Spatial Joins Using R-trees. ICDE 1996: 258-265
8. Ralf Hartmut Güting, Markus Schneider: Realm-Based Spatial Data Types: The ROSE Algebra. VLDB J. 4(2): 243-286(1995)
9. Michael Steinbrunn, Klaus Peithner, Guido Moerkotte, Alfons Kemper: Bypassing Joins in Disjunctive Queries. VLDB 1995: 228-238
10. Surajit Chaudhuri, Umeshwar Dayal, Tak W. Yan: Join Queries with External Text Sources: Execution and Optimization Techniques. SIGMOD Conference 1995: 410-422
11. M. Tamer Özsu, Adriana Muñoz, Duane Szafron: An Extensible Query Optimizer for an Objectbase Management System. CIKM 1995: 188-196
12. Ralf Hartmut Güting: An Introduction to Spatial Database Systems. VLDB J. 3(4): 357-399(1994)
13. Martin Erwig, Ralf Hartmut Güting: Explicit Graphs in a Functional Model for Spatial Databases. IEEE Trans. Knowl. Data Eng. 6(5): 787-804(1994)
14. Ralf Hartmut Güting: GraphDB: Modeling and Querying Graphs in Databases. VLDB 1994: 297-308
15. Alfons Kemper, Guido Moerkotte, Klaus Peithner, Michael Steinbrunn: Optimizing Disjunctive Queries with Expensive Predicates. SIGMOD Conference 1994: 336-347
16. Alfons Kemper, Guido Moerkotte, Klaus Peithner: A Blackboard Architecture for Query Optimization in Object Bases. VLDB 1993: 543-554
17. Surajit Chaudhuri, Kyuseok Shim: Query Optimization in the Presence of Foreign Functions. VLDB 1993: 529-542
18. Ralf Hartmut Güting: Second-Order Signature: A Tool for Specifying Data Models, Query Processing, and Optimization. SIGMOD Conference 1993: 277-286
19. Max J. Egenhofer: What's Special about Spatial? Database Requirements for Vehicle Navigation in Geographic Space (Extended Abstract). SIGMOD Conference 1993: 398-402
20. Ludger Becker, Klaus Hinrichs, Ulrich Finke: A New Algorithm for Computing Joins with Grid Files. ICDE 1993: 190-197
21. Walid G. Aref, Hanan Samet: Optimization for Spatial Query Processing. VLDB 1991: 81-90