An analytical investigation into record structuring and physical database design of generalized logical data structures (optimization, formulation, heuristics)
Prashant Palvia · 1984
This research concerns itself with the efficient design of the physical database. Within physical database design, its emphasis is on the definition of the record structures of the various computerized files in the database. Specifically, efficient physical database designs are generated so as to minimize the page access and/or storage cost of the database; given a generalized logical data structure (LDS), activities on the data and the computer system characteristics. A generic model for physical database design is used which allows aggregation (storing related instances of two entities together) and pointers for representing relationships in the LDS. In order to obtain optimal or near optimal solution to the design problem, six heuristics have been developed. Four of them are based on problem specific pairwise entity information and two are based on generic principles of optimization. Recommendations have been made on the proper use of the heuristics. In addition, the heuristics have been evaluated using a comprehensive experimental design. Further, some guidelines for physical design have been proposed; and a sensitivity analysis of design factors has been made. In addition, a non-linear zero-one integer program has been formulated for a subcase of the general problem. Several approaches have been proposed to optimally solve the integer program. The formulation will serve as the basis for future mathematical programming efforts. In support of the heuristic methods, an evaluator/simulator has been written in FORTRAN to evaluate the access and storage costs of a given physical design. Embedded in the evaluator are certain new mathematical expressions and formulas that facilitate evaluation. Finally, the feasibility of implementing the physical design, as generated by this process, on commercial DBMSs has been examined. This has been demonstrated on two commercial DBMSs, namely IMS of IBM and CODASYL based DBTG systems.