It is well known that the complexity of testing the correctness of an arbitrary update to a database view can be far greater
than the complexity of testing a corresponding update to the main schema. However, views are generally managed according to
some protocol which limits the admissible updates to a subset of all possible changes. The question thus arises as to whether
there is a more tractable relationship between these two complexities in the presence of such a protocol. In this paper, this
question is addressed for closed update strategies, which are based upon the constant-complement approach of Bancilhon and
Spyratos. The approach is to address a more general question – that of characterizing the complexity of axiomatization of
views, relative to the complexity of axiomatization of the main schema. For schemata constrained by
denial or
consistency constraints, that is, statements which rule out certain situations, such as the equality-generating dependencies (EGDs) or, more specifically,
the functional dependencies (FDs) of the relational model, a broad and comprehensive result is obtained in a very general
framework which is not tied to the relational model in any way. It states that every such schema is governed by an equivalent
set of constraints which embed into the component views, and which are no more complex than the original set. For schemata
constrained by
generating dependencies, of which tuple-generating dependencies (TGDs) in general and, more specifically, both join dependencies (JDs) and inclusion
dependencies (INDs) are examples within the relational model, a similar result is obtained, but only within a context known
as meet-uniform decompositions, which fails to recapture some important situations. To address the all-important case of relational
schemata constrained by both FDs and INDs, a hybrid approach is also developed, in which the general theory regarding denial
constraints is blended with a focused analysis of a special but very practical subset of the INDs known as
fanout-free unary inclusion dependencies (fanout-free UINDs), to obtain results parallel to the above-mentioned cases: every such schema is governed by an equivalent
set of constraints which embed into the component views, and which are no more complex than the original set. In all cases,
the question of view update complexity is then answered via a corollary to this main result.
Keywords database - complexity - view
Parts of this paper are based upon work reported in [21].