Schema Evolution publication categorizer

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.