Constant-time-maintainable database schemes are highly desirable with respect to constraint enforcement, since it is possible to determine whether any of their consistent states plus an inserted tuple is consistent in time independent of the state size. Several proper subclasses of constant-time-maintainable database schemes are known to be bounded with respect to dependencies and hence very desirable with respect to query answering. However, whether the whole class of constant-time-maintainable database schemes is bounded is not known for sure. In this paper, it is proven that the entire class of constant-time-maintainable database schemes is bounded with respect to dependencies and thus very desirable with respect to query answering in the following cases: (1) only cover-embedded functional dependencies appear as constraints; (2) only equality-generating dependencies appear as constraints and the database scheme has a lossless join. In particular, it is shown that total projections of representative instances can be computed via unions of projections of simple chase join expressions. Since it is known how to optimize these expressions, it is possible to compute total projections optimally. These results show that the class of constant-time-maintainable database schemes is the largest class of database schemes, which are highly desirable with respect to both constraint enforcement and query answering. This class of schemes can be effectively recognized by known algorithms. The previously known largest class of database schemes with these desirable properties is the class of independent database schemes, which is a proper subclass of constant-time-maintainable schemes.

this paper we propose the factoring technique as a general technique which can detect opportunities for making the recursion less "intensive". For example, this technique can detect that certain subgoals need only be examined a bounded number of times in certain subtrees of the proof trees of the query predicate. More precisely, given a program and a query predicate (the recursive predicate), the factoring technique can determine when it is possible to limit the number of occurrences of a subgoal in selected subtrees of the proof trees of the query predicate. We call this property of subgoals proof tree removability. Our technique can also exploit the knowledge about proof tree removability in transforming a program into an equivalent program such that the proof trees constructed using the transformed program always contain a limited number of occurrences of the subgoal in selected subtrees. Proof tree removability is thus a notion that generalizes the notion of "recursively redundant" introduced by Naughton [N1, N2] in the sense that a subgoal a need not be recursively redundant w.r.t. a predicate and yet its repeated occurrences in certain subtrees of the query predicate may well be redundant. (See Section 9 for examples.) Factoring is one type of proof tree transformation, (e.g. see [RSUV, Sar]), only that it is achieved at the level of rules. In principle it may be possible to start with Naughton and others' characterization of recursively redundant predicates and then try to generalize the conditions to a larger class of rules to capture the notion of "subtree redundancy of predicates" above. Such a generalization is not at all obvious and we find it convenient to start with simple syntactic criteria for predicates to be "factored" out of linear sirups and then ...

A generahzatlon of Sagiv-independent database schemes, called (key-equivalent) independence-reducible schemes, is defined, and it is shown that it 1s highly desirable with respect to query answering and constraint enforcement.By showing that they are bounded and algebraic-maintamable the desirabdlties are proven.The class of independence-reducible schemes M exactly the class of schemes obtained from decomposing relation schemes in a Sagwmdependent scheme in a dependency preserving manner.Todemonstrate theclass ofschemes identified is rather general.itisprovedthatlt contains all prewously known classes of dependency preserving BCNF database schemes with similar properties.An efficient algorlthm is found which recognizes exactly this class of database schemes.Independence-reducible database schemes contain a class of constant-time-maintamable database schemes.A condition is found which characterizes this class of schemes and the condition can be tested efficiently.Throughout, it is assumed that a cover of the functional dependencies is embedded m a database scheme in the form of key dependencies.

The maintenance problem (for database states) ofa database scheme Rwithrespect toa set of functional dependencies Fisthefollowing decision problem.Letrbea consistent state of Rwith respect to F and assume we insert a tuple t into rP~r.Is r U {t}a consistent state of R with respect to F? R is said to be constant-time-maintainable with respect to F if there is an algorithm that solves the maintenance problem of R with respect to F in time independent of the state size.A characterization of constant-time-maintainability for the class of BCNF database schemes is given.Inefficient algorithm that tests this characterization is shown, as well as an algorithm for solving the maintenance problem in time independent of the state size.It is also shown that total projections of the representative instance can be computed via unions of projections of sequential extension joins.Throughout we assume that database schemes are dependency preserving and BCNF, and that functional dependencies are given intheform of key dependencies.

A class of cover embedding database schemes, called independence-reducible, is proposed and is proven to be bounded and algebraic-maintainable, and therefore is highly desirable with respect to query answering and constraint enforcement. This class of schemes is shown to properly contain a superset of all previously known classes of cover embedding BCNF database schemes which are bounded (and constant-time-maintainable). An efficient algorithm is found which recognizes exactly this class of database schemes. Independence-reducible database schemes properly contain a class of constant-time-maintainable database schemes and a condition which characterizes this class of schemes is found, this condition can be tested efficiently. Throughout, it is assumed that a cover of the functional dependencies is embedded in the database scheme in the form of key dependencies.

The maintenance problem (for database states) of a database scheme R with respect to a set of functional dependencies F is the following decision problem. Let r be a consistent state of R with respect to F and assume we insert a tuple t into rp ε r. Is r ∪ {t} a consistent state of R with respect to F? R is said to be constant-time-maintainable with respect to F if there is an algorithm that solves the maintenance problem of R with respect to F in time independent of the state size.

Under the weak instance model, to determine if a class of database schemes is bounded with respect to dependencies is fundamental for the analysis of the behavior of the class of database schemes with respect to query processing and updates. However, proving that a class of database schemes is bounded with respect to dependencies seems to be very difficult even for restricted cases. To resolve this problem, we need to develop techniques for characterizing bounded database schemes