UNIT -III

Relational Database Design: Features of Good Relational Designs- Atomic Domains and First Normal
Form- Second Normal Form-Decomposition Using Functional Dependencies- Functional-Dependency
Theory-Algorithms for decomposition- Decomposition Using Multivalued Dependencies-More Normal
Forms- Database-Design Process- Modeling Temporal Data

Two Marks

1. What is normalization?

The main goal of normalization is to reduce redundant data. Normalization is based on functional
dependencies.

2. What is First Normal Form?( NOV 2010)

First normal form is also called as flat file. There are no composite attributes and every attribute is
single and describe one property.

3. What is functional dependencies?

Functional dependencies play key role in differentiating good database designs from bad database
design. A functional dependency is a type of constraint that is a generalization of the notion of key.

4. What is decomposition?
The process of decomposing a relation schema that has many attributes into several schemas with
fewer attributes is called decomposition.

5. What is Boyce Codd Normal Form?

A relation schema R is in BCNF with respect to a set F of functional dependencies if, for all functional
dependencies in F+ of the form α→β, where α C R and β C R, atleast one of the following holds:

 α→β is a trivial functional dependency.

 α is a superkey for schema R.

6. What is Third Normal Form?

DEPT OF CSE Page 1

A relation is said to be Third normal form where all attributes in a relation tuple are not only
functionally dependent on key attributes but also dependent on non key attributes.

7. What is Second Normal Form?

A relation is said to be in Second normal form, if it is in first normal form and non key attributes are
functionally dependent on the key attributes.

8. What is Fourth Normal Form?

This schema is called as non- BCNF schema. A relation defined with multivalued dependency which is a
new form of constraint is called forth normal form. It is more restrictive than BCNF.

9. What is multi valued dependency?

Multivalued dependencies are referred to as tuple generating dependencies. It do not rule out existence
of certain tuples, instead they require other tuples of certain form be present in the relation.

10. Comparison of BCNF and 3CNF.

3CNF BCNF

 3NF: For every functional  BCNF: For every functional dependency

dependency X->Y in a set F of X->Y in a set F of functional dependencies
functional dependencies over over relation R, either:
relation R, either: Y is a subset Y is a subset of X or,
of X or,X is a superkey of R, or Y
X is a superkey of R
is a subset of K for some key K
of R N.b., no subset of a key is a
key.
 If we cannot check for dependency
 It is always possible to obtain a
preservation eciently, we either pay a
3NF design without sacrificing
high price in system performance or risk
lossless-join or dependency
the integrity of the data.
preservation.
 The limited amount of redundancy in 3NF
 If we do not eliminate all
is then a lesser evil.
transitive dependencies, we
may need to use null values to
represent some of the

DEPT OF CSE Page 2

 meaningful relationships.
 Repetition of information
occurs.

11.Define Functional Dependencies.

Let X  R and Y  R, then the Functional dependency (FD) X  Y holds on R if, in any relation
r(R), for all pairs of tuples t1 and t2 in r such that t1[X] = t2[X], it is also the case that t1[Y] =
t2[Y].

12.Define normalization of data and denormalization.

Normalization:
Process of decomposing an unsatisfactory relation schema into satisfactory relation
schemas by breaking their attributes, so as to satisfy the desirable properties. Denormalization:
Process of storing the join of higher normal form relations as base relation, which is in the lower
normal form.

13.Explain shortly the four properties or objectives of normalization.

 To minimize redundancy
 To minimize insertion, deletion, and updating anomalies.
 Lossless-join or non-additive join decomposition
 Dependency preservation

14.Define Partial Functional Dependency.

A FD x   y is a partial dependency if some attribute A x can be removed from x and
the dependency still holds; ie., for some A  x, ( x – { A } )  y.

11 MARKS
1.Explain in detail about Relational database design? (11 Marks)

DEPT OF CSE Page 3

First Normal Form

