Efficient allocation in distributed object oriented databases with capacity and security constraints

Efficient distribution of data is a major challenge in distributed databases. The problem is even more severe for distributed object oriented databases because of inheritance, encapsulation and the more complex problem involved when methods invoke other methods. This problem, the Object Allocation Problem (OAP), is a harder version of the relational database allocation problem (DAP), a problem known to be NP-hard. The additional problem of restricting sensitive data to secure sites, is at least as hard as the OAP.; In this research we investigated the cost efficient distribution of a fragmented object oriented database to the sites of a network. We investigated allocation algorithms for distributing the fragments in the presence of both capacity and security constraints. Initially, we assumed that all fragments were sensitive and all sites secure, and concentrated on minimizing the number of external accesses in the presence of only the capacity constraints at each node. We later relaxed that restriction and performed the optimal allocation assuming that a percentage of the fragments were sensitive and a percentage of the sites were secure. We also looked at placing the frequently communicating fragments in close proximity. The two proximity placement problems we looked at, were the adjacency placement and minimum diameter placement of frequently communicating fragments. We showed these two problems to be NP-complete.; Of the three algorithms we implemented (Genetic algorithm (GA), Simulated annealing (SA) and Kernighan-Lin (KL)) the SA and GA algorithms were clearly superior. In the presence of both capacity and security constraints, the various versions of the GA performed consistently better in minimizing the number 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.