Article

Free access

Extensible query processing in starburst

Authors:

H. PiraheshAuthors Info & Claims

SIGMOD '89: Proceedings of the 1989 ACM SIGMOD international conference on Management of data

Pages 377 - 388

https://doi.org/10.1145/67544.66962

Published: 01 June 1989 Publication History

Abstract

Today's DBMSs are unable to support the increasing demands of the various applications that would like to use a DBMS. Each kind of application poses new requirements for the DBMS. The Starburst project at IBM's Almaden Research Center aims to extend relational DBMS technology to bridge this gap between applications and the DBMS. While providing a full function relational system to enable sharing across applications, Starburst will also allow (sophisticated) programmers to add many kinds of extensions to the base system's capabilities, including language extensions (e.g., new datatypes and operations), data management extensions (e.g., new access and storage methods) and internal processing extensions (e.g., new join methods and new query transformations). To support these features, the database query language processor must be very powerful and highly extensible. Starburst's language processor features a powerful query language, rule-based optimization and query rewrite, and an execution system based on an extended relational algebra. In this paper, we describe the design of Starburst's query language processor and discuss the ways in which the language processor can be extended to achieve Starburst's goals.

References

[1]

Abiteboul, S., M. Scholl, G. Gardarin and E. Simon, Towards D BMSs for Supporting new Applications, Procs. of the Twelfth International Conference on Very Large Databases (Kyoto, Aug. 1986).

Digital Library

[2]

Astrahan, M., M. Blasgen, D. Chamberlin, K. Eswaran, J. Gray, P. Grifflths, W. King, R. Lorie, P. McJones, J. Mehl, G. Putzolu, I. Traiger, B. Wade and V. Watson, System R: Relational approach to database management, A CM Transactions on Database Systems 1:2 (June 1976).

Digital Library

[3]

Backus, J., Can programming be liberated from the von Neumann style? A functional style and its algebra of programs, Comm. ACM 21:8 (Aug. 1978).

Digital Library

[4]

Bancilhon, F., D. Ma. ier, Y. Sagiv and J. Ullman, Magic sets and other strange ways to implement logic programs, 5th ACM Symposium on Principles of Database Systems, Cambridge (1985).

Digital Library

[5]

Banerjee, J., W. Kim, tl.J. Kim and H. Korth, Semantics and Implementation of Schema Evolution in Object-Oriented Databases, Procs. A CM SIGMOD (San Francisco, May 1987).

Digital Library

[6]

Batory, D., GENESIS: A Project to Develop an Extensible Database Management System, Procs. 1986 lnt. Workshop on Object-oriented Database Systems (Asilomar, Sept. 1986).

Digital Library

[7]

Batory, D., A Molecular Database Systems Technology, Teeh. Report TR-87-23 (Dept. of Comp. Sci., Univ. of Texas at Austin, June 1987).

Digital Library

[8]

Batory, D., Extensible Cost Models and Query Optimization in GENESIS, IEEE Database Engineering 10:4 (Dec. 1986).

[9]

Carey, M., D. DeWitt, D. Frank, G. Graefe, M. Muralikrishna, J. Richardson and E. Shekita, The Architecture of the EXODUS Extensible Database System, Procs. 1986 Int. Workshop on Object-oriented Database Systems (Asilomar, Sept. 1986).

Digital Library

[10]

Carr, B., Graphs and Networks, Oxford University Press: New York, NY, 1979, ch.3 (1979).

[11]

Chamberlin, D., M. Astrahan, W. King, R. Lode, J. Mehl, T. Price, M. Schkolnick, P. Selinger, D. Slutz, B, Wade and R. Yost, Support for Repetitive Transactions and Ad-Hoc Queries in System R, A CM Trans. on Database Systems 6:1 (Mar. 1981).

Digital Library

[12]

Date, C., A Critique of the SQL Database, A CM SIGMOD Record (1984).

Digital Library

[13]

DayaI,U. and J. Smith, PROBE: A Knowledge- Oriented Database Management :~ystem, On Knowledge Base Management Systems: Integrating Artificial Intelligence and Database Technologies, Springer Verlag (Brodie & Mylopoulos (eds.), 1986).

Digital Library

