Characterization of desirable properties of general database decompositions

The classical theory of acyclicity of universal relational schemata identifies a set of “desirable” properties of such schemata, and then shows that all of these properties are equivalent to one another, and in turn equivalent to certain acyclicity characterizations of a hypergraph underlying the schema. The desirable properties include the simplicity of constraints, the correctness of certain efficient query evaluation algorithms, and the complexity of maintaining the integrity of a decomposed database. The principal result of this paper is to show that the essence of this result may be extended to a much more general setting; namely, that in which database schemata are just sets and database mappings just functions. Rather than identifying a single “desirability” class, our work shows that there are several, all of which collapse to a common group when restricted to the universal relational setting. Particularly, the classical notions of “pairwise consistency implies global consistency” and “hypergraph acyclicity” are not equivalent in the general case, but rather are independent of each other, and may be considered separately or in combination, to yield varying strengths of desirability.