© 1976 by British Computer Society
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
Replacement algorithms for storage management in relational data bases*
1 IBM Research Laboratory, Monterey and Cottle Roads, San Jose, California, USA, 2 Department of Computing, Durham University, Durham, USA
This paper treats a generalised storage management problem in which the pages have varying sizes and the cost of a page fault is a function of the particular page reference. In addition, cost may be influenced by functional dependencies between pages. In such an environment the conventional page replacement algorithms are found to perform inadequately.
New replacement algorithms are proposed for managing the content of a buffer storage area in response to a series of such page references. Simulation experiments were conducted to compare the cost performance of these algorithms against standard techniques. An analytical model of the problem yields an upper bound on performance, and offers justification for the intuitively designed replacement algorithms.
One practical environment in which the general problem may arise is a relational data base having an implied relations facility, in which some relations are maintained in definition form until queried. The implied relation is analogous to a page, and the processing time for restructuring a relation from its definition varies from one relation to another. A suitable replacement algorithm is needed to manage the process as the implied relations alternate between the state of definitions and the state of explicit representation in a fixed buffer storage area.
Received September 1974.
* This work was done while the authors were participating in data base research at IBM United Kingdom Scientific Centre, Peterlee, County Durham.
IBM Research Laboratory, Monterey and Cottle Roads, San Jose, California 95193, USA.
¶ Department of Computing, Durham University, Durham DH1 3LE. Present address: Computer Centre, University of Khartoum, Sudan.