[14]

Dayal, U., Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers, Procs. of the Thirteenth International Conference on Very Large Databases (Brighton, Sept. 1987).

Digital Library

[15]

Forgy, C., RETE: A fast algorithm for the many pattern/many object pattern match problem, Artificial Intelligence 19:17-38 (1982).

Digital Library

[16]

Freytag, J.C. and N. Goodman, Rule-Based Translation of Relational Queries into Iterative Programs, Procs. ACM SIGMOD (Washington, D.C., May 1986).

Digital Library

[17]

Freytag, J.C., A Rule-Based View of Query Optimization, Procs. A CM SIGMOD (San Francisco, May 1987).

Digital Library

[18]

Ganski, R. and H. Wong, Optimization of Nested SQL Queries Revisited, Procs. ACM SIGMOD (San Francisco, May 1987).

Digital Library

[19]

Graefe, G. and D. DeWitt, The EXODUS Optimizer Generator, Procs. A CM SIGMOD (San Francisco, May 1987).

Digital Library

[20]

Graefe, G., Software Modularization with the EXODUS Optimizer Generator, 1EEE Database Engineering 10:4 (Dec. 1986).

[21]

Graefe, G., Dynamic Query Evaluation Plans, Oregon Graduate Center TR No. CS/E 88-003 (1988).

[22]

Griftiths, P. and B. Wade, An Authorization Mechanism for a Relational Database System, A CM Trans. on Database Systems 1:3 (Sept. 1976).

Digital Library

[23]

Guttman, A., R-Trees: A Dynamic Index Structure for Spatial Searching, Procs. A CM SIGMOD (Boston, June 1984).

Digital Library

[24]

Haas, L, W. Cody, J. Freytag, G. Lapis, B. Lindsay, G. Lohman and H. Pirahesh, An Extensible Processor for an Extended Relational Query Language, IBM Research Report RJ 6182 (April 1988).

[25]

Hasan, W, and H. Pirahesh, A Rule System for Query Rewrite Optimization in Starburst, IBM Research Report RJ6367 (Aug, 1988).

[26]

IBM Systems Application Architecture, Common Programming Interface: Database Reference, SC 26-4348-0 (Sept. 1987).

[27]

Kim, W., On Optimizing an SQL-like Nested Query, A CM Trans. on Database Systems 7:3 (Sept. 1982).

Digital Library

[28]

Kim, W., J. Banerjee, H.-T. Chou, J. Garza and D. Woelk, Composite Object Support in an Object- Oriented Database System, Proes. A CM Conf. on Object Oriented Programming Systems, Languages and Applications (Orlando, Oct. 1987).

Digital Library

[29]

King, J., QUIST: A system for semantic query optimization in relational database, Proes. of the Seventh International Conference on Very Large Databases (1981).

[30]

Lee, M., J.C. Freytag and G. Lohman, Implementing an interpreter for Functional Rules in a Query Optimizer, Procs. of the Fourteenth International Conferenee on Very Large Databases (Los Angeles, Aug. 1988).

Digital Library

[31]

Lindsay, B., J. McPherson and H. Pirahesh, A Data Management Extension Architecture, Procs. ACM SIGMOD (San Francisco, May 1987).

Digital Library

[32]

Lohman, G., L. i-laas, R. Kistler, P. Selinger and D. Daniels, Optimization of Nested Queries in a Distributed Relational Database, Proc. of the Tenth International Conference on Very Large Database (Singapore, Aug. 1984).

Digital Library

[33]

Lohman, G., C. Mohan, L. Haas, B. Lindsay, P. Selinger, P. Wilms and D. Daniels, Query Processing in R*, Query Processing in Database Systems, Springer- Verlag (Kim, Batory, & Reiner (eds.), 1985).

[34]

Lohman, G., Grammar-like Functional Rules for Representing Query Optimization Alternatives, Procs. of ACM-SIGMOD (Chicago, IL, June 1988).

Digital Library

[35]

Mackert, L. and G. Lohman, R* Optimizer Validation and Performance Evaluation for Distributed Queries, Procs. of the Twelfth International Conference on Very Large Databases (Kyoto, August 1986).

Digital Library

[36]

