Let U = ⟨ A 1 ,..., A n ⟩ be a set of attributes and let d = ⟨ r 1 ,..., r k ⟩ be a set of relations over U. Assume that where R i, is the set of attributes that corresponds to the relation r i , i = 1 , 2 ,..., k. The sequence ⟨ R 1 , R 2 ,..., R k ⟩ is called a decomposition scheme for U. Loizou and Thanisch prove that, for a given set of multivalued dependencies M over U (see Maier [1]), a decomposition scheme ⟨ R 1 , R 2 ,..., R n ⟩, 1 ≤ n, exists that is in fourth normal form (4NF) with respect to M [1]. The proof consists essentially of a description and analysis of an algorithm that finds the required decomposition. The space requirements of this algorithm are polynomial in the size of M and U (its time requirements are, of course, exponential). The number of relations provided by the 4NF decomposition algorithms published previously is not bounded by a number of given attributes. On the other hand, the dependencies can be (trivially) chosen in such a way that the only possible 4NF decomposition should be ⟨ A 1 ,..., A n ⟩.
This paper is devoted to the “pure” normalization theory. As such, it will be helpful not in practical database design, but only in the current search for advanced database architectures.
