Essays on some critical issues in physical database design
Robert Bartôszyński, June Sung Park · 1988
The dissertation investigates four important issues in physical database design and maintenance. In Part I, an analytic model is developed to integrate two closely related subprograms of physical database design: vertical segmentation and access path selection. A generic design process for the integrated performance model is suggested and applied to a relational database. A heuristic procedure and an optimal algorithm are developed for solving the model which is 0/1 nonlinear program. Extensive computational results are reported to show the effectiveness of these solution techniques. Vertical segmentation is shown to save database operating costs by 30-60%. In Part II, a low-level optimizer is developed for queries processed on vertically segmented relations. The optimizer takes into account the presence of both clustered and non-clustered indexes, and incorporates such factors as the optimal subfile access sequence and the optimal selection of an access method based on the selectivity factor. The optimizer is formalized as a rule-based system, and a prototype implementation module coded in LISP is provided. In Part III, the problem of determining optimal reorganization policies for databases which employ file structures with overflow chaining is studied. The dynamics of database 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. 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 stochastically evolves with a nonlinear trajectory. Applications of the model and the solution procedures to real-life databases are illustrated by examples. In Part IV, an adaptive file migration algorithm is developed for distributed database systems based on multi-access broadcast communication network. Decentralized file migration decisions at individual sites are assumed allowing the site autonomy. Bayesian approach is used for adaptive forecasting of file access rates. A dynamic optimization model of the file migration policy is developed using Bellman approach. A heuristic solution algorithm is presented and proved to produce $\epsilon$-optimality. The effect of local storage expansion on the network traffic load is also investigated.