Maier, D., J. Stein, A. Otis and A. Purdy, Development of an Object-Oriented DBMS, Procs. ACM Conf. on Object Oriented Programming Systems, Languages and Applications (Portland, Sept. 1986).

Digital Library

[37]

Ono, K. and G. Lohman, Extensible Enumeration of Feasible Joins for Relational Query Optimization, IBM Research Report RJ6625 (Dec. 1988).

[38]

Ott, N. and K. Horlander, Removing Redundant Join Operations in Queries Involving Views, Heidelberg Scientific Center, TR 82.03.003 (March 1982).

[39]

Paul, H., H. Schek, M. Scholl, G. Weikum and U. Deppisch, Architecture and Implementation of the Darmstadt Database Kernel System, Procs. A CM SIGMOD (San Francisco, CA, May 1987).

Digital Library

[40]

Pirahesh, H. and S. Finkelstein, An Extensible Query Graph Model, internal working paper.

[41]

Ries, D., A. Chan, U. Dayal, S. Fox, K. Wen-Te and L. Yedw.ab, Decompilation and Optimization for ADAPLEX: A procedural Database Language, Technical Report, CCA-82-04 (Sept. 1983).

[42]

Rosenthal, A. and D. Reiner, Extending the Algebraic Framework of Query Processing to handle Outerjoins, Procs. of the Tenth International Conference on Very Large Databases (Singapore, Aug. 1984).

Digital Library

[43]

Rosenthal, A., S. Heiler, U. Dayal and F. Manola, Traversal Recursion: A Practical Approach to Supporting Recursive Applications, Procs. A CM Sigmod (Boston, June 1984).

Digital Library

[44]

Rosenthal, A. and P. Helman, Understanding and Extending Transformation-Based Optimizers, 1EEE Database l~ngineering 10:4 (Dec. 1986).

[45]

Schwarz, P., W. Chang, J.C. Freytag, G. Lohman, J. McPherson, C. Mohan, H. Pirahesh, Extensibility in the Starburst Database System, Procs. 1986 lnt. Workshop on Object-oriented Database Systems (Asilomar, Sept. 1986).

Digital Library

[46]

Selinger, P., M. Astrahan, D. Chamberlin, R. Lorie, and T. Price, Access Path Selection in a Relational Database Management System, Procs. ACM SIGMOD (June 1979).

Digital Library

[47]

Shenoy, S. and Z. Ozsoyoglu, A System for Semantic Query Optimization, Procs. ACM SIGMOD (May 1987).

Digital Library

[48]

Stonebraker, M., E. Wong, P. Kreps and G. Held, The design and implementation of INGRES, ACM Trans. on Database Systems 1:3 (Sept. 1976).

Digital Library

[49]

Stonebraker, M. and L. Rowe, The Design of POSTGRES, Procs. A CM SIGMOD (Washington, D.C., May 1986).

Digital Library

[50]

Ullman, J., Implementation of Logic Query Languages for Databases, A CM Trans. on Database Systems 10:3 (Sept. 1985).

Digital Library

[51]

Wilms, P., P. Schwarz, H. Schek and L. Haas, Incorporating Data Types in an Extensible Database Architecture, 3rd lnt'l Conference on Data and Knowledge Bases (Jerusalem, June 1988).

[52]

Zaniolo, C. and M. Melkanoff, A Formal Approach to the Definition and the Design of Conceptual Schemata for Database Systems, A CM Trans. on Database Systems 7:1 (March 1982).

Digital Library

Cited By

Fejza AGenevès PLayaïda N(2024)Efficient Enumeration of Recursive Plans in Transformation-Based Query OptimizersProceedings of the VLDB Endowment10.14778/3681954.368198617:11(3095-3108)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681986
Gatterbauer W(2023)A Tutorial on Visual Representations of Relational QueriesProceedings of the VLDB Endowment10.14778/3611540.361157816:12(3890-3893)Online publication date: 12-Sep-2023
https://dl.acm.org/doi/10.14778/3611540.3611578
Zhu EHuang SChaudhuri S(2023)High-Performance Row Pattern Recognition Using JoinsProceedings of the VLDB Endowment10.14778/3579075.357909016:5(1181-1195)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.14778/3579075.3579090
Show More Cited By

