Accession Number : ADA326519

Title :   A Physical Database Design Methodology Using the Property of Separability.

Descriptive Note : Doctoral thesis,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Whang, Kyu-Young

PDF Url : ADA326519

Report Date : MAY 1983

Pagination or Media Count : 274

Abstract : 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 designer's 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.

Descriptors :   *DATA BASES, *DISTRIBUTED DATA PROCESSING, ALGORITHMS, OPTIMIZATION, DATA MANAGEMENT, COMPUTER AIDED DESIGN, COMPUTER COMMUNICATIONS, THESES, HEURISTIC METHODS, SYSTEMS ANALYSIS, COMPUTER NETWORKS, COMPUTER FILES, COMPUTER PROGRAM VERIFICATION, DESIGN CRITERIA, BLOCK ORIENTED RANDOM ACCESS MEMORIES, PASCAL PROGRAMMING LANGUAGE.

Subject Categories : Computer Programming and Software
      Computer Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE