ACM SIGMOD Anthology TODS dblp.uni-trier.de

Physical Database Design for Relational Databases.

Sheldon J. Finkelstein, Mario Schkolnick, Paolo Tiberio: Physical Database Design for Relational Databases. ACM Trans. Database Syst. 13(1): 91-128(1988)
@article{DBLP:journals/tods/FinkelsteinST88,
  author    = {Sheldon J. Finkelstein and
               Mario Schkolnick and
               Paolo Tiberio},
  title     = {Physical Database Design for Relational Databases},
  journal   = {ACM Trans. Database Syst.},
  volume    = {13},
  number    = {1},
  year      = {1988},
  pages     = {91-128},
  ee        = {http://doi.acm.org/10.1145/42201.42205, db/journals/tods/FinkelsteinST88.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper describes the concepts used in the implementation of DBDSGN, an experimental physical design tool for relational databases developed at the IBM San Jose Research Laboratory. Given a workload for System R (consisting of a set of SQL statements and their execution frequencies), DBDSGN suggests physical configurations for efficient performance. Each configuration consists of a set of indices and an ordering for each table. Workload statements are evaluated only for atomic configurations of indices, which have only one index per table. Costs for any configuration can be obtained from those of the atomic configurations. DBDSGN uses information supplied by the System R optimizer both to determine which columns might be worth indexing and to obtain estimates of the cost of executing statements in different configurations. The tool finds efficient solutions to the index-selection problem; if we assume the cost estimates supplied by the optimizer are the actual execution costs, it finds the optimal solution. Optionally, heuristics can be used to reduce execution time. The approach taken by DBDSGN in solving the index-selection problem for multiple-table statements significantly reduces the complexity of the problem. DBDSGN's principles were used in the Relational Design Tool (RDT), an IBM product based on DBDSGN, which performs design for SQL/DS, a relational system based on System R. System R actually uses DBDSGN's suggested solutions as the tool expects because cost estimates and other necessary information can be obtained from System R using a new SQL statement, the EXPLAIN statement. This illustrates how a system can export a model of its internal assumptions and behavior so that other systems (such as tools) can share this model.

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

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[1]
Henry D. Anderson, P. Bruce Berra: Minimum Cost Selection of Secondary Indexes for Formatted Files. ACM Trans. Database Syst. 2(1): 68-90(1977) BibTeX
[2]
Morton M. Astrahan, Mario Schkolnick, Won Kim: Performance of the System R Access Path Selection Mechanism. IFIP Congress 1980: 487-491 BibTeX
[3]
Morton M. Astrahan, Mario Schkolnick, Kyu-Young Whang: Approximating the number of unique values of an attribute without sorting. Inf. Syst. 12(1): 11-15(1987) BibTeX
[4]
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) BibTeX
[5]
...
[6]
R. Bonnano, Dario Maio, Paolo Tiberio: An Approximation Algorithm for Secondary Index Selection in Relational Database Physical Design. Comput. J. 28(4): 398-405(1985) BibTeX
[7]
...
[8]
Alfonso F. Cardenas: Analysis and Performance of Inverted Data Base Structures. Commun. ACM 18(5): 253-263(1975) BibTeX
[9]
...
[10]
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) BibTeX
[11]
Donald D. Chamberlin, Morton M. Astrahan, Mike W. Blasgen, Jim Gray, W. Frank King III, Bruce G. Lindsay, Raymond A. Lorie, James W. Mehl, Thomas G. Price, Gianfranco R. Putzolu, Patricia G. Selinger, Mario Schkolnick, Donald R. Slutz, Irving L. Traiger, Bradford W. Wade, Robert A. Yost: A History and Evaluation of System R. Commun. ACM 24(10): 632-646(1981) BibTeX
[12]
Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984) BibTeX
[13]
Douglas Comer: The Difficulty of Optimum Index Selection. ACM Trans. Database Syst. 3(4): 440-445(1978) BibTeX
[14]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
[15]
Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33 BibTeX
[16]
Michael Hammer, Arvola Chan: Index Selection in a Self-Adaptive Data Base Management System. SIGMOD Conference 1976: 1-8 BibTeX
[17]
Michael Hatzopoulos, John G. Kollias: On the Selection of a Reduced Set of Indexes. Comput. J. 28(4): 406-408(1985) BibTeX
[18]
Paula B. Hawthorn, Michael Stonebraker: Performance Analysis of a Relational Data Base Management System. SIGMOD Conference 1979: 1-12 BibTeX
[19]
...
[20]
...
[21]
...
[22]
...
[23]
Maggie Y. L. Ip, Lawrence V. Saxton, Vijay V. Raghavan: On the Selection of an Optimal Set of Indexes. IEEE Trans. Software Eng. 9(2): 135-143(1983) BibTeX
[24]
Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) BibTeX
[25]
...
[26]
John G. Kollias: A heuristic approach for determining the optimal degree of file inversion. Inf. Syst. 4(4): 307-318(1979) BibTeX
[27]
Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Local Queries. SIGMOD Conference 1986: 84-95 BibTeX
[28]
Anne Putkonen: On the selection of the access path in inverted database organization. Inf. Syst. 4(1): 219-225(1979) BibTeX
[29]
...
[30]
Mario Schkolnick: The Optimal Selection of Secondary Indices for Files. Inf. Syst. 1(4): 141-146(1975) BibTeX
[31]
Mario Schkolnick: A Survey of Physical Database Design Methodology and Techniques. VLDB 1978: 474-487 BibTeX
[32]
...
[33]
Mario Schkolnick, Paolo Tiberio: Estimating the Cost of Updates in a Relational Database. ACM Trans. Database Syst. 10(2): 163-179(1985) BibTeX
[34]
...
[35]
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 BibTeX
[36]
...
[37]
Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX
[38]
...
[39]
Kyu-Young Whang, Gio Wiederhold, Daniel Sagalowicz: Separability - An Approach to Physical Database Design. IEEE Trans. Computers 33(3): 209-222(1984) BibTeX
[40]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX
[41]
...
[42]
Karel Youssefi, Eugene Wong: Query Processing in a Relational Database Management System. VLDB 1979: 409-417 BibTeX

