Algebraic Optimization of Computations over Scientific Databases.

@inproceedings{DBLP:conf/vldb/WolniewiczG93,
  author    = {Richard H. Wolniewicz and
               Goetz Graefe},
  editor    = {Rakesh Agrawal and
               Se{\'a}n Baker and
               David A. Bell},
  title     = {Algebraic Optimization of Computations over Scientific Databases},
  booktitle = {19th International Conference on Very Large Data Bases, August
               24-27, 1993, Dublin, Ireland, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1993},
  isbn      = {1-55860-152-X},
  pages     = {13-24},
  ee        = {db/conf/vldb/WolniewiczG93.html},
  crossref  = {DBLP:conf/vldb/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Although scientific data analysis increasingly requires access and manipulation of large quantities of data, current database technology fails to meet the needs of scientific processing in a number of areas. To overcome acceptance problems among scientific users, database systems must provide performance and functionality comparable to current combinations of scientific programs and filesystems. Therefore, we propose extending the concept of a database query to include numeric computation over scientific databases.

In this paper, we examine the specification of an integrated algebra that includes traditional database operators for pattern matching and search as well asnumeric operators for scientific data sets. Through the use of a single integrated algebra, we can perform automatic optimization on scientific computation,realizing all of the traditional benefits of optimization.

We have experimented with a prototype optimizer which integrates sets, time series and spectra data types and operators on those types. Our results demonstrate that scientific database computations using numeric operators on multiple data types can be effectively optimized and permit performance gains that could not be realized without the integration.

This research has been performed in collaboration with the Space Grant Collegeat the University of Colorado at Boulder, where the results are being applied to the analysis of experimental data from satellite observations.

Copyright © 1993 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD 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/vldb8997 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/aDVD1 or /dvd

Printed Edition

References

[1]

José A. Blakeley, William J. McKenna, Goetz Graefe: Experiences Building the Open OODB Query Optimizer. SIGMOD Conference 1993: 287-296 BibTeX

[2]

A. Bolour, T. L. Anderson, L. J. Dekeyser, Harry K. T. Wong: The Role of Time in Information Processing: A Survey. SIGMOD Record 12(3): 27-50(1982) BibTeX

[3]

...

[4]

David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider: An Evaluation of Non-Equijoin Algorithms. VLDB 1991: 443-452 BibTeX

[5]

James C. French, Anita K. Jones, John L. Pfaltz: Summary of the Final Report of the NSF Workshop on Scientific Database Management. SIGMOD Record 19(4): 32-40(1990) BibTeX

[6]

Goetz Graefe: Volcano - An Extensible and Parallel Query Evaluation System. IEEE Trans. Knowl. Data Eng. 6(1): 120-135(1994) BibTeX

[7]

Goetz Graefe, Richard L. Cole, Diane L. Davison, William J. McKenna, Richard H. Wolniewicz: Extensible Query Optimization and Parallel Execution in Volcano. Query Processing for Advanced Database Systems, Dagstuhl 1991: 305-335 BibTeX

[8]

Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993: 209-218 BibTeX

[9]

Himawan Gunadhi, Arie Segev: A Framework for Query Optimization in Temporal Databases. SSDBM 1990: 131-147 BibTeX

[10]

Himawan Gunadhi, Arie Segev: Query Processing Algorithms for Temporal Intersection Joins. ICDE 1991: 336-344 BibTeX

[11]

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

[12]

Won Kim: Object-Oriented Approach to Managing Statistical and Scientific Databases. SSDBM 1990: 1-13 BibTeX

[13]

Leonore Neugebauer: Optimization and Evaluation of Database Queries Including Embedded Interpolation Procedures. SIGMOD Conference 1991: 118-127 BibTeX

[14]

Frank Olken, Doron Rotem: Simple Random Sampling from Relational Databases. VLDB 1986: 160-169 BibTeX

[15]

Frank Olken, Doron Rotem: Random Sampling from B+ Trees. VLDB 1989: 269-277 BibTeX

[16]

Frank Olken, Doron Rotem: Random Sampling from Database Files: A Survey. SSDBM 1990: 92-111 BibTeX

[17]

Frank Olken, Doron Rotem, Ping Xu: Random Sampling from Hash Files. SIGMOD Conference 1990: 375-386 BibTeX

[18]

...

[19]

Doron Rotem, Arie Segev: Physical Organization of Temporal Data. ICDE 1987: 547-553 BibTeX

[20]

Arie Segev, Arie Shoshani: Logical Modeling of Temporal Data. SIGMOD Conference 1987: 454-466 BibTeX

[21]

Arie Segev, Arie Shoshani: The Representation of a Temporal Data Model in the Relational Environment. SSDBM 1988: 39-61 BibTeX

[22]

Arie Segev, Himawan Gunadhi: Event-Join Optimization in Temporal Relational Databases. VLDB 1989: 205-215 BibTeX

[23]

Richard T. Snodgrass, Ilsoo Ahn: A Taxonomy of Time in Databases. SIGMOD Conference 1985: 236-246 BibTeX

[24]

Arie Shoshani: Statistical Databases: Characteristics, Problems, and some Solutions. VLDB 1982: 208-222 BibTeX

[25]

Arie Shoshani, Frank Olken, Harry K. T. Wong: Characteristics of Scientific Databases. VLDB 1984: 147-160 BibTeX

[26]

Arie Shoshani, Harry K. T. Wong: Statistical and Scientific Database Issues. IEEE Trans. Software Eng. 11(10): 1040-1047(1985) BibTeX

[27]

Arie Shoshani, Kyoji Kawagoe: Temporal Data Management. VLDB 1986: 79-88 BibTeX

[28]

Abraham Silberschatz, Michael Stonebraker, Jeffrey D. Ullman: Database Systems: Achievements and Opportunities - The "Lagunita" Report of the NSF Invitational Workshop on the Future of Database System Research held in Palo Alto, California, February 22-23, 1990. SIGMOD Record 19(4): 6-22(1990) BibTeX

Referenced by

1. Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: E-ADTs: Turbo-Charging Complex Data. IEEE Data Eng. Bull. 19(4): 11-18(1996)
2. Esa Falkenroth: Computational Indexes for Time Series. SSDBM 1996: 242-251
3. Goetz Graefe: The Cascades Framework for Query Optimization. IEEE Data Eng. Bull. 18(3): 19-29(1995)
4. Karl Aberer, Gisela Fischer: Semantic Query Optimization for Methods in Object-Oriented Database Systems. ICDE 1995: 70-79
5. Richard L. Cole, Goetz Graefe: Optimization of Dynamic Query Evaluation Plans. SIGMOD Conference 1994: 150-160
6. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
7. Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993: 209-218