Justification for Inclusion Dependency Normal Form.
AbstractFunctional dependencies (FDs) and inclusion dependencies (INDs) are the most fundamental integrity constraints that arise in practice in relational databases. In this paper, we address the issue of normalization in the presence of FDs and INDs and, in particular, the semantic justification for Inclusion Dependency Normal Form (IDNF), a normal form which combines Boyce-Codd normal form with the restriction on the INDs that they be noncircular and key-based. We motivate and formalize three goals of database design in the presence of FDs and INDs: noninteraction between FDs and INDs, elimination of redundancy and update anomalies, and preservation of entity integrity. We show that, as for FDs, in the presence of INDs being free of redundancy is equivalent to being free of update anomalies. Then, for each of these properties, we derive equivalent syntactic conditions on the database design. Individually, each of these syntactic conditions is weaker than IDNF and the restriction that an FD not be embedded in the righthand side of an IND is common to three of the conditions. However, we also show that, for these three goals of database design to be satisfied simultaneously, IDNF is both a necessary and sufficient condition.
Introduction
Functional dependencies (FDs) [Arm74, Mai83, Ull88, AA93] generalise the notions of entity integrity
and keys [Cod79] and inclusion dependencies (INDs) [Mit83, CFP84] generalise the notions
of referential integrity and foreign keys [Cod79, Dat86]. In this sense FDs and INDs are the most
fundamental data dependencies that arise in practice.
Relational database design in the presence of FDs is an established area in database theory,
which has been researched for over twenty years [Cod74, BB79, Mai83, Ull88, AA93]. The semantic
justification of the normal forms in the presence of FDs is well-understood in terms of eliminating
the so called update anomalies and redundancy problems that can arise in a relation satisfying
a set of FDs [BG80, Fag81, Cha89, Vin94, Vin98]. The advice that is given as a result of this
investigation of the semantics of the normal forms is that in order to eliminate the above mentioned
problems we should design database schemas which are in Boyce-Codd Normal Form (BCNF)
[Cod74].
Despite the importance of INDs as integrity constraints little research has been carried out on
how they should be integrated into the normalisation process of a relational database. Such an
integration is fundamental to the success of a design, since the enforcement of referential integrity
is no simple matter [CTF88]. Normal forms which include FDs and INDs have been considered in
[CA84, MR86, LG92, MR92, BD93] but necessary and sufficient conditions in terms of removing
the update anomalies and redundancy problems were not given. It is our goal in this paper to
fill in this gap by providing sufficient and necessary semantics for Inclusion Dependency Normal
We consider some of the problems that occur in the presence of FDs and INDs through two
examples. The first example illustrates the situation when an attribute is redundant due to
interaction between FDs and INDs.
Example 1.1 Let HEAD be a relation schema, with attributes H and D, where H stands for head
of department and D stands for department, and let LECT be a relation schema, with attributes
L and D, where L stands for lecturer and as before D stands for department. Furthermore, let
Dg be a set of FDs over a database schema
stating that a head of department manages a unique department and a lecturer works in a unique
department, and I = fHEAD[HD] ' LECT[LD]g be a set of INDs over R stating that a head of
department also works as a lecturer in the same department. We note that I [
logical implication, by the pullback inference rule (see
Proposition 2.1), and thus the FD HEAD in F is redundant. Also, note that we have not
assumed that HEAD : D ! H in F and thus a department may have more than one head.
Two problems arise with respect to R and F [ I. Firstly, the interaction between F and I
may lead to the logical implication of data dependencies that were not envisaged by the database
designer and may not be easy to detect; in general the implication problem for FDs and INDs is
intractable (see the discussion in Section 2). In this example the pullback inference rule implies
that an FD in F is redundant.
Secondly, the IND HEAD[HD] ' LECT[LD] combined with the FD LECT imply that
the attribute D in HEAD is redundant, since the department of a head can be inferred from the fact
that L is a key for LECT. (Formally this inference can be done with the aid of a relational algebra
expression which uses renaming, join and projection; see [Mai83, Ull88, AA93] for details on the
relational algebra.) Thus HEAD[HD] ' LECT[LD] can be replaced by HEAD[H] ' LECT[L] and
the attribute D in HEAD can be removed without any loss of information.
The second example illustrates the situation when the propagation of insertions due to INDs
may result in the violation of entity integrity.
Example 1.2 Let EMP be a relation schema, with attributes E and P, where E stands for employee
name and P stands for project title, and let PROJ be a relation schema, with attributes P
and L, where as before P stands for project title and L stands for project location. Furthermore,
Pg be a set of FDs over a database schema stating
that an employee works on a unique project, and I = fEMP[P] ' PROJ[P]g be a set of INDs over
R stating that an employee's project is one of the listed projects. We note that a project may
be situated in several locations and correspondingly a location may be associated with several
projects and thus fP, Lg is the primary key of PROJ.
The problem that arises with respect to R and F [ I is that the right-hand side, P, of the IND
EMP[P] ' PROJ[P] is a proper subset of the primary key of PROJ. Let r 1 and r 2 be relations
over EMP and PROJ, respectively. Suppose that an employee is assigned to a new project which
has not yet been allocated a location and is thus not yet recorded in r 2 . Now, due to the IND in
I, the insertion of the employee tuple into r 1 , having this new project, should be propagated to r 2
by inserting into r 2 a tuple recording the new project. But since the location of the project is still
unknown, then due to entity integrity, it is not possible to propagate this insertion to r 2 .
We summarise the problems that we would like to avoid when designing relational databases in
the presence of FDs and INDs. Firstly, we should avoid redundant attributes, secondly we should
avoid the violation of entity integrity when propagating insertions, and lastly we should avoid any
interaction between FDs and INDs due to the intractability of the joint implication problem for
FDs and INDs. The main contributions of this paper are the formalisation of these design problems
and the result that if the database schema is in IDNF then all of these problems are eliminated.
We also demonstrate the robustness of IDNF by showing that, as for BCNF, removing redundancy
from the database schema in the presence of FDs and INDs is also equivalent to eliminating update
anomalies from the database schema.
The layout of the rest of the paper is as follows. In Section 2 we formally define FDs, INDs
and their satisfaction, and introduce the chase procedure as a means of testing and enforcing the
satisfaction of a set of FDs and INDs. In Section 3 we formalise the notion of no interaction between
a set of FDs and INDs and give a necessary and sufficient condition for FDs and noncircular INDs
not to interact. In Section 4 we characterise redundancy in the presence of FDs and INDs. In
Section 5 we characterise insertion and modification anomalies in the presence of FDs and INDs
and show an equivalence between being free of either insertion or modification anomalies and being
free of redundancy. In Section 6 we characterise a generalisation of entity integrity in the presence
of FDs and INDs. In Section 7 we define IDNF and present our main result that establishes
the semantics of IDNF in terms of either the update anomalies or redundancy problems, and the
satisfaction of generalised entity integrity. Finally, in Section 8 we give our concluding remarks
and indicate our current research direction.
Definition 1.1 (Notation) We denote the cardinality of a set S by jSj. The size of a set S is
defined to be the cardinality of a standard encoding of S.
If S is a subset of T we write S ' T and if S is a proper subset of T we write S ae T. We often
denote the singleton fAg simply by A and write A 2 S to mean fAg ' S. In addition, we often
denote the union of two sets S, T, i.e. S [ T, simply by ST.
Functional and inclusion dependencies
We formalise the notions of FDs and INDs and their satisfaction, and define some useful subclasses
of FDs and INDs. We also present the chase procedure for testing and enforcing the satisfaction
of a set of FDs and INDs. The chase procedure is instrumental in proving our main results.
Definition 2.1 (Database schema and database) Let U be a finite set of attributes. A relation
schema R is a finite sequence of distinct attributes from U. A database schema is a finite set
g, such that each R i 2 R is a relation schema and S
We assume a countably infinite domain of values, D; without loss of generality we assume that
D is linearly ordered. An R-tuple (or simply a tuple whenever R is understood from context) is a
member of the Cartesian product D \Theta
A relation r over R is a finite (possibly empty) set of R-tuples. A database d over R is a family
of n relations fr such that each r i 2 d is over R i 2 R. Given a tuple t over R and
assuming that r 2 d is the relation in d over R, we denote the insertion of t into r by d [ ftg, and
the deletion of t from r by d \Gamma ftg.
From now on we let R be a database schema and d be a database over R. Furthermore, we let
r 2 d be a relation over the relation schema R 2 R.
Definition 2.2 (Projection) The projection of an R-tuple t onto a set of attributes Y ' R,
denoted by t[Y] (also called the Y-value of t), is the restriction of t to Y. The projection of a
relation r onto Y, denoted as -Y (r), is defined by -Y rg.
Definition 2.3 (Functional Dependency) A functional dependency (or simply an FD) over a
database schema R is a statement of the Y is an FD over the
relation schema R), where R 2 R and X, Y ' R are sets of attributes. An FD of the
Y is said to be trivial if Y ' X; it is said to be standard if X 6= ;.
An is satisfied in d, denoted by d
Definition 2.4 (Inclusion Dependency) An inclusion dependency (or simply an IND) over a
database schema R is a statement of the form R i [X] ' R j [Y], where R i
are sequences of distinct attributes such that An IND is said to be trivial if it is
of the form R[X] ' R[X]. An IND R[X] ' S[Y] is said to be unary if An IND is said to
be typed if it is of the form R[X] ' S[X].
An IND R i [X] ' R j [Y] over R is satisfied in d, denoted by d
are the relations over R i and R j , respectively.
From now on we let F be a set of FDs over R and F
the set of FDs in F over R i 2 R. Furthermore, we let I be a set of INDs over R and let
Definition 2.5 (Logical implication) \Sigma is satisfied in d, denoted by d
logically implies an FD or an IND oe, written \Sigma whenever d is a database over R
then the following condition is true:
if d holds then d
logically implies a set \Gamma of FDs and INDs over R, written \Sigma
denote the set of all FDs and INDs that are logically implied by \Sigma.
Definition 2.6 (Keys, BCNF and key-based INDs) A set of attributes X ' R i is a superkey
for R i with respect to F i if F i is a key for R i with respect to F i if it is
a superkey for R i with respect to F i and for no proper subset Y ae X is Y a superkey for R i with
respect to F i . We let KEYS(F) be the set of all FDs of the form X ! R i , where X is a key for R i
with respect to F i , for ng.
A database schema R is in Boyce-Codd Normal Form (or simply BCNF) with respect to F if
for all R i 2 R, for all nontrivial FDs R is a superkey for R i with respect to F i .
An IND R i [X] ' R j [Y] is superkey-based, respectively key-based, if Y is a superkey, respectively
a key, for R j with respect to F j .
Definition 2.7 (Circular and noncircular sets of INDs) A set I of INDs over R is circular
if either
1. I contains a nontrivial IND R[X] ' R[Y], or
2. there exist m distinct relation schemas, R 1
contains the INDs: R 1
A set of INDs I is noncircular if it is not circular.
The class of proper circular INDs [Imi91] defined below includes the class of noncircular INDs
as a special case.
Definition 2.8 (Proper circular sets of INDs) A set I of INDs over R is proper circular if it
is either noncircular or whenever there exist m distinct relation schemas, R 1
I contains the INDs: R 1
It is well known that Armstrong's axiom system [Arm74, Mai83, Ull88, AA93] can be used
to compute F + and that Casanova's et al. axiom system [CFP84] can be used to compute I + .
However, when we consider FDs and INDs together computing \Sigma was shown to be undecidable
[Mit83, CV85]. On the other hand, when I is noncircular then Mitchell's axiom system [Mit83]
can be used to compute \Sigma + [CK86]. Moreover, in the special case when I is a set of unary INDs
then Cosmadakis's et al. axiom system [CKV90] can be used to compute \Sigma + .
The implication problem is the problem of deciding whether oe oe is an FD or
IND and \Sigma is a set of FDs and INDs. It is well-know that the implication problem for FDs on
their own is decidable in linear time [BB79]. On the other hand the implication problem for
INDs is, in general, PSPACE-complete [CFP84]. The implication problem for noncircular INDs is
NP-complete [Man84, CK86]. Typed INDs have a polynomial time implication problem [CV83].
Unary INDs have a linear time implication problem [CKV90]. When we consider FDs and INDs
together the implication problem is undecidable, as mentioned above. The implication problem for
FDs and noncircular INDs is EXPTIME-complete and if the noncircular INDs are typed then the
implication problem is NP-hard [CK86]. FDs and unary INDs have a polynomial time implication
problem [CKV90].
The next proposition describes the pullback inference rule [Mit83, CFP84], which allows us to
infer an FD from an FD and an IND.
Proposition 2.1 If \Sigma
Definition 2.9 (Reduced set of FDs and INDs) The projection of a set of FDs F i over R i
onto a set of attributes Y ' R i , denoted by F i [Y], is given by F i
i and WZ ' Yg.
A set of attributes Y ' R i is said to be reduced with respect to R i and a set of FDs F i over
simply reduced with respect to F i if R i is understood from context) if F i [Y] contains only
trivial FDs. A set of FDs and INDs I is said to be reduced if 8 R i [X] ' R j [Y] 2 I, Y is
reduced with respect to F j .
It can easily be shown that it can be decided in polynomial time in the size of \Sigma whether \Sigma is
reduced or not.
The chase procedure provides us with an algorithm which forces a database to satisfy a set of
FDs and INDs.
Definition 2.10 (The chase procedure for INDs) The chase of d with respect to \Sigma, denoted
by CHASE(d; \Sigma), is the result of applying the following chase rules, that is the FD and the IND
rules, to the current state of d as long as possible. (The current state of d prior to the first
application of the chase rule is its state upon input to the chase procedure.)
FD rule: If R
all the occurrences in d of the larger of the values of t 1 [A] and t 2 [A] to the
smaller of the values of t 1 [A] and t 2 [A].
IND rule: If R i [X] ' R j [Y] 2 I and 9t 2 r i such that t[X] 62 -Y (r j ), then add a tuple u over R j
to r j , where assigned a new value greater than any
other current value occurring in the tuples of relations in the current state of d.
We observe that if we allow I to be circular then the chase procedure does not always terminate
[JK84]. (When the chase of d with respect to \Sigma does not terminate, then CHASE(d; \Sigma) is said to
violate a set of FDs G over R, i.e. CHASE(d; \Sigma) 6j= G, if after some finite number of applications
of the IND rule to the current state of d, resulting in d 0 , we have that d 0 6j= G.) In the special case
when I is in the class of proper circular INDs then it was shown that the chase procedure always
terminates [Imi91].
The following theorem is a consequence of results in [MR92, Chapter 10].
Theorem 2.2 Let I be a set of FDs and proper circular INDs over a database schema
R. Then the following two statements are true:
(ii) CHASE(d; \Sigma) terminates after a finite number of applications of the IND rule to the current
state of d. 2
3 Interaction between FDs and INDs
As demonstrated by Proposition 2.1 FDs and INDs may interact in the sense that there may be
FDs and INDs implied by a set of FDs and INDs which are not implied by the FDs or INDs taken
separately. From the point of view of database design, interaction is undesirable since a database
design may be normalised with respect to the set of FDs but not with respect to the combined set
of FDs and INDs. This is illustrated in the following example.
Example 3.1 Consider the database schema and a set \Sigma of
FDs F and INDs I over R given by S[AB]g. It can easily
be verified that R in BCNF with respect to F. However, if we augment F with the
B, which is logically implied by \Sigma on using Proposition 2.1, then R is not in BCNF with respect
to the augmented set of FDs F, since A is not a superkey for R with respect to the set of FDs
Bg.
The other major difficulty that occurs in database design when the set of FDs and INDs
interact is a result of the fact that, as noted earlier, the implication problem for an arbitrary set of
FDs and INDs is undecidable [Mit83, CV85]. Because of this, in general it cannot be determined
whether a database design is in BCNF with respect to an arbitrary set of FDs and INDs, since
the set of all logically implied FDs cannot be effectively computed. As a consequence, a desirable
goal of database design is that the set of FDs and INDs do not interact. We now formalise the
notion of non interaction and characterise, for proper circular INDs, a special case when this non
interaction occurs.
Definition 3.1 (No interaction occurring between FDs and INDs) A set of FDs F over
R is said not to interact with of set of INDs I over R, if
1) for all FDs ff over R, for all subsets G ' F, G [ I
for all INDs fi over R, for all subsets J ' I, F [ J only if J
The following theorem is proven in [LL95] (see [MR92, Chapter 10]).
Theorem 3.1 If R is in BCNF with respect to a set of FDs F over R I is a proper circular set of
of INDs over R and I is reduced then F and I do not interact. 2
As the next example shows we cannot, in general, extend Theorem 3.1 to the case when the set
of INDs I is not proper circular. In particular, by Proposition 2.1 \Sigma being reduced is a necessary
condition for no interaction to occur between F and I, but it is not a sufficient condition for non
interaction.
Example 3.2 Consider a database schema and a set \Sigma of FDs
F and INDs I over R given by, Ag and I = fR[A] ' S[A], S[B] ' R[B]g.
It can easily be verified that \Sigma is reduced and that I is circular. On using the axiom system of
it follows that \Sigma thus F and I interact.
As another example let It can easily be verified
that \Sigma is reduced and I is circular. Again, F and I interact, since on using the axiom system of
R[A]g.
4 Attribute redundancy
In this section we investigate the conditions on database design which ensure the elimination of
redundancy, a goal which has been long cited as one of the principal motivations for the use
of normalisation in database design [Mai83, Ull88, MR92, AA93]. However it has proven to be
somewhat difficult to formalise the intuitive notion of redundancy, and it was only relatively
recently that this notion was formalised and its relationship to the classical normal forms was
established [Vin94, Vin98]. This definition of redundancy, and the associated normal form that
guarantees redundancy elimination, is as follows.
Definition 4.1 (Value redundancy) Let d be a database over R that satisfies F and t 2 r be
a tuple, where r 2 d is a relation over a relation schema R 2 R. The occurrence of a value t[A],
where A 2 R is an attribute, is redundant in d with respect to F if for every replacement of t[A]
by a distinct value v 2 D such that v 6= t[A], resulting in the database d 0 , we have that d 0 6j= F.
A database schema R is said to be in Value Redundancy Free Normal Form (or simply VRFNF)
with respect to a set of FDs F over R if there does not exist a database d over R and an occurrence
of a value t[A] that is redundant in d with respect to F.
We now illustrate the definition by a simple example.
Example 4.1 Consider the single relation scheme and a set F of FDs
given by Bg. Then R is not in VRFNF, since if we consider the relation r over
R, shown in Table 1, then the B-value, 2, present in both tuples, is redundant, since r
replacing the value 2 in either tuple by another value results in F being violated.

Table

1: The relation r
The following result, which was established in [Vin94, Vin98], shows that given a set of FDs
F, VRFNF is equivalent to BCNF. For the sake of completeness, we provide a sketch of the proof.
Theorem 4.1 A database schema R is in BCNF with respect to F if and only if R is in VRFNF
with respect to F.
Proof. The if part follows by showing the contrapositive that if R is not in BCNF then it is
not in VRFNF. This result follows because if R is not in BCNF then there exists a non-trivial
implied FD X ! A where X is not a superkey and using a well known construction (Theorem 7.1
in [Ull88]) there exists a two tuple relation r in which the tuples are identical on XA. The relation
r is not in VRFNF since changing either of the A-values results in X ! A being violated. The
only if part follows from the observation that if an occurrence t[A] is redundant in a relation r,
then there must exist r such that
This implies that X cannot be a superkey and hence that R is not in BCNF and so establishes
the only if part. 2
In [Vin98] it was shown that in the presence of multivalued dependencies 4NF (fourth normal
form [Fag77]) is also equivalent to VRFNF. Somewhat surprisingly, the syntactic equivalent for
VRFNF, in the most general case where join dependencies are present, is a new normal form that
is weaker than PJ/NF (project-join normal form [Fag79]) and 5NF (fifth normal form [Mai83])
[Vin98].
The concept of value redundancy is of little use though, in evaluating database designs in
the presence of INDs because of the following result. It demonstrates that no design where the
constraints involve nontrivial INDs can be in VRFNF with respect to the set of INDs.
Lemma 4.2 Let I be a set of FDs and noncircular INDs over a database schema R.
Then R is not in VRFNF with respect to \Sigma if I is nonempty and contains at least one nontrivial
IND.
Proof. Let R i [X] ' R j [Y] be a nontrivial IND in I. We construct a database d such that the
relation r i in d over R i has in it a single tuple t i containing zeros and every other relation r k in d
is empty. Now, let d thus by Theorem 2.2 d 0 Due to the noncircularity
of I, we have in d 0 that r
i is the current state of r i in d 0 . Let r 0
j be the current state
of the relation r j over R j in d 0 . Then the Y-values of the tuple in r 0
must contain zeros, since
Thus all of the zeros in the single tuple in r 0
are redundant, since changing any of them
results in R i [X] ' R j [Y] being violated. 2
Due to the above lemma, we require only that the design be in VRFNF with respect to the
FDs but not with respect to the INDs. However, as noted by others [Sci86, LG92, MR92], an even
stronger form of redundancy can occur in a database in the presence of INDs. We refer to this as
attribute redundancy, which was illustrated in Example 1.1 given in the introduction.
Definition 4.2 (Attribute redundancy) An attribute A in a relation schema R 2 R is redundant
with respect to \Sigma if whenever d is a database over R which satisfies \Sigma and r 2 d is a nonempty
relation over R, then for every tuple t 2 r, if t[A] is replaced by a distinct value v 2 D such that
resulting in the database d 0 , then d 0 6j= \Sigma.
A database schema R is said to be in Attribute Redundancy Free Normal Form (or simply
ARFNF) with respect to a set of FDs and INDs \Sigma over R if there does not exists an attribute A
in a relation schema R 2 R which is redundant with respect to \Sigma.
The next example shows that ARFNF is too weak when \Sigma contains only FDs, highlighting the
difference between VRFNF and ARFNF.
Example 4.2 Consider the relation r of Example 4.1, shown in Table 1, and let r 0 be the result
of adding the tuple t =! 5; 2; 4 ? to r. Then, it can easily be verified that, although R is not in
VRFNF with respect to F, R is in ARFNF with respect to F, since if we replace any value in t
by a distinct value then the resulting database still satisfies F.
Combining Definitions 4.1 and 4.2 we can define redundancy free normal form.
Definition 4.3 (Redundancy free normal database schema R is said to be in Redundancy
Free Normal Form (or simply RFNF) with respect to a set of FDs and INDs \Sigma over R
if it is in VRFNF with respect to F and in ARFNF with respect to \Sigma.
The next theorem shows that when the set of INDs is noncircular then RFNF is equivalent to
the set of FDs and INDs being reduced and to the database schema being in BCNF.
Theorem 4.3 Let I be a set of FDs and noncircular INDs over a database schema R.
Then R is in RFNF with respect to \Sigma if and only if \Sigma is reduced and R is in BCNF with respect
to F.
Proof. If. By Theorem 4.1 R is in VRFNF with respect to F. So it remains to show that R is in
ARFNF.
In the proof we utilise a directed graph representation, G I = (N, E), of the set of INDs I,
which is constructed as follows (see [Sci86]). Each relation schema R in R has a separate node in
labelled R; we do not distinguish between nodes and their labels. There is an arc (R,
and only if there is a nontrivial IND R[X] ' S[Y] 2 I. It can easily be verified that there is a path
in G I from R to S if and only if for some IND R[X] ' S[Y] we have I
since I is noncircular, we have that G I is acyclic.
Let A 2 R i be an attribute, where R i 2 R is a relation schema. We construct a database d
having a nonempty relation r i 2 d, which exhibits the fact that A is nonredundant with respect
to \Sigma.
We first initialise the database d to be a database d 0 as follows. Let r
have a single tuple
t such that for all B relations r 0
R k are initialised to be empty in d 0 . Therefore, by Theorem 2.2, we have that d
i in d 1 be the current state of r i . Then, by Theorem 3.1 we have r 1
and the current state r 1
k in d 1 of a relation r 0
k is empty, if there does not exist a path in G I from
R i to R k .
i has a single tuple t 0 such that for all B 2 R i , including A,
Therefore, by Theorem 2.2, we have that d
i in d 3 is the current state of r i , since d 2
be
the final state of the initialisation of d. Then, d j= F, since d 3 We claim that it is also that
case that d
Let us call a nontrivial IND R i [X] ' R j [Y] 2 I a source IND, if A 2 X. By the projection and
permutation inference rule for INDs [CFP84] we assume without loss of generality that a source
IND has the form R i [VA] ' R j [WB].
Due to the noncircularity of I any current state r k in d of a relation r 3
k is empty, if there does
not exist a path in G I from R i to R k ; therefore for such r k we have r
Now, if there is an arc from R i to R j in G I , then there is some IND R i [X] ' R j [Y] in I. There are
two cases to consider.
First, if A 62 X then contains only zeros and thus d Secondly,
if A 2 X then R i [X] ' R j [Y] is a source IND R i [VA] ' R j [WB]. Let r j in d be the current state
of r 3
Therefore d It follows that for any IND R i [X] ' R j [Y] such that there is a path
from R i to R j and such that I we have d since d 3
I as required. The if part is now concluded since d 3 and d differ only by the
replacement of t 0
Only if. By Theorem 4.1 if R is not in BCNF with respect to F then it is not in VRFNF. So
assuming that \Sigma is not reduced it remains to show that R is not in ARFNF. By this assumption
there exists an IND R i [X] ' R j [Y] 2 I such that is a nontrivial FD. By the
pullback inference rule there is a nontrivial FD by the
projection and permutation inference rule for INDs [CFP84]. Now let t 2 r i be a tuple, where
is a nonempty relation over R i , and assume that d j= \Sigma. It follows that A is redundant with
respect to \Sigma, since whenever we replace t[A] by a distinct value resulting in a database d 0 , it can
be seen that d 0 contrary to assumption. 2
We next construct two examples which demonstrate that if the conditions of Theorem 4.3 are
violated then R is not in ARFNF.
Example 4.3 Let R be the database schema from Example 1.1 and consider the database d
overR, shown in Tables 2 and 3, respectively. It can be verified that the set of FDs and INDs for
this example is not reduced but that R is in BCNF with respect to the set of FDs. The attribute
D of the relation schema HEAD can be seen to be redundant, since changing e 1 in Table 2 causes
I to be violated. A similar situation occurs for every other database defined over R, and so R is
not in ARFNF.

Table

2: The relation in d over HEAD

Table

3: The relation in d over LECT
Example 4.4 Let R= fSTUDENT, ENROLg, be a database schema, with STUDENT= fStud ID,
Nameg and Addressg. Furthermore, let
Addressg be a set of FDs over R and I = fENROL[Stud ID] ' STUDENT[Stud ID]g be a set of
INDs over R. It can be verified that the set of FDs and INDs for this example is reduced but that
R is not in BCNF with respect to the set of FDs. Then R is not in RFNF because it is not in
VRFNF, since both occurrences of a 1 in ENROL are redundant in the database d shown in Tables
4 and 5, respectively.
Stud ID Name

Table

4: The relation in d over
over STUDENT
Stud ID Course Address

Table

5: The relation in d over ENROL
As the next example shows we cannot extend Theorem 4.3 to the case when the set of INDs I
is circular.
Example 4.5 Consider a database schema and a set
\Sigma of FDs F and INDs I over R given by, Ag and I = fR[A] ' S[A],
R[A]g. It can be verified that \Sigma is reduced, R is in BCNF with respect to F and that I is
proper circular, unary, typed and also key-based.
Let d be a database over R such that d d be a nonempty relation over R and let
r be a tuple. Assume without loss of generality that d 0 is the database resulting from replacing
by a distinct value 1 resulting in a tuple t 0 , with t 0 1. In order to conclude the
example we show that d 0 6j= \Sigma. Assume to the contrary that d 0 \Sigma. Thus there must be a tuple
which is distinct from t and such that 1. If this is not the case then d 0 6j= R[A] ' S[A],
since -A
It follows that thus d A contrary to
assumption. Therefore the attribute A 2 R must be redundant with respect to \Sigma. The reader can
easily verify that the attribute A 2 S is also redundant with respect to \Sigma even if F was empty. It
appears that in this example the relation schema S can be removed from R without any loss of
semantics.
5 Insertion and modification anomalies
In this section, we investigate the conditions under which database design ensures the elimination
of key-based update anomalies, (as distinct from other types of update anomalies as investigated
in [BG80, Vin94]). This concept was originally introduced in [Fag81] to deal with the insertion and
deletion of tuples and was later extended in [Vin92, Vin94] to include the modifications of tuples. A
key-based update anomaly is defined to occur when an update to a relation, which can either be an
insertion or a deletion or a modification, results in the new relation satisfying key uniqueness but
violating some other constraint on the relation. The reason for this being considered undesirable
is that the enforcement of key uniqueness can be implemented via relational database software
in a much more efficient manner than the enforcement of more general constraints such as FDs
[Mai83, Ull88, aa93]. So, if the satisfaction of all the constraints on a relation is a result of key
uniqueness then the integrity of the relation after an update can be easily enforced, whereas the
existence of a key-based update anomaly implies the converse. Herein we formalise these concepts
based on this approach, with the only difference being that because of the presence of INDs we
allow an update to propagate to other relations by the chase procedure. We show that being free
of insertion anomalies is equivalent to being free of modification anomalies. In addition, we show
that when the INDs are noncircular then being free of either insertion or modification anomalies
is equivalent to the set of FDs and INDs being reduced and the database schema being in BCNF
with respect to the set of FDs. We do not consider deletion anomalies, since in the presence of
FDs removing a tuple from a relation that satisfies a set of FDs, does not cause any violation of
an FD in the set.
Definition 5.1 (Compatible tuple) A tuple t over R is compatible with d with respect to a set
of FDs and INDs I over R (or simply compatible with d whenever \Sigma is understood from
Definition 5.2 (Free of insertion anomalies) A database d over R has an insertion violation
with respect to a set of FDs and INDs (or simply d has an insertion violation
whenever \Sigma is understood from context) if
1. d
2. there exists a tuple t over R which is compatible with d but CHASE(d [ ftg, I) 6j= \Sigma.
A database schema R is free of insertion anomalies with respect to \Sigma (or simply R is free of
insertion anomalies if \Sigma is understood from context) if there does not exist a database d over R
which has an insertion violation.
We note that in Definition 5.2 we have utilised the chase procedure to enforce the propagation
of insertions of tuples due to the INDs in I. As an example of an insertion violation consider the
database schema R in Example 1.1 and let d be the database where r 1 , the relation over HEAD, is
empty and r 2 , the relation over LECT, contains the single tuple ! 0; 0 ?. Then d has an insertion
violation when the tuple ! since applying the chase procedure results in
being added to the relation r 2 and thus violating the FD L ! D.
The next theorem shows that assuming that the set of INDs is noncircular, being in BCNF
and the set of FDs and INDs being reduced is equivalent to being free of insertion anomalies.
Theorem 5.1 Let I be a set of FDs and noncircular INDs over a database schema R.
Then R is free of insertion anomalies if and only if \Sigma is reduced and R is in BCNF with respect
to F.
Proof. If. Let d be a database over R such that d
a tuple which is compatible with d. It remains to show that CHASE(d [ ftg, I) We first
claim that CHASE(d [ ftg, This holds due to Theorem 3.1 implying
that the FD rule need never be invoked during the computation of CHASE(d[ ftg; \Sigma). Moreover,
due to the fact that R is in BCNF with respect to F and t is compatible with d. So,
by Theorem 2.2 we have CHASE(d [ ftg; \Sigma)
Only if. There are two cases to consider.
Case 1. If R is not in BCNF with respect to F, then some R i 2 R is not in BCNF with
respect to F i . Thus there is a nontrivial FD is not a superkey for R i
with respect to F i . Assume that X is reduced with respect to R i and F i , otherwise replace X by a
reduced subset W of X such that W! X
i . It follows that X is a proper subset of a superkey
of R i with respect to F i . Let r i over R i contain a single tuple containing zeros and let all other
relations in d be empty. We can assume without loss of generality that d j= \Sigma, otherwise we let d
be CHASE(d; \Sigma). Due to I being noncircular the state of r i remains unchanged in CHASE(d; \Sigma).
let t be a tuple whose X-values are zeros and such that all its other values are ones. Then
t is compatible with d but CHASE(d [ ftg, I) 6j= \Sigma, since the FD will be violated in the
current state of r i . Therefore, R is not free of insertion anomalies.
Case 2. If \Sigma is not reduced but R is in BCNF with respect to F then we have an IND R i [X]
Y is a proper superset of a key, say W, for R j with respect to F j . We let r j
over R j contain a single tuple, say t containing zeros and let all other relations in d, including
r i over R i , be empty. We can assume without loss of generality that d j= \Sigma, otherwise we let d
be CHASE(d; \Sigma). Due to I being noncircular the state of r i remains unchanged in CHASE(d; \Sigma).
a tuple which agrees with t j on its W-value but disagrees with t j on the rest
of its values. Then, t is compatible with d but CHASE(d [ ftg, I) 6j= \Sigma, since the FD W
will be violated in the resulting current state of r j . 2
To illustrate this theorem we note firstly that the example given before Theorem 5.1, demonstrates
the case where a database schema has an insertion anomaly when the set of dependencies
is not reduced. Alternatively, the following example demonstrates the case of a database schema
not being in BCNF and having an insertion anomaly.
Example 5.1 Let R, be as in Example 4.4. We start with the database d shown in

Tables

6 and 7, respectively. If we then insert the tuple which is compatible with
ENROL, into the ENROL relation, applying the chase procedure results in the database d 0 shown
in

Tables

8 and 9, respectively, where n 2 is a new value. It can be seen that d 0 violates \Sigma and so
R is not free of insertion anomalies.
In the next example we show that the only if part of Theorem 5.1 is, in general, false, even
when I is a proper circular set of INDs.
Stud ID Name

Table

The relation in d over
over STUDENT
Stud ID Course Address

Table

7: The relation in d over ENROL
Stud ID Name

Table

8: The relation in d 0
over over STUDENT
Stud ID Course Address

Table

9: The relation in d 0 over ENROL
Example 5.2 Consider a database schema and a set \Sigma of FDs
F and INDs I over R given by,
' R[AB]g. It can easily be verified that I is proper circular, R is in BCNF but that \Sigma is not
reduced. In addition, R is free of insertion anomalies, since for any database d = fr; sg such that
d are the relations in d over R and S, respectively, we have that due to
I. If we drop S[AB] ' R[AB] from I, then, as in the proof of the only if part of Theorem 5.1, R
has an insertion violation.
The next example illustrates that we cannot, in general, extend Theorem 5.1 to the case when
the set of INDs I is circular even when \Sigma is reduced, due to possible interaction between the FDs
and INDs.
Example 5.3 Consider a database schema and a set \Sigma of FDs F and
INDs I over R given by, R[B]g. It can be verified that \Sigma is
reduced but I is circular. As was shown in Example 3.2 although \Sigma is reduced \Sigma
thus F and I interact.
Let d be a database over R such that the relation r over R contains the single tuple !
and let t be the tuple ! has an insertion violation, since d
with d but CHASE(d [ ftg, I) A. (In fact, in this case the chase procedure does not
terminate, but since t is inserted into r and the chase procedure does not modify any of the tuples
in its input database, then it does not satisfy \Sigma; see the comment after Definition 2.10.)
We now formally define the second type of key-based update anomaly, a modification anomaly,
following the approach in [Vin92, Vin94] with the only difference again being that the chase
procedure is used to propagate the effects of the change into other relations.
Definition 5.3 (Free of modification anomalies) A database d over R has a modification
violation with respect to a set of FDs and INDs (or simply d has a modification
violation whenever \Sigma is understood from context) if
1. d
2. there exists a tuple u d is the relation over R, and a tuple t over R which is
compatible with
A database schema R is free of modification anomalies with respect to \Sigma (or simply R is free
of modification anomalies if \Sigma is understood from context) if there does not exist a database d
over R which has a modification violation.
Theorem 5.2 Let I be a set of FDs and noncircular INDs over a database schema R.
Then R is free of modification anomalies if and only if R is free of insertion anomalies.
Proof. If. Let d be a database over R such that d be a tuple that is compatible with
d and u 2 r be a tuple, where r 2 d is the relation over R. It follows that t is compatible with
fug. We need to show that if CHASE(d [ ftg, I)
\Sigma. By Theorem 2.2 of the chase procedure CHASE((d remains
to show that CHASE((d \Gamma fug) [ ftg, I)
g. Then by Definition 2.10 of the chase procedure we
have that for all It follows that CHASE((d since by
Definition 5.2 CHASE(d [ ftg, I)
Only if. If R is free of modification anomalies then by a similar argument to that made in the
only if part of the proof of Theorem 5.1 it follows that \Sigma is reduced and R is in BCNF. In the
first case we add an additional tuple u over R i , which contains ones, to the original state of r i ,
and in the second case we add an additional tuple u over R i , which contains zeros, to the original
state of r i . The result now follows by the if part of Theorem 5.1. 2
Combining Theorems 4.3, 5.1 and 5.2 we obtain the next result.
Corollary 5.3 Let I be a set of FDs and noncircular INDs over a database schema R.
Then the following statements are equivalent:
(i) R is free of insertion anomalies.
(ii) R is free of modification anomalies.
(iii) R is in RFNF. 2
6 Generalised entity integrity
In this section we justify superkey-based INDs on the basis that they do not cause the propagation
of the insertion of tuples that represent undefined entities, thus causing the violation of entity
integrity. This problem was illustrated in Example 1.2 given in the introduction.
In the next definition we view the chase procedure as a mechanism which enforces the propagation
of insertions of tuples due to the INDs in I.
Definition 6.1 (Generalised entity integrity) Let t be a tuple that is added to a relation r i
in the current state of a database d, during the computation of CHASE(d; \Sigma). Then, t is
entity-based if there exists at least one key X for R i with respect to F i such that for all A 2 X,
t[A] is not a new value that is assigned to t as a result of invoking the IND rule.
A database schema R satisfies generalised entity integrity with respect to a set I of
FDs and INDs over R if for all databases d over R, all the tuples that are added to relations in
the current state of d during the computation of CHASE(d; \Sigma) are entity-based.
The next theorem shows that satisfaction of generalised entity integrity is equivalent to the
set of INDs being superkey-based.
Theorem 6.1 A database schema R satisfies generalised entity integrity with respect to a set of
FDs and INDs if and only if I is superkey-based.
Proof. If I is superkey-based then the result immediately follows by the definition of the IND rule
(see Definition 2.10). On the other hand, if I is not superkey-based then there is some IND R i [X]
I such that Y is not a superkey for R j with respect to F j . Let d be a database over R
such that all its relations apart for r i over R i are empty. The relation r i has a single tuple. By
the definition of the FD rule (see Definition 2.10), we have that for every key, say K, of R j with
respect to F j there is at least one attribute, say A 2 K, such that the tuple t j added to r j over R j
is assigned a new A-value by the IND rule, otherwise, contrary to assumption, we can deduce that
Y is a superkey for R j with respect to F j . It follows that R does not satisfy generalised entity
integrity, concluding the proof. 2
7 Inclusion dependency normal form
A database schema is in IDNF with respect to a set of FDs and INDs if it is in BCNF with respect
to the set of FDs and the set of INDs is noncircular and key-based. We show that a database
schema is in IDNF if and only if it satisfies generalised entity integrity and is either free of insertion
anomalies or free of modification anomalies or in redundancy free normal form.
We next formally define IDNF (cf. [MR86, MR92]).
Definition 7.1 (Inclusion dependency normal form) A database schema R is in Inclusion
Dependency Normal Form (IDNF) with respect to a set of \Sigma of FDs F and INDs I over R (or
simply in IDNF if \Sigma is understood from context) if
1. R is in BCNF with respect to F, and
2. I is a noncircular and key-based set of INDs.
We note that if the set of INDs I is empty then R being in IDNF is equivalent to R being in
BCNF. We further note that we have not restricted the FDs in F to be standard.
The next result follows from Corollary 5.3, Theorem 6.1 and Definition 7.1.
Theorem 7.1 Let I be a set of FDs and noncircular INDs over a database schema R.
Then the following statements are equivalent:
(i) R is in IDNF
(ii) R is free of insertion anomalies and satisfies generalised entity integrity.
(iii) R is free of modification anomalies and satisfies generalised entity integrity.
(iv) R is in RFNF and satisfies generalised entity integrity. 2
Concluding Remarks
We have identified three problems that may arise when designing databases in the presence of
FDs and INDs, apart from the update anomalies and redundancy problems that may arise in each
relation due to the FDs considered on their own. The first problem is that of attribute redundancy,
the second problem is the potential violation of entity integrity when propagating insertions, and
the third problem concerns avoiding the complex interaction which may occur between FDs and
INDs and the intractability of determining such interaction. The first problem was formalised
through RFNF and it was shown in Corollary 5.3 that a database schema is in RFNF with respect
to a set of FDs and INDs if and only if it is free of insertion anomalies or equivalently free
of modification anomalies. This result can be viewed as an extension of a similar result when
considering FDs on their own. The second problem was formalised through generalised entity
integrity and it was shown in Theorem 6.1 that a database schema satisfies generalised entity
integrity with respect to a set of FDs and INDs if and only the set of INDs is superkey-based.
The third problem was formalised through the non interaction of the implication problem for FDs
and INDs and it was shown in Theorem 3.1 that a set of FDs and INDs do not interact when
the set of INDs is proper circular, the set of FDs and INDs are reduced and the database schema
is in BCNF. Combining all these result together we obtained, in Theorem 7.1, three equivalent
semantic characterisations of IDNF. Theorem 7.1 justifies IDNF as a robust normal form that
eliminates both redundancy and update anomalies from the database schema.
If the goal of normalisation is to reduce redundancy then it seems that apart from R being
in BCNF, in general, we must restrict the set of INDs to be noncircular (see Example 4.5).
Nonetheless circular sets of INDs arise in practice, for example when we want to express pairwise
consistency. (Two relation schemas R and S are consistent if the set of INDs I includes the two
INDs: database schema R is pairwise consistent
if every pair of its relation schemas are consistent [BFMY83]; we note that pairwise consistency
can be expressed by a set of proper circular INDs.) In this case we need alternative semantics
to express the goal of normalisation. A minimal requirement is that the FDs and INDs have no
interaction. By Theorem 3.1 as long as the set of FDs and INDs I is reduced and R
is in BCNF with respect to F then, when the set of INDs I expresses pairwise consistency, F
does not interact with I, since I is proper circular. Consider a BCNF database schema R with
relation schemas
with
EMP[DNAME]g. The set of INDs I
expresses the fact that all employees work in departments that exist and all departments have at
least one employee. The first IND is key-based but the second is not. Despite this fact it can be
verified that F and I do not interact. Moreover, if managers are also employees then we could add
the IND DEPT[MGR] ' EMP[ENAME] to I, and it can be verified by exhibiting the appropriate
counterexamples that it is still true that F and I do not interact although, now I is not even
proper circular. The database schema R seems to be a reasonable design but it is not in IDNF.
Further research needs to be carried out to determine the semantics of normal forms for such FDs
and INDs. We conclude the paper by proposing such a normal form. A database schema R is
in Interaction Free Inclusion Dependency Normal Form with respect to a set of \Sigma of FDs F and
INDs I over R if
1. R is in BCNF with respect to F,
2. All the INDs in I are either key-based or express pairwise consistency, and
3. F and I do not interact.



--R

Relational Database Theory.
Dependency structures of data base relationships.
Computational problems related to the design of normal form relational schemas.
Objects in relational database schemes with functional
On the desirability of acyclic database schemes.
What does Boyce-Codd normal form do? <Proceedings>In Proceedings of the International Conference on Very Large Data Bases</Proceedings>

Inclusion dependencies and their interaction with functional dependencies.
A design theory for solving the anomalies problem.
A graph theoretic approach.

Recent investigations in relational data base systems.
Extending the database relational model to capture more meaning.
Enforcing
Towards a sound view integration methodology.
The implication problem for functional and
Referential integrity.
Multivalued dependencies and a new normal form for relational databases.
Normal forms and relational database operators.
A normal form for relational databases that is based on domains and keys.
Abstraction in query processing.
Testing containment of conjunctive queries under functional and
Logical database design with
How to prevent interaction of functional and
The Theory of Relational Databases.
On the complexity of the inference problem for subclasses of
The implication problem for functional and


Comparing the universal instance and relational data models.
Principles of Database and Knowledge-Base Systems
Modification anomalies and Boyce-Codd normal form
The Semantic Justification for Normal Forms in Relational Database Design.
Redudnancy elimination and a new normal form for relational databases.
--TR

--CTR
Fabien De Marchi , Jean-Marc Petit, Semantic sampling of existing databases through informative Armstrong databases, Information Systems, v.32 n.3, p.446-457, May, 2007
Stphane Lopes , Jean-Marc Petit , Farouk Toumani, Discovering interesting inclusion dependencies: application to logical database tuning, Information Systems, v.27 n.1, p.1-19, March 2002
Junhu Wang, Binary equality implication constraints, normal forms and data redundancy, Information Processing Letters, v.101 n.1, p.20-25, January 2007
Junhu Wang, Binary equality implication constraints, normal forms and data redundancy, Information Processing Letters, v.101 n.1, p.20-25, January 2007
Laura C. Rivero , Jorge H. Doorn , Viviana E. Ferraggine, Elicitation and conversion of hidden objects and restrictions in a database schema, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain
Millist W. Vincent , Jixue Liu , Chengfei Liu, Strong functional dependencies and their application to normal forms in XML, ACM Transactions on Database Systems (TODS), v.29 n.3, p.445-462, September 2004
Marcelo Arenas , Leonid Libkin, An information-theoretic approach to normal forms for relational and XML data, Journal of the ACM (JACM), v.52 n.2, p.246-283, March 2005
Marcelo Arenas , Leonid Libkin, An information-theoretic approach to normal forms for relational and XML data, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.15-26, June 09-11, 2003, San Diego, California
Marcelo Arenas, Normalization theory for XML, ACM SIGMOD Record, v.35 n.4, December 2006
Solmaz Kolahi , Leonid Libkin, On redundancy vs dependency preservation in normalization: an information-theoretic study of 3NF, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
Mark Levene , George Loizou, Why is the snowflake schema a good data warehouse design?, Information Systems, v.28 n.3, p.225-240, May
relational database design;functional dependency;normal forms;inclusion dependency