Referenced by

  1. Surajit Chaudhuri: Review - Physical Database Design for Relational Databases. ACM SIGMOD Digital Review 2: (2000)
  2. Moses Charikar, Surajit Chaudhuri, Rajeev Motwani, Vivek R. Narasayya: Towards Estimation Error Guarantees for Distinct Values. PODS 2000: 268-279
  3. Surajit Chaudhuri, Vivek R. Narasayya: Index Merging. ICDE 1999: 296-303
  4. Surajit Chaudhuri, Vivek R. Narasayya: AutoAdmin 'What-if' Index Analysis Utility. SIGMOD Conference 1998: 367-378
  5. Surajit Chaudhuri, Rajeev Motwani, Vivek R. Narasayya: Random Sampling for Histogram Construction: How much is enough? SIGMOD Conference 1998: 436-447
  6. Jong-Hak Lee, Young-Koo Lee, Kyu-Young Whang, Il-Yeol Song: A Region Splitting Strategy for Physical Database Design of Multidimensional File Organizations. VLDB 1997: 416-425
  7. Surajit Chaudhuri, Vivek R. Narasayya: An Efficient Cost-Driven Index Selection Tool for Microsoft SQL Server. VLDB 1997: 146-155
  8. Wilburt Labio, Dallan Quass, Brad Adelberg: Physical Database Design for Data Warehouses. ICDE 1997: 277-288
  9. John Mylopoulos, Vinay K. Chaudhri, Dimitris Plexousakis, Adel Shrufi, Thodoros Topaloglou: Building Knowledge Base Management Systems. VLDB J. 5(4): 238-263(1996)
  10. Alberto Caprara, Matteo Fischetti, Dario Maio: Exact and Approximate Algorithms for the Index Selection Problem in Physical Database Design. IEEE Trans. Knowl. Data Eng. 7(6): 955-967(1995)
  11. Praveen Seshadri, Arun N. Swami: Generalized Partial Indexes. ICDE 1995: 420-427
  12. Eric Hughes, Marianne Winslett: The Index Suggestion Problem for Object Database Applications. CIKM 1995: 50-57
  13. Elisa Bertino: Index Configuration in Object-Oriented Databases. VLDB J. 3(3): 355-399(1994)
  14. Sunil Choenni, Elisa Bertino, Henk M. Blanken, Thiel Chang: On the Selection of Optimal Index Configuration in OO Databases. ICDE 1994: 526-537
  15. Doron Rotem, Gerhard A. Schloss, Arie Segev: Data Allocation for Multi-Disk Databases. IEEE Trans. Knowl. Data Eng. 5(5): 882-887(1993)
  16. Michael Siegel, Edward Sciore, Sharon C. Salveter: A Method for Automatic Rule Derivation to Support Semantic Query Optimization. ACM Trans. Database Syst. 17(4): 563-600(1992)
  17. Pai-Cheng Chu: Estimating Block Selectivities for Physical Database Design. IEEE Trans. Knowl. Data Eng. 4(1): 89-98(1992)
  18. Timos K. Sellis, Chih-Chen Lin: A Geometric Approach to Indexing Large Rule Bases. EDBT 1992: 405-420
  19. Martin R. Frank, Edward Omiecinski, Shamkant B. Navathe: Adaptive and Automated Index Selection in RDBMS. EDBT 1992: 277-292
  20. Steve Rozen, Dennis Shasha: A Framework for Automating Physical Database Design. VLDB 1991: 401-411
  21. Chris Clifton, Hector Garcia-Molina: Indexing in a Hypertext Database. VLDB 1990: 36-49
  22. Michael V. Mannino, Paicheng Chu, Thomas Sager: Statistical Profile Estimation in Database Systems. ACM Comput. Surv. 20(3): 191-221(1988)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:04 2008