Optimal Constraint Decomposition for Distributed Databases

The problem considered is that of decomposing a global integrity constraint in a distributed database into local constraints for every local site, such that the local constraints serve as a conservative approximation, i.e., satisfaction of the local constraints by a database instance guarantees satisfaction of the global constraint. Verifying local rather than global constraints during database updates reduces distributed processing costs and allows most updates, even in the presence of site and network failures. This paper focuses on the problem of deriving the best possible decompositions, both at database design and update processing time. A generic framework is formulated for finding optimal decompositions for a range of design and update-time scenarios. For the case of linear arithmetic constraints, (1) a bounded size parametric formulation of the decomposition optimization problem is introduced which has a possibly smaller search space but is proven to have the same optimum, (2) the decomposition problem is reduced to the problem of resource distribution which simplifies distributed management of constraints, and (3) autonomous optimal decompositions in subsets of local database sites are shown possible and are proven to preserve optimality under the resource bounds constraints.