Unique complements and decompositions of database schemata

In earlier work, Bancilhon and Spyratos introduced the concept of a complement to a database schema, and showed how this notion could be used in theories of decomposition and update semantics. However, they also showed that, except in trivial cases, even minimal complements are never unique, so that many desirable results, such as canonical decompositions, cannot be realized. Their work dealt with database schemata which are sets and database mappings which are functions, without further structure. In this work, we show that by adding a modest amount of additional structure, many important uniqueness results may be obtained. Specifically, we work with database schemata whose legal states form partially ordered sets (posets) with least elements, and with database mappings which are isotonic and which preserve this least element. This is a natural algebraic structure which is inherent in many important examples, including relational schemata constrained by data dependencies, with views constructed by composition of projection, restriction, and selection. Other examples include deductive database schemata in which views are defined by rules, and general first-order logic databases. Within this context of posets, we show that direct (i.e., independent) complements must be unique, and that in fact the directly complementable views have the structure, in a very natural sense, of a Boolean algebra. Decompositions of the schema then become identifiable with finite subalgebras of this Boolean algebra. To demonstrate the utility of our approach, we examine in some detail its applicability to the relational model. Particularly, we establish that under the condition that the schema is constrained by universal Horn sentences, there is a unique ultimate decomposition into a finite set of type restrictions. The latter are a special class of views which includes classical projections which occur in direct decompositions. In particular, classical join-based decomposition is completely recovered within a framework which explicitly axiomatizes independence via null values