L. M. Haas
J. C. Freytag
H. Pirahesh
Skip Abstract Section
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.
- ABIT86 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). Google Scholar
Digital Library
- ASTR76 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). Google ScholarDigital Library
- BACK78 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). Google ScholarDigital Library
- BANC86 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). Google ScholarDigital Library
- BANE87 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). Google ScholarDigital Library
- BATO86 Batory, D., GENESIS: A Project to Develop an Extensible Database Management System, Procs. 1986 lnt. Workshop on Object-oriented Database Systems (Asilomar, Sept. 1986). Google ScholarDigital Library
- BATO87a Batory, D., A Molecular Database Systems Technology, Teeh. Report TR-87-23 (Dept. of Comp. Sci., Univ. of Texas at Austin, June 1987). Google ScholarDigital Library
- BATO87b Batory, D., Extensible Cost Models and Query Optimization in GENESIS, IEEE Database Engineering 10:4 (Dec. 1986).Google Scholar
- CARE86 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). Google ScholarDigital Library
- CARR79 Carr, B., Graphs and Networks, Oxford University Press: New York, NY, 1979, ch.3 (1979).Google Scholar
- CHAM81 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). Google ScholarDigital Library
- DATE84 Date, C., A Critique of the SQL Database, A CM SIGMOD Record (1984). Google ScholarDigital Library
- DAYA86 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). Google ScholarDigital Library
- DAYA87 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). Google ScholarDigital Library
- FORG82 Forgy, C., RETE: A fast algorithm for the many pattern/many object pattern match problem, Artificial Intelligence 19:17-38 (1982).Google ScholarDigital Library
- FREY86 Freytag, J.C. and N. Goodman, Rule-Based Translation of Relational Queries into Iterative Programs, Procs. ACM SIGMOD (Washington, D.C., May 1986). Google ScholarDigital Library
- FREY87 Freytag, J.C., A Rule-Based View of Query Optimization, Procs. A CM SIGMOD (San Francisco, May 1987). Google ScholarDigital Library
- GANS87 Ganski, R. and H. Wong, Optimization of Nested SQL Queries Revisited, Procs. ACM SIGMOD (San Francisco, May 1987). Google ScholarDigital Library
- GRAE87a Graefe, G. and D. DeWitt, The EXODUS Optimizer Generator, Procs. A CM SIGMOD (San Francisco, May 1987). Google ScholarDigital Library
- GRAE87b Graefe, G., Software Modularization with the EXODUS Optimizer Generator, 1EEE Database Engineering 10:4 (Dec. 1986).Google Scholar
- GRAE89 Graefe, G., Dynamic Query Evaluation Plans, Oregon Graduate Center TR No. CS/E 88-003 (1988).Google Scholar
- GRIF76 Griftiths, P. and B. Wade, An Authorization Mechanism for a Relational Database System, A CM Trans. on Database Systems 1:3 (Sept. 1976). Google ScholarDigital Library
- GUTT84 Guttman, A., R-Trees: A Dynamic Index Structure for Spatial Searching, Procs. A CM SIGMOD (Boston, June 1984). Google ScholarDigital Library
- HAAS88 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).Google Scholar
- HASA88 Hasan, W, and H. Pirahesh, A Rule System for Query Rewrite Optimization in Starburst, IBM Research Report RJ6367 (Aug, 1988).Google Scholar
- IBM87 IBM Systems Application Architecture, Common Programming Interface: Database Reference, SC 26-4348-0 (Sept. 1987).Google Scholar
- KIM82 Kim, W., On Optimizing an SQL-like Nested Query, A CM Trans. on Database Systems 7:3 (Sept. 1982). Google ScholarDigital Library
- KIM87 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). Google ScholarDigital Library
- KING81 King, J., QUIST: A system for semantic query optimization in relational database, Proes. of the Seventh International Conference on Very Large Databases (1981).Google Scholar
- LEE88 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). Google ScholarDigital Library
- LIND87 Lindsay, B., J. McPherson and H. Pirahesh, A Data Management Extension Architecture, Procs. ACM SIGMOD (San Francisco, May 1987). Google ScholarDigital Library
- LOHM84 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). Google ScholarDigital Library
- LOHM85 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).Google Scholar
- LOHM88 Lohman, G., Grammar-like Functional Rules for Representing Query Optimization Alternatives, Procs. of ACM-SIGMOD (Chicago, IL, June 1988). Google ScholarDigital Library
- MACK86 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). Google ScholarDigital Library
- MAIE86 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). Google ScholarDigital Library
- ONO88 Ono, K. and G. Lohman, Extensible Enumeration of Feasible Joins for Relational Query Optimization, IBM Research Report RJ6625 (Dec. 1988).Google Scholar
- OTT82 Ott, N. and K. Horlander, Removing Redundant Join Operations in Queries Involving Views, Heidelberg Scientific Center, TR 82.03.003 (March 1982).Google Scholar
- PAUL87 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). Google ScholarDigital Library
- PIRA89 Pirahesh, H. and S. Finkelstein, An Extensible Query Graph Model, internal working paper.Google Scholar
- RIES83 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).Google Scholar
- ROSE84 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). Google ScholarDigital Library
- ROSE86 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). Google ScholarDigital Library
- ROSE87 Rosenthal, A. and P. Helman, Understanding and Extending Transformation-Based Optimizers, 1EEE Database l~ngineering 10:4 (Dec. 1986).Google Scholar
- SCHW86 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). Google ScholarDigital Library
- SELI79 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). Google ScholarDigital Library
- SHEN87 Shenoy, S. and Z. Ozsoyoglu, A System for Semantic Query Optimization, Procs. ACM SIGMOD (May 1987). Google ScholarDigital Library
- STON76 Stonebraker, M., E. Wong, P. Kreps and G. Held, The design and implementation of INGRES, ACM Trans. on Database Systems 1:3 (Sept. 1976). Google ScholarDigital Library
- STON86 Stonebraker, M. and L. Rowe, The Design of POSTGRES, Procs. A CM SIGMOD (Washington, D.C., May 1986). Google ScholarDigital Library
- ULLM85 Ullman, J., Implementation of Logic Query Languages for Databases, A CM Trans. on Database Systems 10:3 (Sept. 1985). Google ScholarDigital Library
- WILM88 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).Google Scholar
- ZANI82 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). Google ScholarDigital Library
Index Terms
- Extensible query processing in starburst
Recommendations
Extensible/rule based query rewrite optimization in Starburst
This paper describes the Query Rewrite facility of the Starburst extensible database system, a novel phase of query optimization. We present a suite of rewrite rules used in Starburst to transform queries into equivalent queries for faster execution, ...
Extensible query processing in starburst
SIGMOD '89: Proceedings of the 1989 ACM SIGMOD international conference on Management of dataToday'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 PapersStarburst 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