J.M. Graham (USA)
Databases, genetic algorithms, simulated annealing.
Efficient distribution of data is a major challenge in dis tributed databases. The problem is even more severe for distributed object oriented databases because of inheri tance, encapsulation and the more complex problem in volved when methods invoke other methods. This prob lem, the Object Allocation Problem (OAP), is a harder ver sion of the relational database allocation problem (DAP), a problem known to be NP-hard. The additional constraint of restricting sensitive data to secure sites, results in a problem which is at least as hard as the OAP.In this research we in vestigated the cost efficient distribution of a fragmented ob ject oriented database to the sites of a network. We investi gated allocation algorithms for distributing the fragments in the presence of both capacity and security constraints. We assumed that each site had a fixed capacity and that there are two types of fragments, sensitive fragments containing sensitive data, and non-sensitive fragments containing gen eral data. Likewise we considered two types of sites, secure and non-secure. A secure site is one which was designed to minimize the likelihood of the data at that location be ing compromised. We looked at the two conflicting goals of minimizing the number of external accesses and at the same time, minimizing the number of sensitive fragments placed at non-secure sites. We implemented three algo rithms a Genetic algorithm (GA) a simulated annealing al gorithm (SA) and a graphical partitioning algorithm (KL). We took two multiobjective approaches, the penalty and the pareto approaches and we looked at two types of initial allocations, heuristic and random.Of the three algorithms implemented the Genetic algorithm (GA), Simulated an nealing (SA) and Kernighan-Lin (KL), the SA and GA al gorithms were clearly superior. In the presence of both ca pacity and security constraints, the various versions of the GA performed consistently better in minimizing the num ber of security violations while the SA algorithm versions typically had lower costs. The noted exception was the GA penalty version algorithm with random initial allocation, which performed very well in both cost minimization and reducing the number of security violations.
Important Links:
Go Back
