A Physical Database Design Methodology Using the Property of Separability.

A new approach to the multifile physical database design is presented. Most previous approaches towards multifile physical database design concentrated on developing cost evaluators for given designs. To accomplish the optimal physical design, however, these approaches had to rely on the designers intuition or on exhaustive search, which is practically infeasible even for moderate-sized databases. In our approach we develop a theory called separability to partition the entire database design problem into collective subproblems. Straightforward heuristics are employed to incorporate the features that cannot be included in the formal theory. This approach is somewhat formal, deliberately avoiding excessive reliance on heuristics. Our purpose is to render the whole design phase manageable and to facilitate understanding of the underlying mechanisms. We develop a design methodology for relational database systems based on the theory. First, we set up a basic design phase in accordance with a formal method that includes a large subset of practically important join methods and then, using heuristics, extend the design procedure to include other join methods as well. We show that the theory of separability can be applied to network model databases as well. In particular, we show that a large subset of practically important access structures that are available in network model database systems satisfies the conditions for separability. As an application to the above theory, we propose three physical database design algorithms for relational database systems. These algorithms have been fully implemented in the Physical Database Design Optimizer PhyDDO in about 6000 lines of Pascal code and tested for their validation. The results show that the solutions generated by the design algorithms do not significantly deviate from the optimal solutions.