A domain is atomic if elements of the domain are considered to be indivisible units. We say that
a relation schema R is in first normal form (1NF) if the domains of all attributes of R are atomic. A set
of names is an example of a nonatomic value. For example, if the schema of a relation employee
included an attribute childrenwhose domain elements are sets of names, the schema would not be in
first normal form. Composite attributes, such as an attribute address with component attributes street
and city, also have nonatomic domains. Integers are assumed to be atomic, so the set of integers is an
atomic domain; the set of all sets of integers is a nonatomic domain. The distinction is that we do not
normally consider integers to have subparts, but we consider sets of integers to have subparts namely,
the integers making up the set.

The domain of all integers would be nonatomic if we considered each integer to be an ordered list of
digits.

Some types of nonatomic values can be useful, although they should be used with care. For example,
composite valued attributes are often useful, and set valued attributes are also useful in many cases,
which is why both are supported in the E-R model.

Pitfalls in Relational-Database Design

Among the undesirable properties that a bad design may have are:

 Repetition of information
 Inability to represent certain information

Suppose the information concerning loans is kept in one single relation, lending, which is defined over
the relation schema
Lending-schema = (branch-name, branch-city, assets, customer-name,
loan-number, amount)
A tuple t in the lending relation has the following intuitive meaning:
 t[assets] is the asset figure for the branch named t[branch-name].

DEPT OF CSE Page 4

  t[branch-city] is the city in which the branch named t[branch-name] is located.
 t[loan-number] is the number assigned to a loan made by the branch named t[branch-name] to
the customer named t[customer-name].
 t[amount] is the amount of the loan whose number is t[loan-number].

Suppose that we wish to add a new loan to our database. Say that the loan is made by the Perryridge
branch to Adams in the amount of $1500. Let the loan-number be L-31. In our design, we need a tuple
with values on all the attributes of Lendingschema. Thus, we must repeat the asset and city data for the
Perryridge branch, and must add the tuple
(Perryridge, Horseneck, 1700000, Adams, L-31, 1500)

Another problem with the Lending-schema design is that we cannot represent directly the information
concerning a branch (branch-name, branch-city, assets) unless there exists at least one loan at the
branch. This is because tuples in the lending relation require values for loan-number, amount, and
customer-name. One solution to this problem is to introduce null values, as we did to handle updates
through views.

Sample lending relation.

DEPT OF CSE Page 5

Functional Dependencies

Basic Concepts

Functional dependencies are constraints on the set of legal relations. They allow us to express facts
about the enterprise that we are modeling with our database.

Let R be a relation schema. A subset K of R is a superkeyof R if, in any legal relation r(R), for all pairs t1
and t2 of tuples in r such that t1 _= t2, then t1[K] _= t2[K]. That is, no two tuples in any legal relation
r(R) may have the same value on attribute set K. The notion of functional dependency generalizes the
notion of superkey. Consider a relation schema R, and let α ⊆R and β ⊆R. The functional dependency
α→β
holds on schema R if, in any legal relation r(R), for all pairs of tuples t1 and t2 in r such that t1[α] =
t2[α], it is also the case that t1[β] = t2[β].

Using the functional-dependency notation, we say that K is a superkey of R if K → R. That is, K is a

superkey if, whenever t1[K] = t2[K], it is also the case that t1[R] = t2[R] (that is, t1 = t2).Functional
dependencies allow us to express constraints that we cannot express with superkeys. Consider the
schema
Loan-info-schema = (loan-number, branch-name, customer-name, amount)
which is simplification of the Lending-schema that we saw earlier. The set of functional dependencies
that we expect to hold on this relation schema is
loan-number→amount
loan-number→branch-name

We shall use functional dependencies in two ways:

1. To test relations to see whether they are legal under a given set of functional dependencies. If a
relation r is legal under a set F of functional dependencies, we say that r satisfies F.
2. To specify constraints on the set of legal relations. We shall thus concern ourselves with only
those relations that satisfy a given set of functional dependencies. If we wish to constrain
ourselves to relations on schema R that satisfy a set F of functional dependencies, we say that F
holds on R.

