Logical, Internal, and Physical Reference Behavior in CODASYL Database Systems.

@article{DBLP:journals/tods/EffelsbergL84,
  author    = {Wolfgang Effelsberg and
               Mary E. S. Loomis},
  title     = {Logical, Internal, and Physical Reference Behavior in CODASYL
               Database Systems},
  journal   = {ACM Trans. Database Syst.},
  volume    = {9},
  number    = {2},
  year      = {1984},
  pages     = {187-213},
  ee        = {http://doi.acm.org/10.1145/329.331, db/journals/tods/EffelsbergL84.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This work investigates one aspect of the performance of CODASYL database systems: the data reference behavior. We introduce a model of database traversals at three levels: the logical, internal, and physical levels. The mapping between the logical and internal levels is defined by the internal schema, whereas the mapping between the internal and the physical levels depends on cluster properties of the database. Our model explains the physical reference behavior for a given sequence of DML statements at the logical level.

Software has been implemented to monitor references in two selected CODASYL DBMS applications. In a series of experiments the physical reference behavior was observed for varying internal schemas and cluster properties of the database. The measurements were limited to retrieval transactions, so that a variety of queries could be analyzed for the same well-known state of the database. Also, all databases were relatively small in order to allow fast reloading with varying internal schema parameters. In all cases, the database transactions showed less locality of reference than do programs under virtual memory operating systems; some databases showed no locality at all. No evidence of physical sequentiality was found. This suggests that standard page replacement strategies are not optimal for CODASYL database buffer management; instead, replacement decisions in a database buffer should be based on specific knowledge available from higher system layers.

Copyright © 1984 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]

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

[2]

Richard S. Brice, Stephen W. Sherman: An Extension of the Performance of a Database Manager in a Virtual Memory System Using Partially Locked Virtual Buffers. ACM Trans. Database Syst. 2(2): 196-207(1977) BibTeX

[3]

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

[4]

...

[5]

...

[6]

...

[7]

Peter J. Denning: The Working Set Model for Program Behaviour. Commun. ACM 11(5): 323-333(1968) BibTeX

[8]

Peter J. Denning, Stuart C. Schwartz: Properties of the Working Set Model. Commun. ACM 15(3): 191-198(1972) BibTeX

[9]

...

[10]

...

[11]

...

[12]

Wolfgang Effelsberg, Theo Härder: Principles of Database Buffer Management. ACM Trans. Database Syst. 9(4): 560-595(1984) BibTeX

[13]

...

[14]

Jim Gray, Paul R. McJones, Mike W. Blasgen, Bruce G. Lindsay, Raymond A. Lorie, Thomas G. Price, Gianfranco R. Putzolu, Irving L. Traiger: The Recovery Manager of the System R Database Manager. ACM Comput. Surv. 13(2): 223-243(1981) BibTeX

[15]

Paula B. Hawthorn, Michael Stonebraker: Performance Analysis of a Relational Data Base Management System. SIGMOD Conference 1979: 1-12 BibTeX

[16]

...

[17]

John P. Kearns, Samuel DeFazio: Locality of Reference in Hierarchical Database Systems. IEEE Trans. Software Eng. 9(2): 128-134(1983) BibTeX

[18]

Andreas Reuter, Horst Kinzinger: Automatic Design of the Internal Schema for a CODASYL Database System. IEEE Trans. Software Eng. 10(4): 358-375(1984) BibTeX

[19]

Tomás Lang, Christopher Wood, Eduardo B. Fernández: Database Buffer Paging in Virtual Storage Systems. ACM Trans. Database Syst. 2(4): 339-351(1977) BibTeX

[20]

Mary E. S. Loomis, Frank W. Allen: Paging Behaviour and Performance Optimization in a Codasyl DBMS. ICOD 1980: 119-134 BibTeX

[21]

...

[22]

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

[23]

...

[24]

...

[25]

...

[26]

...

[27]

Giovanni Maria Sacco, Mario Schkolnick: A Mechanism for Managing the Buffer Pool in a Relational Database System Using the Hot Set Model. VLDB 1982: 257-262 BibTeX

[28-1]

Michael E. Senko, Edward B. Altman, Morton M. Astrahan, P. L. Fehder: Data Structures and Accessing in Data-Base Systems. I: Evolution of Information Systems. IBM Systems Journal 12(1): 30-44(1973) BibTeX

[28-2]

Michael E. Senko, Edward B. Altman, Morton M. Astrahan, P. L. Fehder: Data Structures and Accessing in Data-Base Systems. II: Information Organization. IBM Systems Journal 12(1): 45-63(1973) BibTeX

[28-3]

Michael E. Senko, Edward B. Altman, Morton M. Astrahan, P. L. Fehder: Data Structures and Accessing in Data-Base Systems. III: Data Representations and the Data Independent Accessing Model. IBM Systems Journal 12(1): 64-93(1973) BibTeX

[29]

Stephen W. Sherman, Richard S. Brice: Performance of a Database Manager in a Virtual Memory System. ACM Trans. Database Syst. 1(4): 317-343(1976) BibTeX

[30]

Alan Jay Smith: Sequentiality and Prefetching in Database Systems. ACM Trans. Database Syst. 3(3): 223-247(1978) BibTeX

[31]

...

[32]

Michael Stonebraker: Operating System Support for Database Management. Commun. ACM 24(7): 412-418(1981) BibTeX

[33]

...

[34]

...

[35]

William G. Tuel Jr.: An Analysis of Buffer Paging in Virtual Storage Systems. IBM J. Res. Dev. 20(5): 518-520(1976) BibTeX

[36]

...

Referenced by

1. Asit Dan, Philip S. Yu, Jen-Yao Chung: Characterization of Database Access Pattern for Analytic Prediction of Buffer Hit Probability. VLDB J. 4(1): 127-154(1995)
2. Philip S. Yu, Douglas W. Cornell: Buffer Management Based on Return on Consumption in a Multi-Query Environment. VLDB J. 2(1): 1-37(1993)
3. Asit Dan, Philip S. Yu, Jen-Yao Chung: Database Access Characterization for Buffer Hit Prediction. ICDE 1993: 134-143
4. Douglas W. Cornell, Philip S. Yu: Integration of Buffer Management and Query Optimization in Relational Database Environment. VLDB 1989: 247-255
5. Salvatore Orlando, V. Perri, S. Scrivano, Witold Staniszkis: Database Analyzer and Predictor - An Overview. ICDE 1989: 625-634
6. Giovanni Maria Sacco, Mario Schkolnick: Buffer Management in Relational Database Systems. ACM Trans. Database Syst. 11(4): 473-498(1986)