An integer programming formulation of computer data base design problems

Traditionally, computer data base design has been handled intuitively without the assistance of quantitative techniques. A systematic approach to data base design consists of these phases: (1) a mathematical problem statement; (2) problem reduction; (3) mathematical solution. This paper addresses the first phase (associated work on the other phases is briefly discussed) and demonstrates that certain data base design problems can be formulated as nonlinear, zero-one programs. The decision variables state which logical data base elements (entities and attributes) are represented in each subdivision (subfile) of the physical data base. Computational experience using cluster analysis for problem reduction and branch and bound for mathematical solution is reported. It is shown that a planned subdivision of the physical data base can yield noticeable operating cost improvements over conventional data base designs.