On optimal constraint decomposition, monitoring, and management in distributed environments

This dissertation addresses three distributed database management problems: integrity constraint management, optimal view materialization, and quasi-view optimal decomposition. First, it considers the problem of decomposing global integrity constraints in a distributed database. Decompositions are performed in order to save communication and other distributed processing costs, since if during a local update the corresponding local constraint is satisfied, no distributed global constraint checking is necessary. This dissertation addresses the problem of deriving the best possible decompositions, both during database design and at update time. It formulates a generic powerful framework for finding optimal decompositions for a range of design and query-time scenarios. It also provides a comprehensive solution for the family of unrestricted linear constraints. Linear (integrity) constraints are widely used in (distributed) applications such as: resource allocation, ticket reservations, financial transactions, and logistics. The comprehensive optimization-based solution includes: (1) reducing the problem to one of mathematical programming, (2) developing effective algorithms for it, and (3) providing a distributed protocol to manage updates and constraint decompositions, while guaranteeing desirable properties of consistency, availability, and optimality. Second, the optimal view materialization problem is addressed, where for set of views (queries), one must decide which additional (intermediate) views should be materialized in order to reduce the computational effort of maintaining the views updated. It introduces a generic optimization framework to decide optimally those (intermediate) materialized views. It uses expression-DAG (Directed Acyclic Graph) as a mechanism to represent equivalent view evaluation plans, and shows that the optimal view materialization problem, under certain objective function conditions, is equivalent to finding a constrained shortest path in an expression-DAG. For those cases where the optimal solution is an expression-DAG path, a linear-time algorithm is presented. Third, the concept of quasi-view (a view with explicit update conditions) is extended considerably in this dissertation. The problem of deciding on the optimal quasi-view decomposition is addressed. This problem reduces to the optimal view materialization and constraint decomposition problems. Although the quasi-view decomposition problem is not a separable one, a solution strategy is presented in terms of the view materialization and constraint decomposition problems.