Optimal Reorganization Policies for Stationary and Evolutionary Databases

The problem of determining optimal reorganization policies for databases which employ file structures with overflow chaining is studied. The dynamics of the file performance driven by update transactions and reorganizations is formulated as a stochastic control model which incorporates micro-level design parameters of the physical file structure. Various simplifying assumptions employed in past research are relaxed in the model. Polynomial time procedures for solving the optimization models are developed for two cases: when the file size is stationary as in the steady-state and when the file size evolves stochastically with a nonlinear trajectory. The model and the solution procedures are applied to an ISAM file revealing the effectiveness of the solution procedures and the relationship between file design parameters and the optimal policy.