Replacement algorithms for storage management in relational data bases

Open Access
Publisher Website
Google Scholar
Abstract
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.

This publication has 0 references indexed in Scilit: