LOGICAL, INTERNAL AND PHYSICAL REFERENCE BEHAVIOR INCODASYL DATABASE SYSTEMS
Original Publication Date: 1984-May-08
Included in the Prior Art Database: 2007-Mar-30
Software Patent Institute
Effelsberg, Wolfgang: AUTHOR [+3]
RJ 4291 (46989) 5/8/84 Computer Science Research Report
RJ 4291 (46989) 5/8/84 Computer Science
LOGICAL, INTJ3NAL AMl PKYSICAL RJZERENCE BEHAVIOR
IN CODASYL DATMASE SYSTEMS
Wolf gang Eff eIsberg
' IBM Research Laboratory San J w , California 95 193
Mary E.S. Loomis
D. Appfetoa Company Manhattan Beach, Wonria 90266
! UMmD DLStTPIBUTlON NOTICE
- - --- Research DhrWon
- 5 Yotictown HeigMs, New Yor)s a San Jose, CdMrnb a Zurich, Swittertand
Copies may be reduested from:
IBM Thomas .L Watson Research Center Oistribution Services
Post Offia Box 21 8
Yorktown Heights, New York 10598
rW 4291 (46989) 5/8/84
LOGICAL, INTERNAL AND PHYSlCAL REFERENCE BEHAVIOR IN CODASYL OATABASE SYSTEMS
IBM Research Laboratory San Jose, California 95193
Mary E .
S . Loomis
D. Appleton Company
Manhattan Beach, California 90266
This work investigates one aspect of performance of CODASYL database sys- tems: the data reference behavior. We introduce a model of databasetrav- ersals at three levels: the logical, internal and physical level*. The mapping between the logical and internal level is defined by the internal
schema, whereas the mapping between the internal and the physical level depends on cluster properties of the database. Our model explains the phy- sical reference behavior for a given sequence of DML statements at the logical level.
Software has been implemented to monitor references in two selected CQDA- Sn
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 limi.ted 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 pxograms 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 ltnowledge available from high- er system layers.
This resegrch was done while the authors were on the faculty of the Department of Management Information Systems at the University of Arizona. It was supported in part by the National Science Foundation under grant MCS-77-24234 (M. Loomis) and by a NATO tesearch grant, obrained via the Gennar, Academic Exchange Service (W. Ef felsberg) .