DEPT OF CSE Page 6

To distinguish between the concepts of a relation satisfying a dependency and a dependency holding on
a schema, we return to the banking example. In the loan relation (on Loan-schema) we see that the
dependency loannumber→ amount is satisfied. In contrast to the case of customer-city and customer
street in Customer-schema.

The customer relation.

The loan relation.

In the branch relation of Figure 7.5, we see that branch-name → assets is satisfied, as is assets →
branch-name. We want to require that branch-name → assets hold on Branch-schema. However, we do
not wish to require that assets → branch-name hold, since it is possible to have several branches that
have the same asset value.

DEPT OF CSE Page 7

 The branch relation.

 On Branch-schema: branch-name →branch-city

branch-name→assets

 On Customer-schema:customer-name→ customer-city
customer-name→ customer-street

 On Loan-schema: loan-number → amount

loan-number→ branch-name

 On Borrower-schema: No functional dependencies

 On Account-schema: account-number → branch-name
account-number→ balance
 On Depositor-schema: No functional dependencies

Closure of a Set of Functional Dependencies

More formally, given a relational schema R, a functional dependency f on R is logically implied by a set
of functional dependencies F on R if every relation instance r(R) that satisfies F also satisfies f.
Suppose we are given a relation schema R = (A, B, C, G, H, I) and the set of functional dependencies
A →B
A →C
CG→ H
CG→ I
B→H
The functional dependency
DEPT OF CSE Page 8
A→ H

is logically implied. That is, we can show that, whenever our given set of functional dependencies holds
on a relation, A→H must also hold on the relation. Suppose that t1 and t2 are tuples such that
t1[A] = t2[A]
Since we are given that A→B, it follows from the definition of functional dependency that
t1[B] = t2[B]
Then, since we are given that B → H, it follows from the definition of functional dependency that
t1[H] = t2[H]
Therefore, we have shown that, whenever t1 and t2 are tuples such that t1[A] = t2[A], it must be that
t1[H] = t2[H]. But that is exactly the definition of A→ H.

We can use the following three rules to find logically implied functional dependencies. By applying
these rules repeatedly, we can find all of F+, given F. This collection of rules is called Armstrong’s
axioms in honor of the person who first proposed it.
• Reflexivity rule. If α is a set of attributes and β ⊆α, then α →β holds.
• Augmentation rule. If α → β holds and γ is a set of attributes, then γα → γβ holds.
• Transitivity rule. If α →β holds and β → γ holds, then α → γ holds.

Although Armstrong’s axioms are complete, it is tiresome to use them directly for the computation of
F+. To simplify matters further, we list additional rules. It is possible to use Armstrong’s axioms to
prove that these rules are correct .

• Union rule. If α → β holds and α → γ holds, then α →βγ holds.

• Decomposition rule. If α →βγ holds, then α → β holds and α →γ holds.
• Pseudo transitivity rule. If α→β holds and γβ →δ holds, then αγ →δ holds.

Closure of Attribute Sets

To test whether a set α is a superkey, we must devise an algorithm for computing the set of
attributes functionally determined by α. One way of doing this is to compute F+, take all functional
dependencies with α as the left-hand side, and take the union of the right-hand sides of all such
dependencies.However, doing so can be expensive, since F+ can be large.

DEPT OF CSE Page 9

 F+ = F
repeat
for each functional dependency f in F+
apply reflexivity and augmentation rules on f
add the resulting functional dependencies to F+
for each pair of functional dependencies f1 and f2 in F+
if f1 and f2 can be combined using transitivity
add the resulting functional dependency to F+
until F+ does not change any further

