Modeling the Storage Architectures of Commercial Database Systems.

@article{DBLP:journals/tods/Batory85,
  author    = {Don S. Batory},
  title     = {Modeling the Storage Architectures of Commercial Database Systems},
  journal   = {ACM Trans. Database Syst.},
  volume    = {10},
  number    = {4},
  year      = {1985},
  pages     = {463-528},
  ee        = {http://doi.acm.org/10.1145/4879.5392, db/journals/tods/Batory85.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Modeling the storage structures of a DBMS is a prerequisite to understanding and optimizing database performance. Previously, such modeling was very difficult because the fundamental role of conceptual-to-internal mappings in DBMS implementations went unrecognized.

In this paper we present a model of physical databases, called the transformation model, that makes conceptual-to-internal mappings explicit. By exposing such mappings, we show that it is possible to model the storage architectures (i.e., the storage structures and mappings) of many commercial DBMSs in a precise, systematic, and comprehendible way. Models of the INQUIRE, ADABAS, and SYSTEM 2000 storage architectures are presented as examples of the model's utility.

We believe the transformation model helps bridge the gap between physical database theory and practice. It also reveals the possibility of a technology to automate the development of physical database software.

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

• 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/An3-1 or /cdrom

• 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/aDVD2 or /dvd

References

[1]

Houtan Aghili, Dennis G. Severance: A Practical Guide to the Design of Differential Files for Recovery of On-Line Databases. ACM Trans. Database Syst. 7(4): 540-565(1982) BibTeX

[2]

...

[3]

A. James Baroody Jr., David J. DeWitt: An Object-Oriented Approach to Database System Implementation. ACM Trans. Database Syst. 6(4): 576-601(1981) BibTeX

[4]

Don S. Batory: On Searching Transposed Files. ACM Trans. Database Syst. 4(4): 531-544(1979) BibTeX

[5]

Don S. Batory: Optimal File Designs and Reorganization Points. ACM Trans. Database Syst. 7(1): 60-81(1982) BibTeX

[6]

Don S. Batory: Conceptual-To-Internal Mappings in Commercial Database Systems. PODS 1984: 70-78 BibTeX

[7]

...

[8]

...

[9]

...

[10]

Don S. Batory, C. C. Gotlieb: A Unifying Model of Physical Databases. ACM Trans. Database Syst. 7(4): 509-539(1982) BibTeX

[11]

Don S. Batory, Won Kim: Modeling Concepts for VLSI CAD Objects. ACM Trans. Database Syst. 10(3): 322-346(1985) BibTeX

[12]

Elias Berelian, Keki B. Irani: Evaluation and Optimization. VLDB 1977: 545-555 BibTeX

[13]

...

[14]

...

[15]

...

[16]

...

[17]

...

[18]

Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
BibTeX

[19]

Peter P. Chen: The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1(1): 9-36(1976) BibTeX

[20]

...

[21]

Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX

[22]

...

[23]

...

[24]

...

[25]

...

[26]

Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344(1979) BibTeX

[27]

...

[28]

...

[29]

CODASYL: Stored-data description and data translation: a model and language. Inf. Syst. 2(3): 95-148(1977) BibTeX

[30]

Thomas J. Gambino, Rob Gerritsen: A Data Base Design Decision Support System. VLDB 1977: 534-544 BibTeX

[31]

...

[32]

...

[33]

C. C. Gotlieb: Some Large Questions about Very Large Data Bases. VLDB 1980: 3-7 BibTeX

[34]

Jim Gray: Practical Problems in Data Management - A Position Paper. SIGMOD Conference 1983: 3 BibTeX

[35]

John V. Guttag: Abstract Data Type and the Development of Data Structures. Commun. ACM 20(6): 396-404(1977) BibTeX

[36]

Antonin Guttman, Michael Stonebraker: Using a Relational Database Management System for Computer Aided Design Data. IEEE Database Eng. Bull. 5(2): 21-28(1982) BibTeX

[37]

...

[38]

Roger L. Haskin, Raymond A. Lorie: On Extending the Functions of a Relational Database System. SIGMOD Conference 1982: 207-212 BibTeX

[39]

Gerald Held, Michael Stonebraker: B-trees Re-examined. Commun. ACM 21(2): 139-143(1978) BibTeX

[40]

...

[41]

...

[42]

...

[43]

...

[44]

...

[45]

...

[46]

...

[47]

Richard P. King, Henry F. Korth, Barry E. Willner: Design of a Document Filing and Retrieval Service. Databases for Business and Office Applications 1983: 96-101 BibTeX

[48]

Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX

[49]

...

[50]

...

[51]

Per-Åke Larson: Dynamic Hashing. BIT 18(2): 184-201(1978) BibTeX

[52]

Abraham Lempel: Cryptology in Transition. ACM Comput. Surv. 11(4): 285-303(1979) BibTeX

[53]

...

[54]

Salvatore T. March: Techniques for Structuring Database Records. ACM Comput. Surv. 15(1): 45-79(1983) BibTeX

[55]

Salvatore T. March, Dennis G. Severance: The Determination of Efficient Record Segmentations and Blocking Factors for Shared Data Files. ACM Trans. Database Syst. 2(3): 279-296(1977) BibTeX

[56]

Salvatore T. March, Dennis G. Severance, Michael Wilens: Frame Memory: A Storage Architecture to Support Rapid Design and Implementation of Efficient Databases. ACM Trans. Database Syst. 6(3): 441-463(1981) BibTeX

[57]

...

[58]

Michael F. Mitoma, Keki B. Irani: Automatic Data Base Schema Design and Optimization. VLDB 1975: 286-321 BibTeX

[59]

Toshiyuki Nakamura, Tetsuo Mizoguchi: An Analysis of Storage Utilization Factor in Block Split Data Structuring Scheme. VLDB 1978: 489-495 BibTeX

[60]

...

[61]

...

[62]

Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX

[63]

James Ong, Dennis Fogg, Michael Stonebraker: Implementation of Data Abstraction in the Relational Database System Ingres. SIGMOD Record 14(1): 1-14(1984) BibTeX

[64]

Dennis Ritchie, Ken Thompson: The UNIX Time-Sharing System. Commun. ACM 17(7): 365-375(1974) BibTeX

[65]

Lawrence A. Rowe, Kurt A. Shoens: Data Abstractions, Views and Updates in RIGEL. SIGMOD Conference 1979: 71-81 BibTeX

[66]

Michel Scholl: New File Organizations Based on Dynamic Hashing. ACM Trans. Database Syst. 6(1): 194-211(1981) BibTeX

[67]

...

[68]

...

[69]

Dennis G. Severance, Guy M. Lohman: Differential Files: Their Application to the Maintenance of Large Databases. ACM Trans. Database Syst. 1(3): 256-267(1976) BibTeX

[70]

David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981) BibTeX

[71]

...

[72]

...

[73]

...

[74]

...

[75]

...

[76]

Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX

[77]

Michael Stonebraker, W. Bradley Rubenstein, Antonin Guttman: Application of Abstract Data Types and Abstract Indices to CAD Data Bases. Engineering Design Applications 1983: 107-113 BibTeX

[78]

Per Svensson: On Search Performance for Conjunctive Queries in Compressed, Fully Transposed Ordered Files. VLDB 1979: 155-163 BibTeX

[79]

...

[80]

...

[81]

Dennis Tsichritzis, Anthony C. Klug: The ANSI/X3/SPARC DBMS Framework Report of the Study Group on Dabatase Management Systems. Inf. Syst. 3(3): 173-191(1978) BibTeX

[82]

Dennis Tsichritzis, Stavros Christodoulakis: Message Files. ACM Trans. Inf. Syst. 1(1): 88-98(1983) BibTeX

[83]

M. J. Turner, R. Hammond, P. Cotton: A DBMS for Large Statistical Databases. VLDB 1979: 319-327 BibTeX

[84]

...

[85]

...

[86]

...

[87]

...

[88]

S. Bing Yao: An Attribute Based Model for Database Access Cost Analysis. ACM Trans. Database Syst. 2(1): 45-67(1977) BibTeX

[89]

Jacob Ziv, Abraham Lempel: A Universal Algorithm for Sequential Data Compression. IEEE Transactions on Information Theory 23(3): 337-343(1977) BibTeX

Referenced by

1. Elisa Bertino: Index Configuration in Object-Oriented Databases. VLDB J. 3(3): 355-399(1994)
2. John Sieg Jr., Edward Sciore: Extended Relations. ICDE 1990: 488-494
3. José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. ACM Trans. Database Syst. 14(3): 369-400(1989)
4. Don S. Batory, T. Y. Leung, T. E. Wise: Implementation Concepts for an Extensible Data Model and Data Language. ACM Trans. Database Syst. 13(3): 231-262(1988)
5. Don S. Batory: Concepts for a Database System Compiler. PODS 1988: 184-192
6. Randy H. Katz, Ellis E. Chang: Managing Change in a Computer-Aided Design Database. VLDB 1987: 455-462
7. Setrag Khoshafian, Patrick Valduriez: Sharing, Persistence, and Object-Orientation: A Database Perspective. DBPL 1987: 221-240
8. Don S. Batory, Michael V. Mannino: Panel on Extensible Database Systems. SIGMOD Conference 1986: 187-190
9. George P. Copeland, Setrag Khoshafian: A Decomposition Storage Model. SIGMOD Conference 1985: 268-279
10. Don S. Batory: Conceptual-To-Internal Mappings in Commercial Database Systems. PODS 1984: 70-78