Modern applications involving information systems often require the cooperation of several distinct users, and many models of such cooperation have arisen over the years. One way to model such situations is via a cooperative update on a database; that is, an update for which no single user has the necessary access rights, so that several users, each with distinct rights, must cooperate to achieve the desired goal. However, cooperative update mandates new ways of modelling and extending certain fundamentals of database systems. In this paper, such extensions are explored, using database schema components as the underlying model. The main contribution is an effective three-stage process for inter-component negotiation.

A generalized approach to the decomposition of relational schemata is developed in which the component views may be defined using both restriction and projection operators, thus admitting both horizontal and vertical decompositions. The realization of restrictions is enabled through the use of a Boolean algebra of types, while true independence of projections is modelled by permitting null values in the base schema. The flavor of the approach is algebraic, with the collection of all candidate views of a decomposition modelled within a lattice-like framework, and the actual decompositions arising as Boolean subalgebrac. Central to the framework is the notion of sidimensional join dependency, which generalizes the classical notion of join dependency by allowing the components of the join to be selected horizontally as well as vertically. Several properties of such dependencies are presented, including a generalization of many of the classical results known to be equivalent to schema acyclicity. Finally, a characterization of the nature of dependencies which participate in decompositions is presented. It is shown that there are two major types, the bidimensional join dependencies, which are tuple generating and allow tuple removal by implicit encoding of knowledge, and splitting dependencies, which simply partition the database into two components.

The problem of updating incomplete information databases is examined as a programming problem. From this point of view formal denotational semantics are developed for two applicative programming languages, BLU and HLU. BLU is a very simple language with only five primitives, and is designed primarily as a tool for the implementation of higher level languages. The semantics of BLU are formally developed at two levels possible worlds and clausal and the latter is shown to be a correct implementation of the former. HLU is a user level update language. It is defined entirely in terms of BLU, and so immediately inherits its semantic definition from that language. This demonstrates a level of completeness for BLU as a level of primitives for update language implementation. The necessity of a particular BLU primitive, masking, suggests that there is a high degree of inherent complexity in updating logical databases.

The problem of reflecting updates from a view schema to the base schema in relational database systems is investigated. The basic strategy which is employed is that of translation relative to a constant complement, as developed by Bancilhon and Spyratos. We deal in particular with one of the apparent drawbacks of the constant complement approach, namely, the nonuniqueness of such complements. Our approach is to use only a specific set of well-behaved views, termed the components of the schema, as complements. The components form a Boolean algebra, and update reflection to the base schema is independent of choice of complement, as long as the complement is a component. We argue that such reflections of updates are the "natural" ones which should be allowed.

An algebraic framework for investigating the problem of decomposing a relational database schema into components is developed. It is argued that the views of a relational schema which are to be the components of a decomposition should form a finite atomic Boolean algebra. The unit of the algebra is the identity view, and the zero is the null view. The join operation in this algebra is to be a generalization of the usual concept of join; the resulting view should contain precisely the representation contained in the two component views as a unit. The meet operation in this algebra is to measure the interdependence of the components, and is to be zero if and only if they are independent. A decomposition of the schema is then to be a decomposition of the identity component, with the ultimate decomposition the one consisting entirely of atoms.The thrust of the results is in two directions. First, the general properties of relational schemata particular to this problem are developed, within the framework of first-order logic. The key formulations are those of abstract meet and join of schemata. Using these formulations, it is shown that a completely general decomposition theory is impossible. The second part of the work islolates a relatively large class of schemata which do admit reasonable decompositions. These schemata include all of the usual decomposition problems, including project-join decompositions and horizontal decompositions of schemata constrained by universal Horn sentences.