Let α be a set of attributes.We call the set of all attributes functionally determined by α under a set F of
functional dependencies the closure of α under F; we denote it by α+. The input is a set F of functional
dependencies and the set α of attributes. The output is stored in the variable result. The first time that
we execute the while loop to test each functional dependency, we find that
• A → B causes us to include B in result. To see this fact, we observe that A → B is in F, A ⊆result (which
is AG), so result :=result ∪B.
• A→ C causes result to become ABCG.
• CG→H causes result to become ABCGH.
• CG→I causes result to become ABCGHI.

It turns out that, in the worst case, this algorithm may take an amount of time quadratic in the size of F.
There is a faster (although slightly more complex) algorithm that runs in time linear in the size of F.

result:= α;
while(changes to result) do
for each functional dependency β → γ in F do
begin
ifβ ⊆result then result := result ∪γ;
end

There are several uses of the attribute closure algorithm:

 To test if α is a superkey, we compute α+, and check if α+ contains all attributes of R.

DEPT OF CSE Page 10

  We can check if a functional dependency α → β holds (or, in other words, is in F+), by checking if
β ⊆α+. That is, we compute α+ by using attribute closure, and then check if it contains β.
 It gives us an alternative way to compute F+: For each γ ⊆R, we find the closure γ+, and for each
S ⊆γ+, we output a functional dependency γ → S.

Canonical Cover

Suppose that we have a set of functional dependencies F on a relation schema. Whenever a user
performs an update on the relation, the database system must ensure that the update does not violate
any functional dependencies, that is, all the functional dependencies in F are satisfied in the new
database state. The system must roll back the update if it violates any functional dependencies in the set
F.
An attribute of a functional dependency is said to be extraneous if we can remove it without
changing the closure of the set of functional dependencies. The formal definition of extraneous
attributes is as follows. Consider a set F of functional dependencies and the functional dependency α
→β in F.
• Attribute A is extraneous in α ifA ∈α, and F logically implies (F − {α →β}) ∪ {(α − A) → β}.
• Attribute A is extraneous in β if A ∈β, and the set of functional dependencies
(F − {α →β}) ∪ {α → (β − A)} logically implies F.

Consider an attribute A in a dependency α → β.

• If A ∈β, to check if A is extraneous consider the set F_ = (F − {α → β}) ∪ {α → (β − A)}and check if α → A
can be inferred fromF_. To do so, compute α+ (the closure of α) under F_; if α+ includes A, then A is
extraneous in β.
• If A ∈α, to check if A is extraneous, let γ = α − {A}, and check if γ → βcan be inferred from F. To do so,
compute γ+ (the closure of γ) under F; if γ+includes all attributes in β, then A is extraneous in α.

A canonical cover Fc for F is a set of dependencies such that F logically implies all dependencies
in Fc, and Fc logically implies all dependencies in F. Furthermore, Fcmust have the following properties:
• No functional dependency in Fc contains an extraneous attribute.
• Each left side of a functional dependency in Fc is unique. That is, there are no two dependencies α1 →
β1 and α2 → β2 in Fc such that α1 = α2.

DEPT OF CSE Page 11

2.Explain Decomposition? (11 Marks)

Consider an alternative design in which we decompose Lending-schema into the following two
schemas:
Branch-customer-schema = (branch-name, branch-city, assets, customer-name)
Customer-loan-schema = (customer-name, loan-number, amount)

Using the lending relation of Figure 7.1,we construct our new relations branch-customer
(Branch-customer) and customer-loan (Customer-loan-schema):
branch-customer= Π branch-name, branch-city, assets, customer-name (lending)
customer-loan= Π customer-name, loan-number, amount (lending)

It appears that we can do so by writing

branch-customer� customer-loan

The relation branch-customer.

DEPT OF CSE Page 12

 The relation customer-loan.

The relation branch-customer � customer-loan.

Desirable Properties of Decomposition

We illustrate our concepts with the Lending schema

Lending-schema = (branch-name, branch-city, assets, customer-name,
loan-number, amount)

DEPT OF CSE Page 13

The set F of functional dependencies that we require to hold on Lending-schema are
branch-name→ branch-city assets
loan-number→ amount branch-name
Lending-schema is an example of a bad database design. Assume that we decompose it to the following
three relations:
Branch-schema = (branch-name, branch-city, assets)
Loan-schema = (loan-number, branch-name, amount)
Borrower-schema = (customer-name, loan-number)

Lossless-Join Decomposition

Let R be a relation schema, and let F be a set of functional dependencies on R. Let R1 and R2 form a
decomposition of R. This decomposition is a lossless-join decomposition of R if at least one of the
following functional dependencies is in F+:
• R1 ∩ R2 → R1
• R1 ∩ R2 → R2
In other words, if R1 ∩ R2 forms a superkey of either R1 or R2, the decomposition of R is a lossless-join
decomposition.

We now demonstrate that our decomposition of Lending-schema is a lossless-join decomposition by

showing a sequence of steps that generate the decomposition. We begin by decomposing Lending-
schema into two schemas:
Branch-schema = (branch-name, branch-city, assets)
Loan-info-schema = (branch-name, customer-name, loan-number, amount)
Since branch-name → branch-city assets, the augmentation rule for functional dependencies implies
that
branch-name→ branch-name branch-city assets
Since Branch-schema ∩ Loan-info-schema = {branch-name}, it follows that our initial decomposition is
a lossless-join decomposition. Next, we decompose Loan-info-schema into
Loan-schema = (loan-number, branch-name, amount)
Borrower-schema = (customer-name, loan-number)
This step results in a lossless-join decomposition, since loan-number is a common attribute and loan-
number → amount branch-name.

DEPT OF CSE Page 14

Dependency Preservation

To decide whether joins must be computed to check an update, we need to determine what
functional dependencies can be tested by checking each relation individually. Let F be a set of functional
dependencies on a schema R, and let R1, R2, . . . ,Rn be a decomposition of R. The restriction of F to Riis
the set Fi of all functional dependencies in F+ that include only attributes of Ri. Since all functional
dependencies in a restriction involve attributes of only one relation schema, it is possible to test such a
dependency for satisfaction by checking only one relation.

We consider each member of the set F of functional dependencies that we require to hold on Lending-
schema, and show that each one can be tested in at least one relation in the decomposition.
• We can test the functional dependency: branch-name → branch-city assets using Branch-schema =
(branch-name, branch-city, assets)
• We can test the functional dependency: loan-number → amount branch-name using Loan-schema =
(branch-name, loan-number, amount).

Compute F+;
for each schema Riin D do
begin
Fi : = the restriction of F+ to Ri;
end
F_ := ∅
for each restriction Fi do
begin
F_ = F_ ∪Fi
end
compute F_+;
if(F_+ = F+) then return (true)
else return (false);

DEPT OF CSE Page 15

Repetition of Information

In the decomposition, the relation on schema Borrower schema contains the loan-number, customer-
name relationship, and no other schema does. Therefore, we have one tuple for each customer for a
loan in only the relation on Borrower-schema. In the other relations involving loan-number (those on
schemasLoan-schema and Borrower-schema), only one tuple per loan needs to appear.

3.Explain in detail about Boyce–Codd Normal Form? (11 Marks)

Definition

One of the more desirable normal forms that we can obtain is Boyce–Codd normal form (BCNF). A
relation schema R is in BCNF with respect to a set F of functionaldependencies if, for all functional
dependencies in F+ of the form α → β, where α ⊆R and β ⊆R, at least one of the following holds:
• α→ β is a trivial functional dependency (that is, β ⊆α).
• αis a superkey for schema R.

A database design is in BCNF if each member of the set of relation schemas that constitutes the design is
in BCNF. Consider the following relation schemas and their respective functional dependencies:
• Customer-schema = (customer-name, customer-street, customer-city) customer-name → customer-
street customer-city
• Branch-schema = (branch-name, assets, branch-city) branch-name → assets branch-city
• Loan-info-schema = (branch-name, customer-name, loan-number, amount) loan-number → amount
branch-name

