Allocation of database files in a multiprocessor machine
Varsha Iyengar, Syming Hwang · 1989
The allocation of database files in a multiprocessor environment is relevant in two contexts: when processor clusters are (i) not defined, and (ii) defined. For the first situation, three methods are suggested for clustering processors and for allocating database files among the processor clusters after vertical partitioning is performed on all the relations. The first method suggests the use of as many processor clusters as the number of relations, and the placement of all fragments belonging to one relation in one processor cluster. This method exploits the inherent lack of affinity that exists between attributes of a relation that do not belong to the same fragment. After fragments of all the relations are obtained and grouped together such that those having high affinity for one another are placed into one super-fragment the second method suggests having as many processor clusters as the number of super-fragments, and allocating the fragments associated with one super-fragment to one cluster of processors. This method is recommended when the major cost is for transportation or communication of fragments across processor clusters. The third method suggests placing all the fragments contained in one super-fragment in different clusters of processors; this method is recommended when the pure sorting cost of fragments is dominant. When the processors clusters are lady defined, and assumed to be identical, the problem of allocating fragments or related files of a database among the processor clusters or locations is denoted as the Related File Allocation Problem (RFAP). This problem is shown to be NP-hard by showing a special case of the problem to be NP-hard. The RFAP is then formulated as an integer program. Since the problem is NP-hard, we provide methods to obtain lower and upper bounds for the RFAP. A good lower bound can be found in polynomial time by relaxing the binary restriction on the decision variables. Two methods are presented for obtaining upper bounds. The first method suggested is a heuristic which performed well when tested on forty two small sorting-intensive problems. The second method presented is a theoretical formulation using neural networks.