Constant-time-maintainable BCNF database schemes
Héctor J. Hernández, Edward P. F. Chan · ACM Transactions on Database Systems · 1991
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.