It is now possible to avoid redundancy in the case where there are several customers associated with a
loan. There is exactly one tuple for each loan in the relation on Loan-schema, and one tuple for each
customer of each loan in the relation on Borrower-schema. Thus, we do not have to repeat the branch
name and the amount once for each customer associated with a loan. Often testing of a relation to see if
it satisfies BCNF can be simplified:

 To check if a nontrivial dependency α → β causes a violation of BCNF, compute α+ (the attribute

closure of α), and verify that it includes all attributes of R; that is, it is a superkey of R.

DEPT OF CSE Page 16

  To check if a relation schema R is in BCNF, it suffices to check only the dependencies in the given
set F for violation of BCNF, rather than check all dependencies in F

Decomposition Algorithm

The decomposition that the algorithm generates is not only in BCNF, but is also a lossless-join
decomposition. To see why our algorithm generates only lossless-join decompositions, we note that,
when we replace a schema Riwith (Ri−β) and (α, β), the dependency α →β holds, and (Ri−β) ∩(α, β) = α.
result:= {R};
done:= false;
computeF+;
while(not done) do
if(there is a schema Riin result that is not in BCNF)
then begin
letα →β be a nontrivial functional dependency that holds
onRisuch that α →Riis not in F+, and α ∩β = ∅;
result:= (result −Ri) ∪(Ri−β) ∪( α, β);
end
elsedone := true;

Lending-schema = (branch-name, branch-city, assets, customer-name,loan-number, amount)

The set of functional dependencies that we require to hold on Lending-schema are
branch-name→assets branch-city
loan-number→amount branch-name
A candidate key for this schema is {loan-number, customer-name}.
We can apply the algorithm of Figure 7.13 to the Lending-schema example as follows:
•The functional dependency
branch-name→assets branch-city
holds on Lending-schema, but branch-name is not a superkey. Thus, Lending schema is not in BCNF. We
replace Lending-schema by
Branch-schema = (branch-name, branch-city, assets)
Loan-info-schema = (branch-name, customer-name, loan-number, amount)

DEPT OF CSE Page 17

Dependency Preservation

Banker-schema = (branch-name, customer-name, banker-name)

which indicates that a customer has a “personal banker” in a particular branch. The set F of functional
dependencies that we require to hold on the Banker-schema is
banker-name → branch-name
branch-name customer-name → banker-name
Clearly, Banker-schema is not in BCNF since banker-name is not a superkey. If we apply the algorithm
we obtain the following BCNF decomposition:
Banker-branch-schema = (banker-name, branch-name)
Customer-banker-schema = (customer-name, banker-name)
The decomposed schemas preserve only banker-name → branch-name (and trivial dependencies), but
the closure of {banker-name → branch-name} does not include customer-name branch-name → banker-
name. The violation of this dependency cannot be detected unless a join is computed.

Thus, the example shows that we cannot always satisfy all three design goals:
1. Lossless join
2. BCNF
3. Dependency preservation

4.Explain about third normal form? (11 Marks)

We have two alternatives if we wish to check if an update violates any functional dependencies:
• Pay the extra cost of computing joins to test for violations.
• Use an alternative decomposition, third normal form (3NF), which we present below, which makes
testing of updates cheaper. Unlike BCNF, 3NF decompositions may contain some redundancy in the
decomposed schema.

Definition
BCNF requires that all nontrivial dependencies be of the form α → β, where α is a superkey. 3NF relaxes
this constraint slightly by allowing nontrivial functional dependencies whose left side is not a superkey.

DEPT OF CSE Page 18

A relation schema R is in third normal form (3NF) with respect to a set F of functional dependenciesif,
for all functional dependencies in F+ of the form α → β, where α ⊆ R and β ⊆ R, at least one of the
following holds:
 α → β is a trivial functional dependency.
 α is a superkey for R.
 Each attribute A in β − α is contained in a candidate key for R.

