A Framework for Automating Physical Database Design.

Steve Rozen, Dennis Shasha: A Framework for Automating Physical Database Design. VLDB 1991: 401-411

@inproceedings{DBLP:conf/vldb/RozenS91,
  author    = {Steve Rozen and
               Dennis Shasha},
  editor    = {Guy M. Lohman and
               Am\'{\i}lcar Sernadas and
               Rafael Camps},
  title     = {A Framework for Automating Physical Database Design},
  booktitle = {17th International Conference on Very Large Data Bases, September
               3-6, 1991, Barcelona, Catalonia, Spain, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1991},
  isbn      = {1-55860-150-3},
  pages     = {401-411},
  ee        = {db/conf/vldb/RozenS91.html},
  crossref  = {DBLP:conf/vldb/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We propose a two-phase algorithm for physical database design. In phase one the algorithm, for each logical query, uses rules to determine characteristics of a physical design (such as indexes) that would be beneficial tothe query, and selects a physical design that yields a low cost estimate for that query. In phase two we use a notion of compromise between physical database designs. Starting from the physical designs selected in phase one, the algorithm looks for a compromise physical design that minimizes the queries' aggregate frequency- weighted cost. This method is envisioned as a cornerstone in the efficient implementation of aTuring-complete, very-high-level programming language for database applications, but it is also suitable for more conventional relational and -1NF database management systems.

Copyright © 1991 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

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...

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

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

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

Guy M. Lohman, Amílcar Sernadas, Rafael Camps (Eds.): 17th International Conference on Very Large Data Bases, September 3-6, 1991, Barcelona, Catalonia, Spain, Proceedings. Morgan Kaufmann 1991, ISBN 1-55860-150-3

References

[1]: 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)
[2]: François Bancilhon: Object-Oriented Database Systems. PODS 1988: 152-162
[3]: Elena Barcucci, Renzo Pinzani, Renzo Sprugnoli: Optimal Selection of Secondary Indexes. IEEE Trans. Software Eng. 16(1): 32-38(1990)
[4]: Douglas Comer: The Difficulty of Optimum Index Selection. ACM Trans. Database Syst. 3(4): 440-445(1978)
[5]: Douglas W. Cornell, Philip S. Yu: An Effective Approach to Vertical Partitioning for Physical Design of Relational Databases. IEEE Trans. Software Eng. 16(2): 248-258(1990)
[6]: ...
[7]: Klaus R. Dittrich: Object-Oriented Database Systems: The Notion and the Issue. OODBS 1986: 2-4
[8]: Sheldon J. Finkelstein, Mario Schkolnick, Paolo Tiberio: Physical Database Design for Relational Databases. ACM Trans. Database Syst. 13(1): 91-128(1988)
[9]: Johann Christoph Freytag: A Rule-Based View of Query Optimization. SIGMOD Conference 1987: 173-180
[10]: Johann Christoph Freytag, Nathan Goodman: On the Translation of Relational Queries into Iterative Programs. ACM Trans. Database Syst. 14(1): 1-27(1989)
[11]: Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172
[12]: Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
[13]: Alfons Kemper, Peter C. Lockemann, Mechtild Wallrath: An Object-Oriented Database System for Engineering Applications. SIGMOD Conference 1987: 299-310
[14]: 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
[15]: Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27
[16]: Won Kim, David S. Reiner, Don S. Batory (Eds.): Query Processing in Database Systems. Springer 1985, ISBN 3-540-13831-5
Contents
[17]: ...
[18]: ...
[19]: Steve Rozen, Dennis Shasha: Using a Relational System On Wall Street: The Good, The Bad, The Ugly, And The Ideal. Commun. ACM 32(8): 988-994(1989)
[20]: Hans-Jörg Schek, Marc H. Scholl: The relational model with relation-valued attributes. Inf. Syst. 11(2): 137-147(1986)
[21]: Joachim W. Schmidt: Some High Level Language Constructs for Data of Type Relation. ACM Trans. Database Syst. 2(3): 247-261(1977)
[22]: ...
[23]: 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