A New Normal Form for Nested Relations

We consider nested relations whose schemes are structured as trees, called scheme trees, and introduce a normal form for such relations, called the nested normal form. Given a set of attributes U, and a set of multivalued dependencies (MVDs) M over these attributes, we present an algorithm to obtain a nested normal form decomposition of U with respect to M. Such a decomposition has several desirable properties, such as explicitly representing a set of full and embedded MVDs implied by M, and being a faithful and nonredundant representation of U. Moreover, if the given set of MVDs is conflict free, then the nested normal form decomposition is also dependency preserving. Finally, we show that if M is conflict free, then the set of root-to-leaf paths of scheme trees in nested normal form decomposition is precisely the unique 4NF decomposition [Fa, L2] of U with respect to M. 1. Introduction A relational database [Co] is a collection of relations where each relation is at least in First ..