The first two alternatives are the same as the two alternatives in the definition of BCNF. The third
alternative of the 3NF definition seems rather unintuitive, and it is not obvious why it is useful. It
represents, in some sense, a minimal relaxation of the BCNF conditions that helps ensure that every
schema has a dependency-preserving decomposition into 3NF. Its purpose will become more clear
later, when we study decomposition into 3NF.

The only nontrivial functional dependencies of the form α → banker-name include {customer-name,
branch-name} as part of α. Since {customer-name, branch-name} is a candidate key, these dependencies
do not violate the definition of 3NF.

Decomposition Algorithm

The set of dependencies Fc used in the algorithm is a canonical cover for F.Note that the
algorithm considers the set of schemas Rj, j = 1, 2, . . . , i; initially i = 0, and in this case the set is empty.

let Fc be a canonical cover for F;

i := 0;
for each functional dependency α → β in Fc do
if none of the schemas Rj, j = 1, 2, . . . , i contains αβ
then begin
i := i + 1;
Ri := αβ;
end
if none of the schemas Rj, j = 1, 2, . . . , i contains a candidate key for R
then begin
i := i + 1;

DEPT OF CSE Page 19

 Ri := any candidate key for R;
end
return (R1,R2, . . .,Ri)
Banker-info-schema = (branch-name, customer-name, banker-name, office-number)
The main difference here is that we include the banker’s office number as part of the information. The
functional dependencies for this relation schema are
banker-name → branch-name office-number
customer-name branch-name → banker-name
The for loop in the algorithm causes us to include the following schemas in our decomposition:
Banker-office-schema = (banker-name, branch-name, office-number)
Banker-schema = (customer-name, branch-name, banker-name)
Let us consider the three possible cases:
 B is in both α and β. In this case, the dependency α → β would not have been in Fc since B would
be extraneous in β. Thus, this case cannot hold.
 B is in β but not α. Consider two cases:
- γ is a superkey. The second condition of 3NF is satisfied.
- γ is not a superkey. Then α must contain some attribute not in γ. Now, since γ → B is in F+, it
must be derivable from Fc by using the attribute closure algorithm on γ. The derivation could
not have used α → β— if it had been used, α must be contained in the attribute closure of γ,
which is not possible, since we assumed γ is not a superkey. Now, using α → (β −{B}) and γ → B,
we can derive α → B (since γ ⊆ αβ, and γ cannot contain B because γ → B is nontrivial). This
would imply that B is extraneous in the right hand side of α → β, which is not possible since α →
β is in the canonical cover Fc. Thus, if B is in β, then γ must be a superkey, and the second
condition of 3NF must be satisfied.
 B is in α but not β. Since α is a candidate key, the third alternative in the definition of 3NF is
satisfied.
5..Explain about fourth normal form? (11 Marks)
BC-schema = (loan-number, customer-name, customer-street, customer-city)
The astute reader will recognize this schema as a non-BCNF schema because of the functional
dependency
customer-name → customer-street customer-city

DEPT OF CSE Page 20

Multivalued Dependencies

Functional dependencies rule out certain tuples from being in a relation. If A → B, then we cannot have
two tuples with the same A value but different B values. Multivalued dependencies, on the other hand,
do not rule out the existence of certain tuples. Instead, they require that other tuples of a certain form
be present in the relation. For this reason, functional dependencies sometimes are referred to as
equality generating dependencies, and multivalued dependencies are referred to as tuple
generating dependencies.
Let R be a relation schema and let α ⊆ R and β ⊆ R. The multivalued dependency
α →→ β
holds on R if, in any legal relation r(R), for all pairs of tuples t1 and t2 in r such that t1[α] = t2[α], there
exist tuples t3 and t4 in r such that

t1[α] = t2[α] = t3[α] = t4[α]

t3[β] = t1[β]
t3[R − β] = t2[R − β]
t4[β] = t2[β]
t4[R − β] = t1[R − β]

