A methodology for the distribution of databases (functional dependency, computer network, integer programming)
Mourad. Oulid-Aissa · Deep Blue (University of Michigan) · 1984
This research proposes an approach to distribute data that feature semantic cross-references in a computer network. The unit of distribution is the functional dependency (FD). Firstly, each scheduled query is assigned a set of cross-referencing data units (CRDUs) that will normally be accessed, at possibly different sites, to process it. Each CRDU is associated with one FD. The selected FDs are mapped to a so-called query envelope. The selection of a query envelope is based on semantic integrity and on the minimization of the total "volume" of the instances of the FDs belonging to the envelope. This problem, identified as the envelope optimization problem, is presented and analyzed in a formal framework, and is solved with efficient graph algorithms. Secondly, the CRDUs corresponding to the FDs of all the envelopes are distributed so as to minimize the operational communication cost. The issue of preservation of the database consistency is mentioned. Further, the following modeling points are considered: (i) The cross-references of physically distant CRDUs, which produce file-to-file inter-site communication in addition to the usual file-to-user communication, (ii) the partitioning of the set of CRDUs, (iii) the materialization of the CRDUs associated with one envelope, in case of duplication, (iv) the flow capacity constraints. The problem of the distribution of CRDUs is modeled in the form of a manageable multi-commodity mixed-integer program, with quadratic cost and linear constraints. Computational techniques and numerical experience are discussed. Through experimental investigations, the research draws some practical conclusions about the distribution of CRDUs in a computer network. The effect of the reducing and assembly rates over the simultaneous referencing of CRDUs, and over data redundancy, is investigated. Further, the effect of the updating rates over cross-referencing, and over data redundancy, is investigated. The results suggest that a look-up of the user-provided data can indicate whether st and ard data distribution techniques, instead of CRDU distribution techniques, can be used.