A Comparative Study of Various Nested Normal Forms.
As object-relational databases (ORDBs) become popular in the industry, it is important for database designers to produce database schemes with good properties in these new kinds of databases. One distinguishing feature of an ORDB is that its tables may not be in first normal form. Hence, ORDBs may contain nested relations along with other collection types. To help the design process of an ORDB, several normal forms for nested relations have recently been defined, and some of them are called nested normal forms. In this paper, we investigate four nested normal forms, which are NNF 20, NNF 21, NNF 23, and NNF 25, with respect to generalizing 4NF and BCNF, reducing redundant data values, and design flexibility. Another major contribution of this paper is that we provide an improved algorithm that generates nested relation schemes in NNF 2 from an $ database scheme, which is the most general type of acyclic database schemes. After presenting the algorithm for NNF 20, the algorithms of all of the four nested normal forms and the nested database schemes that they generate are compared. We discovered that when the given set of MVDs is not conflict-free, NNF 20 is inferior to the other three nested normal forms in reducing redundant data values. However, in all of the other cases considered in this paper, NNF 20 is at least as good as all of the other three nested normal forms.
Introduction
Object-Relational Databases (ORDBs) could be an alternative for the next-generation databases [SBM98].
This hybrid approach is sound because it is based on mature relational technology. By adding object-oriented
features to a relational database, an ORDB is obtained. Since this approach seems like a natural extension of
a relational database, numerous relational commercial products are already supporting many object-oriented
features [Kim97], [Urm97].
One distinguished feature of an ORDB is that a relation can be nested in another relation; thus, a nested
relation. Since ORDBs support nested relations, it is imperative for database designers to be able to design
nested databases with good properties. In the past, numerous normal forms have been defined for flat
relations so that if a flat relation scheme satisfies a certain normal form, then the relations on that scheme
will enjoy the properties of the normal form. For a long time, database designers have been using these
normal forms as guides for flat relational database design. In the same spirit, numerous normal forms have
been defined recently for nested relations as well [MNE96], [OY87a], [OY89], [RK87], [RKS88]. Among
all of these cited normal forms, Partition Normal Form (PNF), which is defined in [RKS88], is the most
fundamental. In essence, PNF basically states that in a nested relation, there can never be distinct tuples
that agree on the atomic attributes of either the nested relation itself or of any nested relation embedded
within it [RKS88]. Since this is a basic property of nested relations, the normal forms defined in [MNE96],
[OY87a], [OY89], [RK87] all imply PNF.
As guides for database design, normal forms should be used with cautions. Database designers should
understand the strengths and the weaknesses of a normal form in order to use it intelligently. As an example,
it is well known that 4NF is able to remove redundancy caused by FDs; however, it is not dependency
preserving. On the other hand, 3NF is dependency preserving but it is not able to remove redundancy
caused by FDs in all cases. Knowing information like this is in fact vital for a successful database design.
Hence, the main purpose of this paper is to compare the normal forms defined in [MNE96], [OY87a], [OY89],
[RK87], and to find out their strengths and weaknesses. In particular, we investigate them with respect to
generalizing 4NF and BCNF, reducing redundant data values, and design flexibility. In addition, we also
examine their algorithms and the nested database schemes that they generate.
Since the algorithms of the normal forms will be investigated, we take this opportunity to provide a more
general algorithm for the normal form defined in [MNE96] than the ones we gave in [ME96], [ME98]. It
turns out to be another contribution of this paper.
Here, we would like to recognize some other normal forms defined for nested relations, such as the ones in
[LY94], [TSS97]. However, they are not included in the investigation because the normal form in [TSS97] is
mainly dealing with semantic issues as opposed to removing redundancy; and the one in [LY94] is based on
extended MVDs, which makes it very hard to be compared with the others.
In the following, to avoid being too wordy, we abbreviate the normal form defined in [MNE96], which is
called nested normal form, as NNF [MNE96] . Similarly, the normal form defined in [OY87a] is abbreviated as
NNF [OY87a] , the one defined in [OY89] as NNF [OY89] , and the one defined in [RK87] as NNF [RK87] . Notice
that the comparisons among NNF [OY87a] , NNF [OY89] , and NNF [RK87] are already done, as presented in
[OY89], [RK87], and the results are not reproduced here.
The paper is organized as follows. In Section II, we present some basic definitions and concepts. The
normal forms are formally compared in Section III and we conclude in Section IV.
II. Basic Concepts & Terminology
We first present some basic definitions. After which, the definition of each of the normal forms is presented.
A. Nested Relation Schemes & Nested Relations
The following definitions of nested relation schemes, nested relations, and scheme trees are adapted from
[MNE96]. However, any equivalent definitions of these concepts, such as those in [OY87a], [OY89], [RK87],
can be used as well.
nested relation allows each tuple component to be either atomic or another nested relation, which may
itself be nested several levels deep.
1: Let U be a set of attributes. A nested relation scheme is recursively defined as follows:
1. If X is a nonempty subset of U , then X is a nested relation scheme over the set of attributes X .
2. If X , X 1 , . , are pairwise disjoint, nonempty subsets of U , and R 1 , . , Rn are nested relation
schemes over X 1 , . , respectively, then X (R 1 )  . (Rn )  is a nested relation scheme over XX 1 .
Dept Chair (Prof (Hobby)  (Matriculation (Student (Interest)
CS Turing Jane Skiing Ph.D. Young Chess
Soccer
Barker Skiing
M.S. Adams Skiing
Pat Hiking Ph.D. Lee Travel
Math Polya Steve Dance M.S. Carter Travel
Hiking Skiing
Fig. 1. Nested relation.
Definition 2: Let R be a nested relation scheme over a nonempty set of attributes Z. Let the domain of
an attribute A 2 Z be denoted by dom(A). A nested relation over R is recursively defined as follows:
1. If R has the form X where X is a set of attributes fA 1 , . , An g, n  1, then r is a nested relation over
if r is a (possibly empty) set of functions where each function t i , 1  i  m, maps A j to an
element in
2. If R has the form X (R 1 )  . (Rm is a set of attributes fA 1 , . , An g, n  1, then
r is a nested relation over R if
(a) r is a (possibly empty) set of functions ft 1 , . , t p g where each function t i , 1  i  p, maps A j to an
element in to a nested relation over R k , 1  k  m, and
Each function of a nested relation r over nested relation scheme R is a nested tuple of r. 2
Several observations can be made about Definitions 1 and 2. First, flat relation schemes are also nested
relation schemes. Second, any two distinct embedded nested relation schemes do not have any attribute in
common. For example, a nested relation scheme such as A (C)* (B (C)* is not allowed. Third, in this
paper, every nested relation is in PNF [RKS88].
Example 1: Figure 1 shows a nested relation. Its scheme is Dept Chair (Prof (Hobby)* (Matriculation
(Student (Interest)* and it contains two nested tuples. Each embedded nested relation also contains
nested tuples of its own. For example, !Young, fChess, Soccerg? and !Barker, fSkiingg? are nested tuples
under the embedded nested relation scheme Student (Interest)*. Notice that, as required, PNF is satisfied.
Thus, the values for the atomic attributes, Dept Chair, differ, and in each embedded nested relation, the
atomic values differ. 2
Definition 3: Let R be a nested relation scheme. Let r be a nested relation on R. The total unnesting of
r is recursively defined as follows:
1. If R has the form X , where X is a set of attributes, then r is the total unnesting of r.
2. If R has the form X (R 1 )  . (Rn ) , where X i is the set of attributes in R i , 1  i  n, then the total
unnesting of there exists a nested tuple u 2 r such that tuple in the
total unnesting of u(R i
Example 2: Figure 2 shows the total unnesting of the nested relation in Figure 1. 2
Dept Chair Prof Hobby Matriculation Student Interest
CS Turing Jane Skiing Ph.D. Young Chess
CS Turing Jane Skiing Ph.D. Young Soccer
CS Turing Jane Skiing Ph.D. Barker Skiing
CS Turing Jane Skiing M.S. Adams Skiing
CS Turing Pat Hiking Ph.D. Lee Travel
Math Polya Steve Dance M.S. Carter Travel
Math Polya Steve Dance M.S. Carter Skiing
Math Polya Steve Hiking M.S. Carter Travel
Math Polya Steve Hiking M.S. Carter Skiing
Fig. 2. Total unnesting of nested relation in Fig. 1.
We can graphically represent a nested relation scheme by a tree, called a scheme tree. A scheme tree
captures the logical structure of a nested relation scheme and explicitly represents a set of MVDs.
Definition 4: A scheme tree T corresponding to a nested relation scheme R is recursively defined as follows:
1. If R has the form X , then T is a single node scheme tree whose root node is the set of attributes X .
2. If R has the form X (R 1 )  . (Rn ) , then the root node of T is the set of attributes X , and a child of
the root of T is the root of the scheme tree T i , where T i is the corresponding scheme tree for the nested
relation scheme R i
The one-to-one correspondence between a scheme tree and a nested relation scheme along with the definition
of a nested relation scheme impose several properties on a scheme tree. Let T be a scheme tree. We
denote the set of attributes in T by Aset(T ). Observe that the atomic attributes of a nested relation scheme,
at any level of nesting, constitute a node in a scheme tree. Observe further that since Definition 1 requires
nonempty sets of attributes, every node in T consists of a nonempty set of attributes. Furthermore, since
the sets of attributes corresponding to nodes in T are pairwise disjoint and include all the attributes of T ,
the nodes in T are pairwise disjoint, and their union is Aset(T ).
Let N be a node in T . Notationly, Ancestor(N ) denotes the union of attributes in all ancestors of N ,
including N . Similarly, Descendent(N ) denotes the union of attributes in all descendants of N , including
N .
In a scheme tree T each edge (V; W ), where V is the parent of W , denotes an MVD Ancestor(V ) !!
Notationly, we use MVD(T ) to denote the set of all the MVDs represented by the edges in
T . By construction, each MVD in MVD(T ) is satisfied in the total unnesting of any nested relation for T .
Since FDs are also of interest, we use FD(T ) to denote any set of FDs equivalent to all FDs
by a given set of FDs and MVDs over a set of attributes U such that Aset(T ) ' U and XY ' Aset(T ).
Example 3: Figure 3 shows the scheme tree T for the scheme of the nested relation in Figure 1. Figure 3
also gives the set of attributes in Aset(T ) and the set of MVDs in MVD(T ). Observe that each of the MVDs
in MVD(T ) is satisfied in the unnested relation in Figure 2. 2
Given a set D of MVDs and FDs over a set of attributes U , and a scheme tree T such that Aset(T ) ' U ,
Aset(T ) may be a proper subset of U . However, D may imply MVDs and FDs that hold for T . By Theorem 5
in [Fag77], an MVD X !! Y holds for T with respect to D if X ' Aset(T ) and there exists a set of attributes
Prof
Hobby Matriculation
Student
Interest
Matriculation Student Interest
Matriculation Student Interest,
Dept Chair Prof !! Hobby,
Dept Chair Prof !! Matriculation Student Interest,
Dept Chair Prof Matriculation !! Student Interest,
Dept Chair Prof Matriculation Student !! Interestg
Fig. 3. Scheme tree T , Aset(T ), and MVD(T ) for nested relation scheme in Fig. 1.
Student, Interestg
fStudent !! Interest, Prof !! Hobby Hobby-Equipment,
Hobby !! Hobby-Equipmentg
Fig. 4. Some given constraints over a set of attributes.
Z ' U such that
to D if XY ' Aset(T ) and D implies X ! Y on U .
Example 4: Figure 4 shows a given set of attributes U and a given set of FDs F over U and a given set of
MVDs M over U . All the FDs in F hold for the scheme tree T in Figure 3. Not all the MVDs in M hold for
In particular, neither Hobby !! Hobby-Equipment nor Prof !! Hobby Hobby-Equipment holds
for T . Since Hobby Hobby-Equipment " Aset(T does hold for T . Although Prof
!! Hobby does hold for T , observe that it is not implied by M [ F on U . 2
B. Conflict-Free Sets of MVDs & Acyclic Database Schemes
Some researchers have claimed that most real-world sets of MVDs are conflict-free and that acyclic database
schemes are sufficiently general to encompass most real-world situations [BFMY83], [Sci81]. In fact, conflict-free
sets of MVDs and acyclic database schemes have numerous desirable properties [BFMY83]. Therefore,
we would like to examine the normal forms with respect to conflict-free sets of MVDs and acyclic database
schemes. Their definitions are now presented.
An MVD X !! Y (with X and Y disjoint) splits two attributes A and B if one of them is in Y and the
other is in U \Gamma XY , where U is the set of all the attributes. A set M of MVDs splits A and B if some
MVD in M splits them. An MVD (or a set of MVDs) splits a set X , where X ' U , if it splits two distinct
attributes in X . Let D be a set of MVDs and FDs over U . LHS (D) denotes the set of left-hand sides of the
members of D. As usual, DEP(X ) denotes the dependency basis of X , which is a partition of U \Gamma X .
Definition 5: A set M of MVDs is conflict-free if
1. M does not split any element in LHS (M ).
2. For every X 2 LHS (M ) and for every Y 2 LHS (M ),
A conflict-free set of MVDs allows a unique 4NF decomposition [BFMY83]. We shall use this fact in the
proof of Lemma 6.
A database scheme over a set of attributes U is a set of relation schemes where each
relation scheme R i is a subset of U and [ n
Notice that every database scheme R corresponds
to a unique join dependency, namely 1R [Mai83]. A database scheme R is acyclic if and only if the join
dependency 1R is equivalent to a conflict-free set of MVDs [BFMY83]. Also, R is acyclic if and only if R
has a join tree [BFMY83].
Definition be a database scheme. A join tree for R is a tree where each
R i is a node, and
1. Each edge (R i , R j ) is labeled by the set of attributes R i " R j , and
2. For every pair R i and R j (R i 6= R j ) and for every A in R i " R j , each edge along the unique path between
R i and R j includes label A (possibly among others). 2
Let M be a set of MVDs over a set of attributes U . Notationly, we use M + to denote the closure of M .
M has the intersection property if whenever the MVDs X !! Z and Y !! Z are implied by M (with Z
disjoint from both X and Y ), then by M . Furthermore, M has the intersection
property if and only if M + is implied by a join dependency 1R [BFMY83]. We shall use this property in
the proof of Theorem 6.
C. NNF [MNE96]
We now present NNF [MNE96] .
Definition 7: Let U be a set of attributes. Let M be a set of MVDs over U and F be a set of FDs over U .
Let T be a scheme tree such that Aset(T ) ' U . T is in NNF [MNE96] with respect to M [ F if the following
conditions are satisfied.
1. If D is the set of MVDs and FDs that hold for T with respect to M [F , then D is equivalent to MVD(T )
2. For each nontrivial FD X ! A that holds for T with respect to M [ F ,
with respect to M [ F , where NA is the node in T that contains A. 2
D. NNF [OY 87a]
The definition of reduced MVDs is fundamental to NNF [OY87a] , NNF [OY89] , and NNF [RK87] and is now
adapted from [OY87a], [OY87b].
Definition 8: Let U be a set of attributes. Let M be a set of MVDs over U . X !! W in M + is
1. trivial if
2. left-reducible if there is an X 0 ae X such that X 0 !! W is in M
3. right-reducible if there is a W 0 ae W such that X !! W 0 is a nontrivial MVD in M
4. transferable if there is an X 0 ae X such that X 0 !!
An MVD X !! W is reduced if it is nontrivial, left-reduced (non-left-reducible), right-reduced (non-right-
reducible), and non-transferable. 2
Let M 1 and M 2 be sets of MVDs over a set of attributes U . M 1 is a cover of M 2 if and only if M
.
Definition 9: Let U be a set of attributes. Let M be a set of MVDs over U . Let
X !! W is a reduced MVD in M + g. Elements in LHS are called of M . A minimal cover Mmin
of M is a subset of M \Gamma and no proper subset of Mmin is a cover of M . 2
NNF [OY87a] disallows several configurations of scheme trees. To achieve this goal, transitive dependencies
and fundamental keys in a scheme tree are defined. Let M be a set of MVDs over a set of attributes U . Let
T be a scheme tree such that Aset(T ) ' U . We say that M implies MVD(T ) on Aset(T ) if for each MVD
implies an MVD X !! Z on U such that Assuming that M
implies MVD(T ) on Aset(T ). Let (V; W ) be an edge in T . Suppose that there is a key X of M such that
there exists a Z 2 DEP(X ) and Descendent(W there exist some sibling nodes W 1 , . ,
Wn of W in T such that
not hold for T with respect to M , then W is transitive redundant with respect to X in T . In this case X
Descendent(W ) on Aset(T ) is a transitive dependency in Aset(T ). Let V be a subset of U . The set of
fundamental keys on V , denoted by FK (V ), is defined as FK (V
When FDs are given, NNF [OY87a] uses the MVDs counterparts of FDs. That is, for each given FD
replaced by the set of MVDs fX !! A j A 2 Y g. We are now ready to present NNF [OY87a] .
Definition 10: Let U be a set of attributes. Let D be a set of MVDs and FDs over U . Let M be the
set g. Let T be a scheme tree such that
Aset(T . T is in NNF [OY87a] with respect to D if
1. M implies MVD(T ) on Aset(T ).
2. For each edge (V; W ) of T , Ancestor(V ) !! Descendent(W ) on Aset(T ) is left- and right-reduced with
respect to M .
3. For each node N in T , there is no key X of M such that N is transitive redundant with respect to X .
4. The root of T is a key of M , and for each other node N in T , if FK (Descendent(N
When FDs are given, this normal form uses the envelope sets defined in [YO92] to handle MVDs and
FDs together. Hence, it is not necessary to consider the MVDs counterparts of FDs. From a given set D
of MVDs and FDs, the authors first derive the envelope set E (D) of D and the normal form is defined in
terms of E (D) and D.
The envelope set E (D) of D is defined as fX !! W j X 2 LHS (D) and W 2 DEP(X ) and X 6! Wg.
Notice that the authors also redefine transitive dependencies and fundamental keys for this normal form,
which affect Conditions 3 and 4. The new definition of fundamental keys on a set of attributes V is denoted by
defined as fV " and there is no Y 2 LHS (E (D) min )
such that ;g. The new definition of transitive dependencies is lengthy and involved,
however. Furthermore, since we will not use this new definition of transitive dependencies in this paper, we
do not reproduce it here.
Definition 11: Let U be a set of attributes. Let D be a set of MVDs and FDs over U . Let E (D) be the
envelope set of D. Let T be a scheme tree such that Aset(T ) ' U . T is in NNF [OY89] with respect to D if
1. E (D) implies MVD(T ) on Aset(T ).
2. For each edge (V; W ) of T , Ancestor(V ) !! Descendent(W ) on Aset(T ) is left- and right-reduced with
respect to E (D).
3. For each node N in T , there is no key X of E (D) such that N is transitive redundant with respect to X .
4. The root of T is a key of E (D), and for each edge (V; W ) in T , if D does not imply Ancestor(V
is a leaf node
of T . 2
F. NNF [RK87]
When FDs are given, this normal form uses the integrated approach described in [BK86] to handle MVDs
and FDs together. Hence, it is not necessary to consider the MVDs counterparts of FDs. From a given
set D of MVDs and FDs, the authors first derive another set M 0 of MVDs and the normal form is defined
mainly in terms of M 0 . Notice in the following that X + denotes the closure of a set of attributes X and that
NNF [RK87] uses the original definition of fundamental keys in Section II-D.
Definition 12: Let U be a set of attributes. Let D be a set of MVDs and FDs over U . Let M 0 be the
set g. Let T be a scheme tree such that Aset(T ) ' U . T is in
NNF [RK87] with respect to D if
1. M 0 implies MVD(T ) on Aset(T ).
2. For each edge (V; W ) of T , Ancestor(V ) !! Descendent(W ) on Aset(T ) is left- and right-reduced with
respect to M 0 .
3. For each node N in T , there is no key X of M 0 such that N is transitive redundant with respect to X .
4. The root of T is a key of M 0 and is in LHS (M 0 ), and for each other node N in T , if FK (Descendent(N
Further normalization is specified to remove redundancy caused by FDs. If T contains a node N such
that X ! N where X ae N , then replace N by N 0 where N 0 ae N , N 0 ! N , and for no N 00 ae N 0 does
In essence, each node N in T is replaced by one of its candidate keys defined in the usual
sense [Ram98], [SKS99]. 2
III. Comparison of the normal forms
In this section, we compare the normal forms with respect to generalizing 4NF and BCNF, reducing
redundant data values in a nested relation, and providing flexibility in nested relation schemes design.
Furthermore, we also examine their algorithms to see if they can generate nested relation schemes that
preserve the set of given MVDs and FDs. Another contribution here is providing a more general algorithm
for NNF [MNE96] than the ones in [ME96], [ME98].
A. Generalizing 4NF & BCNF
As mentioned in Section II-A, flat relation schemes are also nested relation schemes. Here, we show
that NNF [MNE96] , NNF [OY87a] , NNF [OY89] , and NNF [RK87] all imply 4NF with respect to the given set of
MVDs and FDs if the nested relation scheme is actually flat. Furthermore, each of the normal forms also
implies BCNF when there are only FDs. However, the converses of these results are not true for NNF [OY87a] ,
NNF [OY89] , and NNF [RK87] .
Theorem 1: Let U be a set of attributes. Let D be a set of MVDs and FDs over U . Let T be a single
node scheme tree such that Aset(T ) ' U . T is in NNF [MNE96] with respect to D if and only if T is in 4NF
with respect to D.
Proof. Theorem 6.1 in [MNE96]. 2
Lemma 1: Let U be a set of attributes. Let M be a set of MVDs over U . Let Z be a key of M and X ae Z.
There exists a V 2 DEP(X ) such that Z ae XV .
Proof. Lemma 3.5 in [OY87b]. 2
Lemma 2: Let U be a set of attributes. Let M be a set of MVDs over U . Let Z be a key of M . Z is in
4NF with respect to M .
Proof. Let X ae Z. By Lemma 1, there exists a V 2 DEP(X ) such that Z ae XV . Hence, X !! V i does not
split Z for every Therefore, Z is in 4NF with respect to M . 2
Theorem 2: Let U be a set of attributes. Let D be a set of MVDs and FDs over U . Let T be a single
node scheme tree such that Aset(T ) ' U . If T is in NNF [OY87a] with respect to D, then T is also in 4NF
with respect to D.
Proof. Since T is a single node scheme tree, it only consists of the root. By Condition 4 of NNF [OY87a] , the
root is a key of the set of MVDs M , which is defined in Definition 10. By Lemma 2, the root is in 4NF with
respect to M . By the definition of M , it is clear that the root is also in 4NF with respect to D. 2
Lemma 3: Let U be a set of attributes. Let D be a set of MVDs and FDs over U . Let E (D) be the
envelope set of D. Let R ' U . If R is in 4NF with respect to E (D), then R is also in 4NF with respect to
D.
Proof. Proposition 4.2 in [YO92]. 2
Theorem 3: Let U be a set of attributes. Let D be a set of MVDs and FDs over U . Let T be a single
node scheme tree such that Aset(T ) ' U . If T is in NNF [OY89] with respect to D, then T is also in 4NF
with respect to D.
Proof. Since T is a single node scheme tree, it only consists of the root. By Condition 4 of NNF [OY89] , the
root is a key of E (D). By Lemma 2, the root is in 4NF with respect to E (D). By Lemma 3, the root is also
in 4NF with respect to D. 2
Theorem 4: Let U be a set of attributes. Let D be a set of MVDs and FDs over U . Let T be a single
node scheme tree such that Aset(T ) ' U . If T is in NNF [RK87] with respect to D, then T is also in 4NF
with respect to D.
Proof. By Condition 4 of NNF [RK87] , the root K is a key of M 0 and is in LHS (M 0 ), where the set of MVDs
M 0 is defined in Definition 12. Following this, K is replaced by one of its candidate keys, namely T . Since
K is a key of M 0 , by Lemma 2, K is in 4NF with respect to M 0 . We now show that T is in 4NF with respect
to D. Assume not, then there is a nontrivial MVD X !! Y that holds for T with respect to D such that
implies an MVD X !! Z on U such that . We now claim that
is a nontrivial MVD that holds for K with respect to M 0 such that X
Therefore, K is not in 4NF with respect to M 0 , which is a contradiction. We first show that X + !! W
holds for K with respect to M 0 . Since D implies X !! Z, D implies X Z. By the definition of M 0 ,
holds for K with respect
to M 0 . We next show that X + !! W is nontrivial. Since X !! Y is nontrivial and holds for T , neither Y
nor is not a candidate key. Therefore, there is an
attribute A 2 Y such that X 6! A. Since A 2 Y and
Therefore, A 2 W . Since X 6! A, A 62 X . Similarly, there is an attribute B such that
is nontrivial on K. 2
However, the converses of Theorems 2, 3 and 4 are all false, as the following example shows.
Example 5: Let R = AB be a relation scheme and Bg be the given set of MVDs and FDs.
Trivially, R is in 4NF with respect to D. However, since D only contains a trivial MVD, each of the sets of
MVDs M , E (D), and M 0 as defined in Definitions 10, 11 and 12 respectively only contains trivial MVDs.
Thus, by Definition 9, none of these sets of MVDs has any key. Hence, R violates Conditions 4 of NNF [OY87a] ,
Notice the fact that NNF [MNE96] , NNF [OY87a] , NNF [OY89] , and NNF [RK87] all imply BCNF when only FDs
are given follow immediately from Theorems 1, 2, 3 and 4.
Example 5 sounds trivial; however, its implications cannot be underestimated. First, D is clearly equivalent
to the empty set of MVDs, which is vacuously conflict-free. Hence, NNF [OY87a] , NNF [OY89] , and NNF [RK87] ,
at least in their current forms, have difficulties in generating nested relation schemes with respect to conflict-free
sets of MVDs. Second, many-to-many relationships between two attributes, such as the one between A
and B in Example 5, arise naturally in practice. It is important for a normal form to be well-defined for
these simple situations. We will elaborate more on this subject in Section III-C.
We conclude this subsection by stating that NNF [MNE96] is superior to NNF [OY87a] , NNF [OY89] , and
NNF [RK87] in generalizing 4NF and BCNF.
Prof (Article-Title)* (Publication-Location)*
Steve Programming in C++ USA
Programming in Ada Hong Kong
Pat Programming in Ada USA
Hong Kong
Prof Article-Title Publication-Location
Steve Programming in C++ USA
Steve Programming in Ada USA
Steve Programming in C++ Hong Kong
Steve Programming in Ada Hong Kong
Pat Programming in Ada USA
Pat Programming in Ada Hong Kong
Fig. 5. Nested relation with redundancy caused by an MVD.
B. Reducing Redundant Data Values
In this subsection, each of the normal forms is investigated with respect to reducing redundant data values
in a nested relation. Two cases are considered: when the given set of MVDs is not conflict-free and when
the given set of MVDs is conflict-free.
B.1 Non Conflict-Free Sets of MVDs
Some terminology is needed here. Given a set D of MVDs and FDs over a set of attributes U , and a
scheme tree T such that Aset(T ) ' U , T is consistent with D if for each MVD X !! Y in MVD(T ), D
implies an MVD X !! Z on U such that scheme tree should be consistent with the
given MVDs and FDs; otherwise its scheme implies an MVD that does not follow from the given MVDs and
FDs. Hence, only consistent scheme trees are considered in this paper.
Theorem 5: Let U be a set of attributes. Let D be a set of MVDs and FDs over U . Let T be a scheme
tree such that Aset(T ) ' U . If T is consistent with D, then T is in NNF [MNE96] with respect to D if and
only if for every nested relation R on T , R does not have redundancy caused by any MVD or FD implied
by D that holds for T .
Proof. Follow immediately from Theorems 5.1 and 5.2 in [MNE96]. 2
Neither NNF [OY87a] , nor NNF [OY89] , nor NNF [RK87] has this property, as the following example shows,
which is Example 2.3.5 in [MNE96].
Example Publication-Locationg and let
Article-Title !! Prof g be the given set of MVDs. Consider the nested relation and its total unnesting in

Figure

5. There are redundant data values in the nested relation. For example, the last Hong Kong value
under (Publication-Location)* is redundant because if it is covered up, based on the MVD Article-Title !!
Publication-Location and the other data values in the nested relation, we can deduce that it must be Hong
Kong. Notice that M is not conflict-free because it violates Condition 2 of Definition 5. 2
If a scheme tree T violates Condition 1 or Condition 2 of NNF [MNE96] , then by Lemmas 5.2, 5.3 and 5.4 in
[MNE96], there exists a nested relation on T that has redundancy caused by an MVD that holds for T . The
Prof (Article-Title)* Prof (Publication-Location)*
Steve Programming in C++ Steve USA
Programming in Ada Hong Kong
Pat Programming in Ada Pat USA
Hong Kong
Fig. 6. Decomposition of nested relation in Fig. 5.
scheme of the nested relation in Figure 5 violates Condition 1 of NNF [MNE96] and Example 6 is designed to
show the redundancy. By Theorem 5, the nested relation scheme in Figure 5 violates NNF [MNE96] . However,
as stated in [MNE96], this nested relation scheme satisfies NNF [OY87a] , NNF [OY89] , and NNF [RK87] . From this
example, we can see that NNF [OY87a] , NNF [OY89] , and NNF [RK87] all allow nested relations with redundancy.
To satisfy NNF [MNE96] , the nested relation in Figure 5 needs to be decomposed into two smaller nested
relations, which are shown in Figure 6. The number of data values, however, increases from 9 to 11.
Therefore, decomposing the nested relation in Figure 5 cannot remove the redundant data values and thus
cannot reduce the number of data values. On the other hand, NNF [OY87a] , NNF [OY89] , and NNF [RK87] all
accept the nested relation in Figure 5 and without requiring it to be decomposed. In general, the paths of
a scheme tree have to be separated to satisfy NNF [MNE96] . When the given set of MVDs is not conflict-free,
it is beneficial not to separate the paths for some situations, as Example 6 shows. On the other hand, as
stated in [BK86], there is rarely a satisfactory solution to normalization with respect to non conflict-free sets
of MVDs.
Notice that there is no FD in Example 6. However, even if some FDs are added to Example 6, our
arguments still hold. Suppose we add an attribute Dept and an FD Prof ! Dept to Example 6. We also
modify the nested relation scheme in Figure 5 by adding Dept as a child to the root Prof. As in Figure 1, Steve
is a professor in the Mathematics Department and Pat is a professor in the Computer Science Department.
This new scheme tree still satisfies NNF [OY87a] and NNF [OY89] and it still violates NNF [MNE96] . Furthermore,
the modified nested relation and the nested relation in Figure 5 both have the same redundant data values.
Interestingly, if the given set of MVDs has the intersection property, then Conditions 1 and 2 of NNF [OY87a]
imply Condition 3 of NNF [OY87a] .
Theorem U be a set of attributes. Let M be a set of MVDs over U that has the intersection
property. Let T be a scheme tree such that Aset(T ) ' U . If T satisfies Conditions 1 and 2 of NNF [OY87a]
with respect to M , then T also satisfies Condition 3 of NNF [OY87a] with respect to M .
Proof. Suppose T does not satisfy Condition 3 of NNF [OY87a] . We shall derive a contradiction. Assume there
is an edge (V; W ) in T and there is a key X of M such that there exists a Z 2 DEP(X ) and Descendent(W )
Assume also that there are some sibling nodes W 1 , . , Wn of W in T such that Y
does not hold for T with respect
to M . Ancestor(V
Ancestor(V ); otherwise Ancestor(V ) !! Descendent(W ) on Aset(T ) is not left-reduced with respect to M
and thus T violates Condition 2 of NNF [OY87a] . Hence, X 6' Ancestor(V ). Since T satisfies Condition 1 of
implies an MVD Ancestor(V ) !! Z 0 on U such that Descendent(W
the nodes in T are pairwise disjoint,
is disjoint from both Z). By the intersection property
of M ,
proper subset of Ancestor(V ). Thus, Ancestor(V ) !! Descendent(W ) on Aset(T )
is not left-reduced with respect to M , which is a contradiction. 2
We conclude this subsection by stating that NNF [OY87a] , NNF [OY89] , and NNF [RK87] are all superior to
NNF [MNE96] in reducing redundant data values with respect to non conflict-free sets of MVDs. In addition,
if the given set of MVDs has the intersection property, then Condition 3 of NNF [OY87a] is redundant. This
implies that if the given set of MVDs is conflict-free, then we do not need to check for Condition 3 of
NNF [OY87a] since conflict-free sets of MVDs have the intersection property [BFMY83].
B.2 Conflict-Free Sets of MVDs
Here, we shall show that if a scheme tree T is in NNF [OY87a] with respect to a conflict-free set of MVDs,
then T is also in NNF [MNE96] . The converse of this result, however, is not true. Furthermore, if a scheme
tree T is consistent with a conflict-free set of MVDs, and each path (defined below) of T is in 4NF with
respect to M , then the nesting structure of T is able to squeeze out redundant data values. Since when
there is no given FD, NNF [OY87a] , NNF [OY89] , and NNF [RK87] are all equivalent, therefore, these results also
hold for NNF [OY89] and NNF [RK87] . Notice that we do not consider FDs here; instead, FDs are considered
in Section III-D.
Given a scheme tree T and a leaf node V of T , Ancestor(V ) is called a path of T . The set of paths of T
is denoted by Path(T ). Notice that this definition of a path is different from the one in [MNE96], in which
a path is defined as the list of nodes from V to the root of T . However, defining a path as Ancestor(V ) is
convenient for this paper.
Lemma 4: Let U be a set of attributes. Let M be a conflict-free set of MVDs over U . Let T be a scheme
tree such that Aset(T ) ' U . If T is in NNF [OY87a] with respect to M , then Path(T ) is in 4NF with respect
to M .
Proof. Stated in the conclusions of [OY87a]. 2
Lemma 5: Let U be a set of attributes. Let T be a scheme tree such that Aset(T ) ' U . If MVD(T ) does
not imply an MVD X !! Y on Aset(T ), then X !! Y splits a path of T .
Proof. Lemma 5.1 in [MNE96]. 2
Lemma U be a set of attributes. Let M be a conflict-free set of MVDs over U . Let T be a scheme
tree such that Aset(T ) ' U and is consistent with M . Let D be the set of MVDs implied by M that hold
for T . If Path(T ) is in 4NF with respect to M , then MVD(T ) implies D on Aset(T ).
Proof. As mentioned in Section II-B, a conflict-free set of MVDs allows a unique 4NF decomposition
[BFMY83]. Since Path(T ) is in 4NF with respect to M , which is conflict-free, and T is consistent with M ,
Path(T ) is the unique 4NF decomposition of Aset(T ) with respect to M . Now, suppose MVD(T ) does not
imply D. Then, there is an MVD X !! Y in D such that MVD(T ) does not imply X !! Y . By Lemma 5,
splits a path of T and thus Path(T ) is not a unique 4NF decomposition of Aset(T ) with respect to
M , which is a contradiction. 2
Notice that if the given set of MVDs is not conflict-free, then Lemma 6 does not hold, as demonstrated
by Example 6.
Theorem 7: Let U be a set of attributes. Let M be a conflict-free set of MVDs over U . Let T be a scheme
tree such that Aset(T ) ' U . If T is in NNF [OY87a] with respect to M , then T is also in NNF [MNE96] with
respect to M .
Proof. Since there is no given FD, we only need to show that T satisfies Condition 1 of NNF [MNE96] . Since
Condition 1 of NNF [OY87a] , T is consistent with M . Thus, the set D defined in Condition 1 of
NNF [MNE96] implies MVD(T ) on Aset(T ). By Lemma 4, Path(T ) is in 4NF with respect to M and then
by Lemma 6, MVD(T ) implies the set D defined in Condition 1 of NNF [MNE96] on Aset(T ). 2
Theorem 7 says that if a given set of MVDs is conflict-free, a nested relation scheme that is acceptable
to NNF [OY87a] is also acceptable to NNF [MNE96] . The converse of Theorem 7, however, is not true, as
demonstrated by Example 5 and Theorem 1. Notice that the given set of MVDs in Example 5 is equivalent
to the empty set of MVDs, which is clearly conflict-free.
Lemma 7: Let U be a set of attributes. Let M be a conflict-free set of MVDs over U . Let T be a scheme
tree such that Aset(T ) ' U . If T is in NNF [MNE96] with respect to M , then Path(T ) is in 4NF with respect
to M .
Proof. Assume there is a path P in Path(T ) such that P is not in 4NF with respect to M . Then there is a
nontrivial MVD X !! Y that holds for P . Since there is no given FD, MVD(T does not imply
Condition 1 of NNF [MNE96] . 2
When there is no given FD, the main cause of the problem of Examples 6 is that the given set of MVDs is not
conflict-free. If a set of MVDs is not conflict-free, there may be more than one possible 4NF decomposition.
Hence, even if each path of a scheme tree T is in 4NF, there may still be MVDs that hold for T which do
not follow from MVD(T ). These MVDs are the ones that cause the redundancy. Therefore, even after the
paths of a scheme tree are separated to satisfy NNF [MNE96] , the redundant data values remain.
This problem will not happen with conflict-free sets of MVDs. By Lemmas 4 and 6, if a scheme tree T is
in NNF [OY87a] , then all the MVDs that hold for T follow from MVD(T ). Thus, the nesting structure of T
is able to squeeze out the redundant data values. By Lemmas 6 and 7, NNF [MNE96] also has this property.
Since when there is no given FD, NNF [OY87a] , NNF [OY89] , and NNF [RK87] are all equivalent, NNF [OY89] and
NNF [RK87] both have this property.
Example 7: Let
Hobby-Equipmentg be the given set of MVDs. Notice that M is conflict-free. Consider the nested relation in

Figure

7. Its scheme violates NNF [MNE96] , NNF [OY87a] , NNF [OY89] , and NNF [RK87] because one of its paths,
namely Prof, Hobby, Hobby-Equipment, is not in 4NF with respect to M . Due to this violation, there are
redundant data values in the nested relation. As we can see, the equipments of hiking are stored twice in the
nested relation. After we decompose this nested relation into two smaller nested relations in Figure 8, the
redundant data values are removed. Notice that every path of the two nested relation schemes in Figure 8
is in 4NF and both nested relation schemes satisfy NNF [MNE96] , NNF [OY87a] , NNF [OY89] , and NNF [RK87] . 2
We conclude this subsection by stating that when no FD is given, NNF [MNE96] , NNF [OY87a] , NNF [OY89] ,
and NNF [RK87] are all able to reduce redundant data values with respect to conflict-free sets of MVDs.
Furthermore, if there is no given FD, NNF [OY87a] implies NNF [MNE96] with respect to conflict-free sets of
MVDs. The same results hold for NNF [OY89] and NNF [RK87] .
Prof (Student)* (Hobby (Hobby-Equipment)*
Pat Lee Hiking Water Bottle
Hat
Steve Carter Hiking Water Bottle
Hat
Dance Dancing Shoe
Costume
Chi-Ming null null
Fig. 7. Nested relation with redundancy caused by an MVD.
Prof (Student)* (Hobby)* Hobby (Hobby-Equipment)*
Pat Lee Hiking Hiking Water Bottle
Steve Carter Hiking Hat
Dance Dance Dancing Shoe
Chi-Ming null Costume
Fig. 8. Decomposition of nested relation in Fig. 7.
C. Design Flexibility
Here, we show several examples to illustrate how flexible each of the normal forms is in nested relation
schemes design. It turns out that NNF [MNE96] allows greater flexibility in nested relation schemes design
than NNF [OY87a] , NNF [OY89] and NNF [RK87] .
Example 8: Let us replace A by Child and B by Toy in Example 5. The following three nested relation
schemes Child Toy, Child (Toy)*, and Toy (Child)* are all in NNF [MNE96] vacuously. Choosing which one
to use, of course, depends on the application in hand. However, since there is no "key," as mentioned in
Example 5, all of these nested relation schemes violate NNF [OY87a] , NNF [OY89] , and NNF [RK87] . Notice that
many-to-many relationships, such as the one between Child and Toy, occur commonly. 2
Example 9: Let Hobby-Equipmentg be the
given set of MVDs. Notice that M is conflict-free. The only nested relation scheme allowed by NNF [OY87a] ,
NNF [OY89] , and NNF [RK87] is Hobby (Prof )* (Hobby-Equipment)* since Hobby is the only key. In this nested
relation scheme, data are forced to be stored in the point of view of Hobby, which is fine if this is what the
application in hand dictates. Notice that this nested relation scheme also satisfies NNF [MNE96] . Now suppose
we need to store the data in the point of view of Prof and the nested relation schemes that are needed are
Prof (Hobby)* and Hobby (Hobby-Equipment)*. Both of these nested relation schemes satisfy NNF [MNE96] .
However, since Prof is not a key, Prof (Hobby)* violates Conditions 4 of NNF [OY87a] , NNF [OY89] , and
NNF [RK87] . 2
We now turn to an example that involves FDs.
Example 10: As discussed in [MNE96], the scheme tree in Figure 3 is in NNF [MNE96] , but it violates
NNF [OY87a] , NNF [OY89] and NNF [RK87] . There are several violations. Since the rationale behind the violations
for NNF [OY89] and NNF [RK87] is quite similar to that of NNF [OY87a] , we focus on NNF [OY87a] .
We now argue that Matriculation cannot be an inner node in the scheme tree. Consider the set of attributes
Descendent(Matriculation), which is equal to fMatriculation, Student, Interestg. Student is in
FK (Descendent(Matriculation)) because Student is a key and is contained in Descendent(Matriculation).
However, since Matriculation is not a key, therefore it is not in FK (Descendent(Matriculation)) and thus
the scheme tree violates a subcondition of Condition 4 of NNF [OY87a] . Moreover, Dept Chair cannot be the
root since Dept Chair is not a key. Therefore, the scheme tree violates another subcondition of Condition 4
of NNF [OY87a] . With some work, the reader can check that these two violations also apply for NNF [OY89]
and NNF [RK87] . 2
Observe that Examples 8, 9 and 10 are all quite natural and reasonable. Unlike Example 6, these examples
are easily created and are all very practical. By these examples, we can see that Conditions 4 of both
NNF [OY87a] and NNF [OY89] are the most problematic and NNF [RK87] inherits the same problem. Due to these
limitations, NNF [OY87a] , NNF [OY89] and NNF [RK87] all restrict attribute clustering and design flexibility. We
conclude this subsection by stating that NNF [MNE96] provides greater design flexibility than the other three
normal forms.
D. Algorithms & Nested Database Schemes
In this subsection, we first present an algorithm that generates scheme trees in NNF [MNE96] from an
acyclic database scheme and a set of FDs where each given FD is embedded in a relation scheme in the given
database scheme (defined below). This algorithm generalizes the algorithms in [ME96], [ME98], in which
only fl-acyclic database schemes are considered [Fag83]. The acyclic database schemes that we consider in
this paper, however, are ff-acyclic database schemes, which are the most general type of acyclic database
schemes [Fag83]. In Section II-B, some of the numerous equivalent definitions of ff-acyclic database schemes
are presented. To avoid being too wordy, however, "an acyclic database scheme" simply means "a ff-acyclic
database scheme" in this paper. After presenting the algorithm of NNF [MNE96] , we shall compare the
algorithms of all of the normal forms and the nested database schemes that they generate.
In addition to the assumptions that the given database scheme is acyclic and each given FD is embedded
in a relation scheme of the given database scheme, we also assume that each relation scheme is in BCNF
with respect to the given FDs. These assumptions are justified as follows. First, in Section II-B, we have
already mentioned the importance of acyclic database schemes. Second, as stated in [FMU82], most FDs
that are relevant for data structuring are embedded in some relation schemes of the given database scheme.
Furthermore, most FDs that are derived from the semantic data models that we use in [ME96], [ME98]
are indeed embedded in some relationship sets which roughly correspond to relation schemes in this paper.
Third, as stated in [ME98], in most cases relation schemes are of small arity and a majority of them are
binary, thus we believe that most relation schemes in practice are in BCNF.
D.1 Algorithm for NNF [MNE96]
We now present Algorithm 1, which is the algorithm that generates nested relation schemes in NNF [MNE96] .
Example 11: Consider the set U of attributes, the set M of MVDs, and the set F of FDs in Figure 4.
To save space, we abbreviate Dept as D, Chair as C, Prof as P , Hobby as H , Hobby-Equipment as E,
Matriculation as M , Student as S, and Interest as I . Notice that M and F is equivalent to 1R and F where
g.
At Step 1, a join tree J of R is derived and is shown in Figure 9. Initially all the nodes in J are unmarked.
At Step 2.1, suppose DC is selected as the seed relation scheme (R seed ) of a new scheme tree and the single
path scheme tree TDC is simply created as DC. The node DC in J is then marked and is entered into L.
Algorithm 1
Input: An acyclic database scheme and a set of nontrivial FDs F where each
in F is embedded in a R i (XY ' R i ). Furthermore, each R i is in BCNF with respect to F .
Without loss of generality, no R i is a subset of another R j if i 6= j.
Nested relation schemes that are in NNF [MNE96] with respect to R and F .
Internal Data Structure: A join tree J of R and a first-in first-out queue L of relation schemes that is initially
empty.
1 Use the Graham Reduction to derive J from R [Mai83]. We begin with the graph with nodes R 1 ,
. , Rn and with no edge. Let R 0
i be R i after applying zero or more node removals. Each time R 0
is removed because R 0
add an edge between R i and R j in the graph. Eventually
be added to the graph and the resulting graph is J . Notice that since there may
be more than one possible reduction sequences, an acyclic database scheme may have more than
one join trees.
2 While there is an unmarked node in J , do:
2.1 Select an unmarked node R seed in J . Create a single path scheme tree TR seed
from R seed .
Mark R seed and enter R seed into L.
2.2 While L is not empty, do:
2.2.1 Let RM be the first marked relation scheme in L. Remove RM from L.
2.2.2 For each unmarked neighbor RU of RM in J , do:
2.2.2.1 If there is a node N in TR seed
such that RU ! Ancestor(N ) and
are several nodes that satisfy these
conditions, choose the lowest one.), modify TR seed
as follows:
2.2.2.1.1 If Ancestor(N Otherwise,
create a single path scheme tree TRU from (RU \Gamma RM ) and
attach the root of TRU as a child of N .
2.2.2.1.2 Mark RU and enter RU into L.
3 A scheme tree T produced in Step 2 can be modified by moving an attribute A in Aset(T ) up or
down the nodes in the path that A appears as long as T satisfies Condition 2 of NNF [MNE96] and
remains the same.
At Step 2.2.1, RM becomes DC and it has one unmarked neighbor DP in J . The node N in Step 2.2.2.1 is
DC and at Step 2.2.2.1.1, P is attached as a child of DC. DP is then marked and is entered into L. Back
at Step 2.2.1, RM becomes DP and it has two unmarked neighbors PH and SP in J . Successively H and S
become children of P in TDC and both PH and SP are marked and are entered into L. Back at Step 2.2.1,
RM becomes PH and it has one unmarked neighbor HE. Since there is no node N in TDC such that HE !
Ancestor(N ), we cannot extend the path that contains H . Back at Step 2.2.1, RM becomes SP and it has
two unmarked neighbors SI and SM in J . For SI, the node N in Step 2.2.2.1 is S and I becomes a child of
S in TDC . For SM, the node N in Step 2.2.2.1 is also S. But since Ancestor(N we put the attribute
M into the node N and thus the node N becomes SM. Notice that in this example, the order of choosing
unmarked neighbors at Step 2.2.2 does not make a difference in TDC . The only unmarked node left in J is
HE and thus in the second iteration of Step 2, a single path scheme tree created from HE is generated and
Fig. 9. Join tree of join dependency in Example 11.
Fig. 10. Join tree of join dependency in Example 12.
then HE is marked. In Step 3, we may choose to move M as a parent of S in TDC and Algorithm 1 has
generated the scheme tree in Figure 3. 2
The database scheme R in Example 11 is fl-acyclic. The following example shows that Algorithm 1 is able
to generate scheme trees in NNF [MNE96] from an ff-acyclic, but not fl-acyclic, database scheme.
Example 12: Let ACEg. The join tree generated at Step 1
is shown in Figure 10. Suppose we select ABC as the seed relation scheme and the single path scheme tree
TABC created at Step 2.1 is AC - B. ABC has only one unmarked neighbor ACE. Later E becomes a child
of AC in TABC . As the reader may verify, CDE and AEF cannot be attached to TABC . In the second and
the third iterations of Step 2, two single path scheme trees are created from CDE and AEF respectively.
Notice that CDE and AEF cannot appear in the same scheme tree in this example because they are not
neighbors in the join tree in Figure 10. 2
The concept of a closed set of relation schemes is crucial to the proof of correctness of Algorithm 1. Let
be a database scheme over a set of attributes U . Let S ' R and let S be [R i 2S R i . S is
closed if for every R i 2 R, there is a R k 2 S such that R i " S ' R k . Notice that if R is acyclic, then any
closed set of relation schemes of R is also acyclic [BFMY83].
Also, the proof of correctness of Algorithm 1 depends on Lemmas 8 and 10 as well, which characterize the
set of MVDs and the set of FDs that hold for a scheme tree generated by Algorithm 1.
Let 1R be a join dependency is a database scheme over a set of attributes U .
1R implies numerous MVDs. However, every MVD implied by 1R is also implied by an MVD in MVD(1R).
MVD(1R) is a set of MVDs of the form 1f[ i2S1 R ng and
As shown in Chapter 13 in [Mai83], R is acyclic if and only if MVD(1R) and 1R are equivalent.
Lemma 8: Let U be a set of attributes. Let be a database scheme over U . Let S ' R
and let S be [R i 2S R i . If S is closed and D is the set of MVDs that hold for S with respect to 1R, then D
is equivalent to MVD(1S ).
Proof. Let X !! Y be an MVD implied by 1R where X ' S. Thus, X !! (Y " S) is in D. X !! Y is
equivalent to the join dependency 1fXY, X (U \Gamma XY )g. 1R implies 1fXY, X (U \Gamma XY )g if and only if R i
' XY or R i Hence, for each R i in S, R i ' XY or R i ' X (U \Gamma XY )g. Thus,
1 For every MVD X !! Y on U , X !! Y is equivalent to the join dependency 1fXY, X (U \Gamma XY )g. 1R implies 1fXY,
only if R i
' XY or R i
implied by an MVD
in MVD(1R).
implied by MVD(1S ). Now consider an MVD V !! W in MVD(1S ), which is equivalent
to the join dependency 1fVW, V (S \Gamma VW )g. Let us construct an MVD implied by 1R which is denoted
by 1fL, Rg. Initially, As we add the relation schemes in R \Gamma S to either
the L set or the R set, since S is closed, L " R is always equal to V . Thus, 1R implies an MVD V !! Z on
U such that
In the following, if G is a set of FDs and W is a set of attributes, then G[W Wg.
Lemma 9: Let be a database scheme. Let F be a set of FDs such that each FD in F
is embedded in a R i . 1R and F implies an FD X ! Y if and only if F implies
Proof. Lemma 1 in [GY84]. 2
Lemma 10: Let U be a set of attributes. Let be an acyclic database scheme over U
and let J be a join tree of R. Let F be a set of FDs over U such that each FD in F is embedded in a R i .
Let J 0 be a connected subtree of J . Let S be the set of nodes (relation schemes) in J 0 and let S be [R i 2S R i .
If D is the set of FDs that hold for S with respect to 1R and F , then D is equivalent to [R i
Proof. By Lemma 9, 1R has nothing to do with closures of sets of attributes. The if-part is obvious because
for each R i 2 We proceed to the only-if part. Without loss of generality, assume the
right-hand side of every FD in F is a single attribute. We first show that if W
embedded in a relation scheme in S. Assume not, we shall derive a contradiction. Let RB
be a relation scheme in R \Gamma S such that WB ' RB . Since J 0 is connected, there is a unique node (relation
R u in J 0 such that among all the nodes in J 0 , R u is the closest node to RB . By Condition 2 of
Definition 6, for each R j 2 S, R j " RB ' R u . Now, since WB ' S, therefore WB ' R u , which is a
contradiction.
A be an FD in D. Since X ! A 2 D, XA ' S and there is a derivation sequence Z of X ! A
by using the FDs in F . Let Z be the following derivation sequence:
A.
If each A i that appears in Z is in S, then all V i 's are subsets of S. This implies that every V i A i is a subset
of S. Thus, by what we have just proved, each embedded in a relation scheme in S and the proof
is done. Now assume some A i 's are not in S. Suppose A p is the first such attribute in Z. Since
and A 2 S, there is a A q that appears in Z such that A 1 2 S, . , A
and A q 2 S. Let RA i
be a relation scheme in R that embeds connected and RAp is not
a node in J 0 , Z can be arranged in such a way that V p+1 , . , V q all contain some of these attributes A p ,
. , A q\Gamma1 . This implies that we can arrange Z such that RAp , . , all belong to the same remaining
connected subtree J 00 after we remove all the nodes in J 0 from J and all the edges in J that are incident on
the nodes in J 0 . Since J 0 is a connected subtree, there is a unique node R v in J 0 such that among all the
nodes in J 0 , R v is the closest node to any node in J 00 . We now show by induction that X
Basis: Since A 1 2 S, . , A and RAp is in J 00 , RAp 62 S; therefore by
Condition 2 of Definition 6,
Induction: Assume X l , for every l where p  l ! q. Now consider l 1. By the construction
of Z, V l+1 ' A p . A l X
, which is not a node in J 0 , V l+1 '
RA l+1
. This implies that V l+1 ' A p . A l (X
). But since RA l+1
is not a node in J 0 and X
' S, by Condition 2 of Definition 6, X
R v ). By the induction hypothesis, X and we conclude that
Now since V q ! A q is embedded in R q , R q
By using the same reasoning, it is possible to show that for each
implied by [R i
Lemma 11: Let U be a set of attributes. Let T be a scheme tree such that Aset(T ) ' U . MVD(T ) is
equivalent to the join dependency 1Path(T ) on Aset(T ).
Proof. Proposition 4.1 in [OY87a]. 2
Lemma 12: All the nodes in TR seed
that satisfy the conditions in Step 2.2.2.1 are on the same path.
Proof. Assume there are two nodes N and N 0 that satisfy the conditions. That is, RU
This implies that
and RM are neighbors in J , RU "
Aset(TR seed
) and since every given FD is embedded in a relation scheme of the given database scheme, RU
only if
will force N and N 0 to be on the same path at Step 2.2.2.1.1. 2
In the following proof, we assume the reader is familiar with the chase, which is described in Chapter 8 in
[Mai83].
Theorem 8: Algorithm 1 is correct.
Proof. It is obvious that Step 1 generates a join tree for the given acyclic database scheme. Next we show
that every tree generated by Algorithm 1 satisfies Definitions 1 and 4. In particular, we show that the nodes
in a generated tree are all nonempty and are pairwise disjoint. By assumption, no relation scheme is a
subset of another relation scheme in the given database scheme. Also, since RU and RM are neighbors in
the derived join tree, RU " seed
which is not empty, does not
intersect with Aset(TR seed
). Furthermore, the single path scheme trees generated at Steps 2.1 and 2.2.2.1.1
thus they do not have empty node. Step 3 simply will not violate these two
definitions. Thus, Algorithm 1 generates trees that satisfy Definitions 1 and 4.
Obverse that Algorithm 1 generates a scheme tree from the nodes in a connected subtree of the derived
join tree. Since the nodes in a connected subtree constitutes a closed set of relation schemes, Algorithm 1
generates a scheme tree from a closed set of relation schemes. In fact, this is exactly the purpose of the join
tree created at Step 1. As an example, fCDE, AEFg in Example 12 is not a closed set of relation schemes
and thus CDE and AEF cannot appear in the same scheme tree. The purpose of the first-in first-out queue
in Algorithm 1, however, is to ensure that a scheme tree is built level by level.
Next we need to characterize the set D of MVDs and FDs that hold for a scheme tree T generated by
Algorithm 1. Let S be the closed set of relation schemes from which T is constructed and let S be [R i 2S R i .
Thus, Aset(T ) is equal to S. It turns out that D is equivalent to [R i 1S. The proof is as
follows. D implies [R i the given database scheme R is acyclic and
S is closed, S is acyclic. Thus, MVD(1S ) and 1S are equivalent. However, since S is closed, by Lemma 8,
Therefore, D implies 1S. We now consider the reverse implication. By Lemma 10, the
set of FDs in D is equivalent to [R i Y be an MVD in D. By the definition of D,
R and F imply an MVD X !! Z on U (= [R i 2RR i ) such that X ' S, and us run the
chase on the tableau TXZ for X !! Z. TXZ has two rows r 1 and r 2 . r 1 has a's under XZ-columns and b's
elsewhere and r 2 has a's under X(U \Gamma XZ)-columns and b's elsewhere. Since R and F imply X !! Z on
U , by Lemma 9, we can assume that we apply the FDs in F until no more b can be changed into a, and
then for every R ag or R i ' ag. This statement also holds for every
using the FDs in [R i instead of the FDs in F . By Lemma 9
again, the FDs in [R i are strong enough to ensure that for every R i 2 S, R i ag or
ag. Thus, [R i imply X !! Y on S.
We are now ready to prove by induction that a scheme tree T generated by Algorithm 1 is in NNF [MNE96] .
The induction is on the size of S, which is denoted by jSj.
Basis: When is created at Step 2.1. MVD(T ) is a set of trivial MVDs and thus is equivalent
to 1S, which is a trivial join dependency. By definition, FD(T ) is equivalent to [R i
Condition 1 of NNF [MNE96] . By assumption, every given relation scheme is in BCNF. Hence, T
also satisfies Condition 2 of NNF [MNE96] . At Step 3, Path(T ) remains the same and thus T still satisfies
NNF [MNE96] .
Induction: Assume the statement is true for every closed set of relation schemes S of R where 1  jSj  k.
Now consider when 1. In the connected subtree J 0 from which S is defined, let N k+1 be a node in
J 0 that has exactly one neighbor in J 0 . We denote the scheme tree before N k+1 is added by TS \GammaN k+1
and
the scheme tree after N k+1 is added by TS . The goal is to show that MVD(T S
to [R i 1S. Observe that FD(T S ) is equivalent to [R i 2S F
is equivalent to the join dependency 1Path(T ) on Aset(T ) for any scheme tree T . Hence, 1S implies
for each R i in S, there is a path P in Path(T S ) such that R i ' P . Therefore, we are
left to show that 1Path(T S us run the chase on the tableau T1S for 1S. Notice
that T1S has all the rows in T1S \GammaN k+1
, which is the tableau for 1(S \Gamma N k+1 ). Observe that FD(T S \GammaN k+1
' FD(T S ). By the induction hypothesis, 1Path(T S \GammaN k+1
consider adding N k+1 into TS \GammaN k+1
. By Lemma 12, there is only one node N in TS \GammaN k+1
that satisfies the
conditions at Step 2.2.2.1. One more path will be added to TS \GammaN k+1
or the paths
that contain N will be enlarged if Ancestor(N These changes can be done in T1S by using the
FDs in [R i which is equivalent to FD(T S ). Thus, for each path P in Path(T S ), there is a row r
in T1S such that P ' fC j ag. Therefore, 1Path(T imply 1S and thus MVD(T
imply 1S. Hence, Condition 1 of NNF [MNE96] is satisfied. T satisfies Condition 2 of NNF [MNE96] is
implied by the fact that every given relation scheme is in BCNF and by the conditions in Step 2.2.2.1. At
remains the same and thus T still satisfies NNF [MNE96] . 2
A (B (C )*
3Fig. 11. The instance I on scheme A(B(C ) ) .
D.2 Advantages of FDs
We first discuss how FDs can be used in constructing large scheme trees, and thus big clusters of data. If
with the MVD B !! C and T is a scheme tree with A as the root, B as the child of A, and C
as the child of B, then B !! C holds for T . The redundancy caused by this MVD can be easily seen in the
instance I on A(B(C ) )  in Figure 11.
For I , we can cover the data f3, 4g in the first nested tuple under (C) , and we can tell that it must be
f3, 4g by using the MVD B !! C and the other data values in I . A(B(C ) )  is not in NNF [MNE96] with
respect to U and B !! C, neither is it in NNF [OY87a] , nor in NNF [OY89] , nor in NNF [RK87] . However, with
an additional FD B ! A, this redundancy cannot happen. In this example, I violates B ! A since the
B-value 1 associates with two A-values, 5 and 6. In fact, with this FD, no data instance that satisfies the
MVD and the FD in this example can have redundancy. A(B(C ) )  is in NNF [MNE96] with respect to U
and the dependencies B !! C and B ! A. However, A(B(C does not satisfy NNF [OY87a] , NNF [OY89] ,
and NNF [RK87] even in the presence of the FD B ! A.
Since NNF [OY87a] and NNF [OY89] do not take advantages of FDs, as opposed to NNF [MNE96] , their definitions
lead to small scheme trees and thus small clusters of data. In particular, removing partial dependencies,
as defined in Conditions 2 of NNF [OY87a] and NNF [OY89] , regardless of the given FDs, is the main cause of
this problem. For example, the scheme tree in Figure 3 has partial dependencies with respect to NNF [OY87a]
and NNF [OY89] . Consider the edge (Student, Interest). Ancestor(Student) !! Descendent(Interest) is not
left-reduced and thus the scheme tree violates Condition 2 of NNF [OY87a] , and with some work, we can also
show that the scheme tree violates Condition 2 of NNF [OY89] because of the same edge (Student, Interest).
Using the same reasoning, Ancestor(Prof ) !! Descendent(Hobby) is also not left-reduced with respect to
NNF [OY87a] and NNF [OY89] . To remove these partial dependencies, which do not cause any data redundancy
in the presence of the given FDs in Figure 4, the algorithms of NNF [OY87a] and NNF [OY89] decompose more
than necessary and generate small scheme trees. To be more specific, a scheme tree with P as the root and H
and S as the children of P will be generated by their algorithms. Furthermore, the algorithm of NNF [RK87]
will also generate more than one scheme tree for this example because of the way they handle FDs.
In short, NNF [OY87a] , NNF [OY89] , and NNF [RK87] do not take full advantages of FDs in constructing large
scheme trees while NNF [MNE96] does.
D.3 Dependency Preservation
In addition to characterizing data redundancy, another property of interest of nested database schemes
is dependency preservation. In this subsection, we mainly focus on NNF [MNE96] and NNF [OY89] and their
algorithms.
Some definitions are needed here. Let D be a set of MVDs and FDs over a set of attributes U . A
dependency preserving if there is a
set F of FDs such that each FD in F is embedded in a R i , and 1R [ F is equivalent to D on U [YO92].
Furthermore, conditions are defined for D to be extended conflict-free [YO92]. One interesting property,
among many others, is that if D is an extended conflict-free set of MVDs and FDs over U , then there
is an acyclic and dependency preserving 4NF decomposition of U with respect to D (Proposition 5.1 in
[YO92]). Now, using the decomposition algorithm in [OY89], a set of scheme trees fT 1 , . , Tm g, m  1,
is generated from the given set D of MVDs and FDs and the set of all the attributes U . According to
Proposition 6.3 in [OY89], if D is extended conflict-free, then [ m
is an acyclic and dependency
preserving decomposition of U with respect to D.
In the following theorem, we show that Algorithm 1 also has this property.
Theorem 9: Algorithm 1 generates a nested database scheme that is dependency preserving with respect
to an extended conflict-free set of MVDs and FDs D.
Proof. Since D is extended conflict-free, according to Proposition 5.1 in [YO92], D is equivalent to 1R [
F where R is an acyclic 4NF database scheme and F is a set of FDs such that each FD in F is embedded
in a relation scheme in R. R is in 4NF implies R is in BCNF. Hence, D satisfies the input requirements
of Algorithm 1. Assume Algorithm 1 generates m scheme trees T 1 , . , Tm from m closed sets of relation
schemes S 1 , . , Sm of R. By the construction of Algorithm
Consider running the chase
on the tableau T1R for 1R. By Theorem 8, MVD(T equivalent to [R i 2S j
m. Therefore, MVD(T S 1
equivalent to 1[ m
and F , which is equivalent to 1R [ F , and in turn is equivalent to D. 2
Thus, if a given set of MVDs and FDs is extended conflict-free, the decomposition algorithm in [OY89]
and Algorithm 1 both produce a nested database scheme that is dependency preserving.
IV. Conclusions
Here, we summarize the results of this paper. First, NNF [MNE96] is superior to NNF [OY87a] , NNF [OY89] ,
and NNF [RK87] in generalizing 4NF and BCNF. Second, with respect to non conflict-free sets of MVDs,
NNF [OY87a] , NNF [OY89] , and NNF [RK87] are all superior to NNF [MNE96] in reducing redundant data values.
In addition, Condition 3 of NNF [OY87a] is redundant with respect to sets of MVDs that have the intersection
property. Third, when no FD is given and the given set of MVDs is conflict-free, NNF [MNE96] , NNF [OY87a] ,
NNF [OY89] , and NNF [RK87] are all able to reduce redundant data values and NNF [OY87a] NNF [OY89] , and
NNF [RK87] all imply NNF [MNE96] . However, NNF [MNE96] does not imply NNF [OY87a] , or NNF [OY89] , or
NNF [RK87] . Fourth, NNF [MNE96] provides greater design flexibility than the other three normal forms. Fifth,
NNF [OY87a] , NNF [OY89] , and NNF [RK87] do not take full advantages of FDs in creating large scheme trees
while NNF [MNE96] does; and finally sixth, the algorithms of NNF [MNE96] and NNF [OY89] both are dependency
preserving with respect to extended conflict-free sets of MVDs.



--R

On the desirability of acyclic database schemes.
An integrated approach to logical design of relational database schemes.
Multivalued dependencies and a new normal form for relational databases.
Degrees of acyclicity for hypergraphs and relational database schemes.
A simplified universal relation assumption and its properties.
Independent database schemas.
Bringing object/relational down to earth.
NF-NR: A practical normal form for nested relations.
The Theory of Relational Databases.
Transforming conceptual models to object-oriented database designs: Practicalities
Using nnf to transform conceptual data models to object-oriented database designs
A normal form for precisely characterizing redundancy in nested relations.
A new normal form for nested relations.
Reduced mvds and minimal covers.
On the normalization in nested relational databases.
Database Management Systems.
The design of :1nf relational databases into nested normal form.
Extended algebra and calculus for nested relational databases.


Database System Concepts.
Object normal forms and dependency constraints for object-oriented schemata
Oracle8 PL/SQL Programming.
Unifying functional and multivalued dependencies for relational database design.
--TR

--CTR
Emanuel S. Grant , Rajani Chennamaneni , Hassan Reza, Towards analyzing UML class diagram models to object-relational database systems transformations, Proceedings of the 24th IASTED international conference on Database and applications, p.129-134, February 13-15, 2006, Innsbruck, Austria
Hai Zhuge, Fuzzy resource space model and platform, Journal of Systems and Software, v.73 n.3, p.389-396, November-December 2004
Hai Zhuge, Resource space model, its design method and applications, Journal of Systems and Software, v.72 n.1, p.71-81, June 2004
Wai Yin Mok, Designing nesting structures of user-defined types in object-relational databases, Information and Software Technology, v.49 n.9-10, p.1017-1029, September, 2007
Sven Hartmann , Sebastian Link , Klaus-Dieter Schewe, Functional and multivalued dependencies in nested databases generated by record and list constructor, Annals of Mathematics and Artificial Intelligence, v.46 n.1-2, p.114-164, February  2006
data redundancy;nested normal forms;nested databases;acyclic database schemes;design flexibility;algorithms;object-relational database management systems;object-relational databases;nested database design;nested database schemes;nested relations;conflict-free sets of MVDs;nested relation schemes;SQL:1999