As with functional dependencies, we shall use multivalued dependencies in two ways:

1. To test relations to determine whether they are legal under a given set of functional and multivalued
dependencies
2. To specify constraints on the set of legal relations; we shall thus concern ourselves
with only those relations that satisfy a given set of functional and multivalued
dependencies.

From the definition of multivalued dependency, we can derive the following rule:
• If α → β, then α →→ β.
In other words, every functional dependency is also a multivalued dependency.

Definition of Fourth Normal Form

Consider again our BC-schema example in which the multivalued dependency customer
name→→customer-street customer-city holds, but no nontrivial functional dependencies hold.We saw

DEPT OF CSE Page 21

in the opening paragraphs of Section 7.8 that, although BCschema is in BCNF, the design is not ideal,
since we must repeat a customer’s address information for each loan. We shall see that we can use the
given multivalued dependency to improve the database design, by decomposing BC-schema into a
fourth normal form decomposition.
A relation schema R is in fourth normal form (4NF) with respect to a set D of functional and
multivalued dependencies if, for all multivalued dependencies in D+ of the form α →→ β, where α ⊆ R
and β ⊆ R, at least one of the following holds
• α →→ β is a trivial multivalued dependency.
• α is a superkey for schema R.
A database design is in 4NF if each member of the set of relation schemas that constitutes the design is
in 4NF.

result := {R};
done := false;
compute D+; Given schema Ri, let Di denote the restriction of D+ to Ri
while (not done) do
if (there is a schema Ri in result that is not in 4NF w.r.t. Di)
then begin
let α →→ β be a nontrivial multivalued dependency that holds
on Ri such that α → Ri is not in Di, and α ∩ β = ∅;
result := (result − Ri) ∪ (Ri − β) ∪ (α, β);
end
else done := true;

Let R be a relation schema, and let R1,R2, . . . , Rn be a decomposition of R. To check if each relation
schema Ri in the decomposition is in 4NF, we need to find what multivalued dependencies hold on each
Ri. Recall that, for a set F of functional dependencies, the restriction Fi of F to Ri is all functional
dependencies in F+ that include only attributes ofRi.Now consider a setDof both functional and
multivalued dependencies. The restriction of D to Ri is the set Di consisting of
1. All functional dependencies in D+ that include only attributes of Ri
2. All multivalued dependencies of the form
α →→ β ∩ Ri
where α ⊆ Ri and α →→ β is in D+.

DEPT OF CSE Page 22

Decomposition Algorithm
The analogy between 4NF and BCNF applies to the algorithm for decomposing a schema . It is
identical
to the BCNF decomposition algorithm of Figure 7.13, except that it uses multivalued, instead of
functional, dependencies and uses the restriction of D+ to Ri. If we apply the algorithm BC-schema, we
find that customer-name →→ loan-number is a nontrivial multivalued dependency, and customer-name
is not a superkey for BC-schema. Following the algorithm, we replace BC-schema by two schemas:
Borrower-schema = (customer-name, loan-number)
Customer-schema = (customer-name, customer-street, customer-city).
This pair of schemas, which is in 4NF, eliminates the problem we encountered earlier
with the redundancy of BC-schema.

Let R be a relation schema, and let D be a set of functional and multivalued dependencies on R. Let R1
and R2 form a decomposition of R. This decomposition is a lossless-join decomposition of R if and only
if at least one of the following multivalued dependencies is in D+:
R1 ∩ R2 →→ R1
R1 ∩ R2 →→ R2

More Normal Forms

The fourth normal form is by no means the “ultimate” normal form. As we saw earlier, multivalued
dependencies help us understand and tackle some forms of repetition of information that cannot be
understood in terms of functional dependencies. There are types of constraints called join
dependencies that generalize multivalued dependencies, and lead to another normal form called
project-join normal form (PJNF) (PJNF is called fifth normal form in some books). There is a class of
even more general constraints, which leads to a normal form called domain-key normal form.

DEPT OF CSE Page 23