On the desirability of γ-acyclic BCNF database schemes

AbstractIn this paper, we show that γ-acyclic Boyce-Codd Normal Form database schemes are highly desirable with respect to query processing and updates. We first prove that this class of schemes is bounded with respect to the set of functional dependencies embodied in the database scheme. This result enlarges the class of known bounded database schemes. We then show that this class of schemes is simple in semantics by proving that there is a simple and efficient way to compute the X-total projection of the representative instance. As a consequence, answers to many queries for this class of schemes can be computed easily and efficiently. We also show that if a γ-acyclic Boyce-Codd Normal Form database scheme is lossless, then it is connection-trap-free. Finally, we derive a simple and efficient algorithm that determines if an updated state is consistent. This allows the system to enforce the satisfaction of functional dependencies embodied in the database scheme incrementally and efficiently