Index Terms

Extensible query processing in starburst

Recommendations

Extensible query processing in starburst

Today's DBMSs are unable to support the increasing demands of the various applications that would like to use a DBMS. Each kind of application poses new requirements for the DBMS. The Starburst project at IBM's Almaden Research Center aims to extend ...
Extensions to Starburst: objects, types, functions and rules
CASCON '10: CASCON First Decade High Impact Papers

Starburst is a research prototype of an extensible relational database management system that is under development at the IBM Almaden Research Center. Through extensions to Starburst, we are incorporating the advanced structuring and data behavior ...
Extensions to Starburst: objects, types, functions and rules
CASCON '91: Proceedings of the 1991 conference of the Centre for Advanced Studies on Collaborative research

Starburst is a research prototype of an extensible relational database management system that is under development at the IBM Almaden Research Center. Through extensions to Starburst, we are incorporating the advanced structuring and data behavior ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '89: Proceedings of the 1989 ACM SIGMOD international conference on Management of data

June 1989

451 pages

ISBN:0897913175

DOI:10.1145/67544

ACM SIGMOD Record Volume 18, Issue 2
June 1989
442 pages
ISSN:0163-5808
DOI:10.1145/66926
Editors:
James Clifford,
Bruce Lindsay,
David Maier
Issue’s Table of Contents

Copyright © 1989 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS04

Sponsor:

SIGMOD

SIGMOD/PODS04: International Conference on Management of Data and Symposium on Principles Database and Systems

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

225
Total Citations
View Citations
1,635
Total Downloads

Downloads (Last 12 months)343
Downloads (Last 6 weeks)24

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fejza AGenevès PLayaïda N(2024)Efficient Enumeration of Recursive Plans in Transformation-Based Query OptimizersProceedings of the VLDB Endowment10.14778/3681954.368198617:11(3095-3108)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681986
Gatterbauer W(2023)A Tutorial on Visual Representations of Relational QueriesProceedings of the VLDB Endowment10.14778/3611540.361157816:12(3890-3893)Online publication date: 12-Sep-2023
https://dl.acm.org/doi/10.14778/3611540.3611578
Zhu EHuang SChaudhuri S(2023)High-Performance Row Pattern Recognition Using JoinsProceedings of the VLDB Endowment10.14778/3579075.357909016:5(1181-1195)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.14778/3579075.3579090
Gavriilidis HBeedkar KQuiané-Ruiz JMarkl V(2023)In-Situ Cross-Database Query Processing2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00214(2794-2807)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00214
Gatterbauer W(2020)Databases will visualize queries tooProceedings of the VLDB Endowment10.14778/3402755.34028054:12(1498-1501)Online publication date: 3-Jun-2020
https://dl.acm.org/doi/10.14778/3402755.3402805
Rigger MSu Z(2020)Finding bugs in database systems via query partitioningProceedings of the ACM on Programming Languages10.1145/34282794:OOPSLA(1-30)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428279
Pierazzi FMezzour GHan QColajanni MSubrahmanian V(2020)A Data-driven Characterization of Modern Android SpywareACM Transactions on Management Information Systems10.1145/338215811:1(1-38)Online publication date: 10-Apr-2020
https://dl.acm.org/doi/10.1145/3382158
Li PHuang LWang CLai JHuang D(2020)Community Detection by Motif-Aware Label PropagationACM Transactions on Knowledge Discovery from Data10.1145/337853714:2(1-19)Online publication date: 9-Feb-2020
https://dl.acm.org/doi/10.1145/3378537
Yan XLou ZHu SYe Y(2020)Multi-task Information Bottleneck Co-clustering for Unsupervised Cross-view Human Action CategorizationACM Transactions on Knowledge Discovery from Data10.1145/337539414:2(1-23)Online publication date: 9-Feb-2020
https://dl.acm.org/doi/10.1145/3375394
Lin CChuang KWu WChen M(2020)Budget-Constrained Real-Time Bidding OptimizationACM Transactions on Knowledge Discovery from Data10.1145/337539314:2(1-27)Online publication date: 9-Feb-2020
https://dl.acm.org/doi/10.1145/3375393
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents