Mathematical Techniques for Efficient Record Segmentation in Large Shared Data Bases.

摘要

To minimize the average cost of retrieval from a large shared data base, it is desirable to partition the data items stored within each record into a primary and secondary record segment. Three alternative analytic models, based upon knowledge of data item lengths, transportation costs and retrieval patterns, are developed here to assist an analyst with this assignment problem. First, assuming a known constant of proportionality, k, between the cost of primary segment storage and the value of user satisfaction, the problem is formulated in terms of network flows and solved using the Ford Fulkerson Algorithm. Because a precise determination of k is often difficult, the problem is restated parametrically and solved once again for all possible values of k. It is discovered that as the value of a small primary segment increases from zero, successive optimal primary assignments are nested; i.e., there is a well-defined order in which data items are forced from the primary into the secondary segment. Lastly, a more complex total system cost is proposed as a design objective function. The resulting problem is determined to be a member of the class of bicriterion programming problems. A quick method of approximating an optimal solution is devised. In the event that suboptimality is unacceptable, the problem structure permits the use of an efficient branch and bound enumeration to locate an exact solution.