ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Extensible Query Processing in Starburst.

Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388
@inproceedings{DBLP:conf/sigmod/HaasFLP89,
  author    = {Laura M. Haas and
               Johann Christoph Freytag and
               Guy M. Lohman and
               Hamid Pirahesh},
  editor    = {James Clifford and
               Bruce G. Lindsay and
               David Maier},
  title     = {Extensible Query Processing in Starburst},
  booktitle = {Proceedings of the 1989 ACM SIGMOD International Conference on
               Management of Data, Portland, Oregon, May 31 - June 2, 1989},
  publisher = {ACM Press},
  year      = {1989},
  pages     = {377-388},
  ee        = {http://doi.acm.org/10.1145/67544.66962, db/conf/sigmod/HaasFLP89.html},
  crossref  = {DBLP:conf/sigmod/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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.

Copyright © 1989 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.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

James Clifford, Bruce G. Lindsay, David Maier (Eds.): Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 - June 2, 1989. ACM Press 1989 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 18(2), June 1989
Contents

Online Edition: ACM Digital Library


References

[ABIT86]
Serge Abiteboul, Michel Scholl, Georges Gardarin, Eric Simon: Towards DBMSs for Supporting New Applications. VLDB 1986: 423-435 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ASTR76]
Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BACK78]
John W. Backus: Can Programming Be Liberated From the von Neumann Style? A Functional Style and its Algebra of Programs. Commun. ACM 21(8): 613-641(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BANC86]
François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BANE87]
Jay Banerjee, Won Kim, Hyoung-Joo Kim, Henry F. Korth: Semantics and Implementation of Schema Evolution in Object-Oriented Databases. SIGMOD Conference 1987: 311-322 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BATO86]
Don S. Batory: GENESIS: A Project to Develop an Extensible Database Management System. OODBS 1986: 207-208 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BATO87a]
...
[BATO87b]
Don S. Batory: Extensible Cost Models and Query Optimization in GENESIS. IEEE Database Eng. Bull. 9(4): 30-36(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CARE86]
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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CARR79]
...
[CHAM81]
Donald D. Chamberlin, Morton M. Astrahan, W. Frank King III, Raymond A. Lorie, James W. Mehl, Thomas G. Price, Mario Schkolnick, Patricia G. Selinger, Donald R. Slutz, Bradford W. Wade, Robert A. Yost: Support for Repetitive Transactions and Ad Hoc Queries in System R. ACM Trans. Database Syst. 6(1): 70-94(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DATE84]
C. J. Date: A Critique of the SQL Database Language. SIGMOD Record 14(3): 8-54(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DAYA86]
...
[DAYA87]
Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FORG82]
Charles Forgy: Rete: A Fast Algorithm for the Many Patterns/Many Objects Match Problem. Artif. Intell. 19(1): 17-37(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FREY86]
Johann Christoph Freytag, Nathan Goodman: Rule-Based Translation of Relational Queries into Iterative Programs. SIGMOD Conference 1986: 206-214 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FREY87]
Johann Christoph Freytag: A Rule-Based View of Query Optimization. SIGMOD Conference 1987: 173-180 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GANS87]
Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GRAE87a]
Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GRAE87b]
Goetz Graefe: Software Modularization with the EXODUS Optimizer Generator. IEEE Database Eng. Bull. 9(4): 37-45(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GRAE89]
Goetz Graefe, Karen Ward: Dynamic Query Evaluation Plans. SIGMOD Conference 1989: 358-366 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GRIF76]
Patricia P. Griffiths, Bradford W. Wade: An Authorization Mechanism for a Relational Database System. ACM Trans. Database Syst. 1(3): 242-255(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GUTT84]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HAAS88]
...
[HASA88]
...
[IBM87]
...
[KIM82]
Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KIM87]
Won Kim, Jay Banerjee, Hong-Tai Chou, Jorge F. Garza, Darrell Woelk: Composite Object Support in an Object-Oriented Database System. OOPSLA 1987: 118-125 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KING81]
Jonathan J. King: QUIST: A System for Semantic Query Optimization in Relational Databases. VLDB 1981: 510-517 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LEE88]
Mavis K. Lee, Johann Christoph Freytag, Guy M. Lohman: Implementing an Interpreter for Functional Rules in a Query Optimizer. VLDB 1988: 218-229 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LIND87]
Bruce G. Lindsay, John McPherson, Hamid Pirahesh: A Data Management Extension Architecture. SIGMOD Conference 1987: 220-226 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LOHM84]
Guy M. Lohman, Dean Daniels, Laura M. Haas, Ruth Kistler, Patricia G. Selinger: Optimization of Nested Queries in a Distributed Relational Database. VLDB 1984: 403-415 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LOHM85]
Guy M. Lohman, C. Mohan, Laura M. Haas, Dean Daniels, Bruce G. Lindsay, Patricia G. Selinger, Paul F. Wilms: Query Processing in R*. Query Processing in Database Systems 1985: 31-47 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LOHM88]
Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MACK86]
Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Distributed Queries. VLDB 1986: 149-159 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MAIE86]
David Maier, Jacob Stein, Allen Otis, Alan Purdy: Development of an Object-Oriented DBMS. OOPSLA 1986: 472-482 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ONO88]
...
[OTT82]
...
[PAUL87]
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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PIRA89]
...
[RIES83]
...
[ROSE84]
Arnon Rosenthal, David S. Reiner: Extending the Algebraic Framework of Query Processing to Handle Outerjoins. VLDB 1984: 334-343 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ROSE86]
Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ROSE87]
Arnon Rosenthal, Paul Helman: Understanding and Extending Transformation-Based Optimizers. IEEE Database Eng. Bull. 9(4): 44-51(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SCHW86]
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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SELI79]
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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SHEN87]
Sreekumar T. Shenoy, Z. Meral Özsoyoglu: A System for Semantic Query Optimization. SIGMOD Conference 1987: 181-195 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[STON76]
Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[STON86]
Michael Stonebraker, Lawrence A. Rowe: The Design of Postgres. SIGMOD Conference 1986: 340-355 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ULLM85]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[WILM88]
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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ZANI82]
Carlo Zaniolo, Michel A. Melkanoff: A Formal Approach to the Definition and the Design of Conceptual Schemata for Database Systems. ACM Trans. Database Syst. 7(1): 24-59(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Referenced by

  1. Laura M. Haas: Review - Physical Data Independence, Constraints, and Optimization with Universal Plans. ACM SIGMOD Digital Review 1: (1999)
  2. Mary Tork Roth, Fatma Ozcan, Laura M. Haas: Cost Models DO Matter: Providing Cost Information for Diverse Data Sources in a Federated System. VLDB 1999: 599-610
  3. Michael Jaedicke, Bernhard Mitschang: User-Defined Table Operators: Enhancing Extensibility for ORDBMS. VLDB 1999: 494-505
  4. Gunter Saake, Andreas Heuer: Datenbanken: Implementierungstechniken. MITP-Verlag 1999, ISBN 3-8266-0513-6
    Contents
  5. Stefan Deßloch, Theo Härder, Nelson Mendonça Mattos, Bernhard Mitschang, Joachim Thomas: Advanced Data Processing in KRISYS: Modeling Concepts, Implementation Techniques, and Client/Server Issues. VLDB J. 7(2): 79-95(1998)
  6. Subbu N. Subramanian, Shivakumar Venkataraman: Cost-Based Optimization of Decision Support Queries Using Transient Views. SIGMOD Conference 1998: 319-330
  7. Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998: 34-43
  8. Ramana Yerneni, Yannis Papakonstantinou, Serge Abiteboul, Hector Garcia-Molina: Fusion Queries over Internet Databases. EDBT 1998: 57-71
  9. Laura M. Haas, Donald Kossmann, Edward L. Wimmers, Jun Yang: Optimizing Queries Across Diverse Data Sources. VLDB 1997: 276-285
  10. 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
  11. David E. Simmen, Eugene J. Shekita, Timothy Malkemus: Fundamental Techniques for Order Optimization. SIGMOD Conference 1996: 57-67
  12. Vassilis Christophides, Sophie Cluet, Guido Moerkotte: Evaluating Queries with Generalized Path Expressions. SIGMOD Conference 1996: 413-422
  13. Mitch Cherniack, Stanley B. Zdonik: Rule Languages and Internal Algebras for Rule-Based Optimizers. SIGMOD Conference 1996: 401-412
  14. Dave D. Straube, M. Tamer Özsu: Query Optimization and Execution Plan Generation in Object-Oriented Data Management Systems. IEEE Trans. Knowl. Data Eng. 7(2): 210-227(1995)
  15. Fatma Ozcan, Sena Nural, Pinar Koksal, Mehmet Altinel, Asuman Dogac: A Region Based Query Optimizer Through Cascades Query Optimizer Framework. IEEE Data Eng. Bull. 18(3): 30-40(1995)
  16. Michael Steinbrunn, Klaus Peithner, Guido Moerkotte, Alfons Kemper: Bypassing Joins in Disjunctive Queries. VLDB 1995: 228-238
  17. Georges Gardarin, Jean-Robert Gruser, Zhao-Hui Tang: A Cost Model for Clustered Object-Oriented Databases. VLDB 1995: 323-334
  18. Surajit Chaudhuri, Umeshwar Dayal, Tak W. Yan: Join Queries with External Text Sources: Execution and Optimization Techniques. SIGMOD Conference 1995: 410-422
  19. Dinesh Das, Don S. Batory: Praire: A Rule Specification Framework for Query Optimizers. ICDE 1995: 201-210
  20. Joachim Thomas, T. Gerbes, Theo Härder, Bernhard Mitschang: Implementing Dynamic Code Assembly for Client-Based Query Processing. DASFAA 1995: 264-272
  21. M. Tamer Özsu, Adriana Muñoz, Duane Szafron: An Extensible Query Optimizer for an Objectbase Management System. CIKM 1995: 188-196
  22. Ralf Hartmut Güting: An Introduction to Spatial Database Systems. VLDB J. 3(4): 357-399(1994)
  23. Wei Sun, Clement T. Yu: Semantic Query Optimization for Tree and Chain Queries. IEEE Trans. Knowl. Data Eng. 6(1): 136-151(1994)
  24. Alfons Kemper, Guido Moerkotte, Klaus Peithner, Michael Steinbrunn: Optimizing Disjunctive Queries with Expensive Predicates. SIGMOD Conference 1994: 336-347
  25. Hamid Pirahesh, Bernhard Mitschang, Norbert Südkamp, Bruce G. Lindsay: Composite-Object Views in Relational DBMS: An Implementation Perspective. EDBT 1994: 23-30
  26. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  27. Richard H. Wolniewicz, Goetz Graefe: Algebraic Optimization of Computations over Scientific Databases. VLDB 1993: 13-24
  28. Joachim Thomas, Stefan Deßloch: A Plan-Operator Concept for Client-Based Knowledge Progressing. VLDB 1993: 555-566
  29. Gail Mitchell, Umeshwar Dayal, Stanley B. Zdonik: Control of an Extensible Query Optimizer: A Planning-Based Approach. VLDB 1993: 517-528
  30. Ralf Hartmut Güting: Second-Order Signature: A Tool for Specifying Data Models, Query Processing, and Optimization. SIGMOD Conference 1993: 277-286
  31. Magdi M. A. Morsi, Shamkant B. Navathe: Application and System Prototyping Via an Extensible Object-Oriented Environment. ER 1993: 24-33
  32. Ludger Becker, Ralf Hartmut Güting: Rule-Based Optimization and Query Processing in an Extensible Geometric Database System. ACM Trans. Database Syst. 17(2): 247-303(1992)
  33. Tobin J. Lehman, Eugene J. Shekita, Luis-Felipe Cabrera: An Evaluation of Starburst's Memory Resident Storage Component. IEEE Trans. Knowl. Data Eng. 4(6): 555-566(1992)
  34. Peter M. G. Apers, Carel A. van den Berg, Jan Flokstra, Paul W. P. J. Grefen, Martin L. Kersten, Annita N. Wilschut: PRISMA/DB: A Parallel Main Memory Relational DBMS. IEEE Trans. Knowl. Data Eng. 4(6): 541-554(1992)
  35. Vibby Gottemukkala, Tobin J. Lehman: Locking and Latching in a Memory-Resident Database System. VLDB 1992: 533-544
  36. Guy M. Lohman, Bruce G. Lindsay, Hamid Pirahesh, K. Bernhard Schiefer: Extensions to Starburst: Objects, Types, Functions, and Rules. Commun. ACM 34(10): 94-109(1991)
  37. Ulf Schreier, Hamid Pirahesh, Rakesh Agrawal, C. Mohan: Alert: An Architecture for Transforming a Passive DBMS into an Active DBMS. VLDB 1991: 469-478
  38. Walid G. Aref, Hanan Samet: Optimization for Spatial Query Processing. VLDB 1991: 81-90
  39. Jurgen Annevelink: Database Programming Languages: A Functional Approach. SIGMOD Conference 1991: 318-327
  40. Beat Wüthrich: Semantic Improvement of Deductive Databases. MFDBS 1991: 216-229
  41. Joel L. Wolf, Balakrishna R. Iyer, Krishna R. Pattipati, John Turek: Optimal Buffer Partitioning for the Nested Block Join Algorithm. ICDE 1991: 510-519
  42. Gerald Kiernan, Christophe de Maindreville: Compiling a Rule Database Program into a C/SQL Application. ICDE 1991: 388-395
  43. Béatrice Finance, Georges Gardarin: A Rule-Based Query Rewriter in an Extensible DBMS. ICDE 1991: 248-256
  44. Joel E. Richardson, Peter M. Schwarz: MDM: An Object-Oriented Data Model. DBPL 1991: 86-95
  45. Ryohei Nakano: Translation with Optimization from Relational Calculus to Relational Algebra Having Aggregate Functions. ACM Trans. Database Syst. 15(4): 518-557(1990)
  46. Laura M. Haas, Walter Chang, Guy M. Lohman, John McPherson, Paul F. Wilms, George Lapis, Bruce G. Lindsay, Hamid Pirahesh, Michael J. Carey, Eugene J. Shekita: Starburst Mid-Flight: As the Dust Clears. IEEE Trans. Knowl. Data Eng. 2(1): 143-160(1990)
  47. Donovan A. Schneider, David J. DeWitt: Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines. VLDB 1990: 469-480
  48. Stefano Ceri, Jennifer Widom: Deriving Production Rules for Constraint Maintainance. VLDB 1990: 566-577
  49. Michael J. Carey, Eugene J. Shekita, George Lapis, Bruce G. Lindsay, John McPherson: An Incremental Join Attachment for Starburst. VLDB 1990: 662-673
  50. Jennifer Widom, Sheldon J. Finkelstein: Set-Oriented Production Rules in Relational Database Systems. SIGMOD Conference 1990: 259-270
  51. Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic is Relevant. SIGMOD Conference 1990: 247-258
  52. Gerald Kiernan, Christophe de Maindreville, Eric Simon: Making Deductive Databases a Practical Technology: A Step Forward. SIGMOD Conference 1990: 237-246
  53. Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic Conditions. PODS 1990: 314-330
  54. Marc H. Scholl, Hans-Jörg Schek: A Relational Object Model. ICDT 1990: 89-105
  55. José A. Blakeley, Nancy L. Martin: Join Index, Materialized View, and Hybrid-Hash Join: A Performance Analysis. ICDE 1990: 256-263
  56. Tobin J. Lehman, Bruce G. Lindsay: The Starburst Long Field Manager. VLDB 1989: 375-383

Copyright © Mon Nov 2 21:11:37 2009 by Michael Ley (ley@uni-trier.de)