Optimal Reorganization Policies for Stationary and Evolutionary Databases
研究使用溢出链文件结构的数据库的最优重组策略，建立随机控制模型，开发多项式时间求解方法，适用于文件大小静态或随机演化的情况，并应用于ISAM文件验证有效性。
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.