# ITC423 Database Systems Charles Sturt University

- Description
- Full Document

Charles Sturt University

ITC423 Database Systems Charles Sturt UniversityIn the previous chapter we introduced the technique of normalization and the

concept of functional dependencies between attributes. We described the benefits

of using normalization to support database design and demonstrated how attributes

shown on sample forms are transformed into 1NF, 2NF, and 3NF relations. In

this chapter, we return to consider functional dependencies and describe normal

forms that go beyond 3NF such as BCNF, 4NF, and 5NF. Relations in 3NF are

normally sufficiently well structured to prevent the problems associated with data

redundancy, which was described in Section 14.3. However, later normal forms

were created to identify relatively rare problems with relations that, if not corrected,

might result in undesirable data redundancy.

lOMoARcPSD|5735817

482 | Chapter 15 Advanced Normalization

Structure of this Chapter With the exception of 1NF, all normal

forms discussed in the previous chapter and in this chapter are based on

functional dependencies among the attributes of a relation. In Section 15.1 we

continue the discussion on the concept of functional dependency, which was

introduced in the previous chapter. We present a more formal and theoretical

aspect of functional dependencies by discussing inference rules for functional

dependencies.

In the previous chapter we described the three most commonly used normal

forms: 1NF, 2NF, and 3NF. However, R. Boyce and E.F. Codd identified a

weakness with 3NF and introduced a stronger definition of 3NF Boyce-Codd

Normal Form (BCNF) (Codd, 1974), which we describe in Section 15.2. In

Section 15.3 we present a worked example to demonstrate the process of

normalizing attributes originally shown on a report into a set of BCNF relations.

Higher normal forms that go beyond BCNF were introduced later, such as

Fourth (4NF) and Fifth (5NF) Normal Forms (Fagin, 1977, 1979). However,

these later normal forms deal with situations that are very rare. We describe

4NF and 5NF in Sections 15.4 and 15.5.

To illustrate the process of normalization, examples are drawn from the

DreamHome case study described in Section 11.4 and documented in Appendix A.

15.1 More on Functional Dependencies

One of the main concepts associated with normalization is functional dependency,

which describes the relationship between attributes (Maier, 1983). In the previous

chapter we introduced this concept. In this section we describe this concept

in a more formal and theoretical way by discussing inference rules for functional

dependencies.

15.1.1 Inference Rules for Functional Dependencies

In Section 14.4 we identified the characteristics of the functional dependencies

that are most useful in normalization. However, even if we restrict our attention to

functional dependencies with a one-to-one (1:1) relationship between attributes on

the left-hand and right-hand sides of the dependency that hold for all time and are

fully functionally dependent, then the complete set of functional dependencies for

a given relation can still be very large. It is important to find an approach that can

reduce that set to a manageable size. Ideally, we want to identify a set of functional

dependencies (represented as X) for a relation that is smaller than the complete set

of functional dependencies (represented as Y) for that relation and has the property

that every functional dependency in Y is implied by the functional dependencies

in X. Hence, if we enforce the integrity constraints defined by the functional

lOMoARcPSD|5735817

15.1 More on Functional Dependencies | 483

the larger set of functional dependencies in Y. This requirement suggests that

there must be functional dependencies that can be inferred from other functional

dependencies. For example, functional dependencies A ® and ® C in a relation

implies that the functional dependency A ® C also holds in that relation. A ® C is

an example of a transitive functional dependency and was discussed previously in

Sections 14.4 and 14.7.

How do we begin to identify useful functional dependencies on a relation?

Normally, the database designer starts by specifying functional dependencies that

are semantically obvious; however, there are usually numerous other functional

dependencies. In fact, the task of specifying all possible functional dependencies

for “real” database projects is more often than not impractical. However, in this

section we do consider an approach that helps identify the complete set of functional

dependencies for a relation and then discuss how to achieve a minimal set of

functional dependencies that can represent the complete set.

The set of all functional dependencies that are implied by a given set of functional

dependencies X is called the closure of X, written X+. We clearly need a set

of rules to help compute X+ from X. A set of inference rules, called Armstrong’s

axioms, specifies how new functional dependencies can be inferred from given

ones (Armstrong, 1974). For our discussion, let A, B, and C be subsets of the attributes

of the relation R. Armstrong’s axioms are as follows:

(1) Reflexivity: If is a subset of A, then A ®

(2) Augmentation: If A ® , then A,C ® ,C

(3) Transitivity: If A ® and ® C, then A ® C

Note that each of these three rules can be directly proved from the definition of

functional dependency. The rules are complete in that given a set X of functional

dependencies, all functional dependencies implied by X can be derived from X

using these rules. The rules are also sound in that no additional functional dependencies

can be derived that are not implied by X. In other words, the rules can be

used to derive the closure of X+.

Several further rules can be derived from the three given previously that simplify

the practical task of computing X+. In the following rules, let D be another subset

of the attributes of relation R. Then:

(4) Self-determination: A ® A

(5) Decomposition: If A ® ,C, then A ® and A ® C

(6) Union: If A ® and A ® C, then A ® ,C

(7) Composition: If A ® and C ® D then A,C ® ,D

Rule 1 (Reflexivity) and Rule 4 (Self-determination) state that a set of attributes

always determines any of its subsets or itself. Because these rules generate functional

dependencies that are always true, such dependencies are trivial and, as

stated earlier, are generally not interesting or useful. Rule 2 (Augmentation) states

that adding the same set of attributes to both the left-hand and right-hand sides of

a dependency results in another valid dependency. Rule 3 (Transitivity) states that

functional dependencies are transitive. Rule 5 (Decomposition) states that we can

remove attributes from the right-hand side of a dependency. Applying this rule

lOMoARcPSD|5735817

484 | Chapter 15 Advanced Normalization

dependencies A ® , A ® C, and A ® D. Rule 6 (Union) states that we can do the

opposite: we can combine a set of dependencies A ® , A ® C, and A ® D into a

single functional dependency A ® , C, D. Rule 7 (Composition) is more general

than Rule 6 and states that we can combine a set of nonoverlapping dependencies

to form another valid dependency.

To begin to identify the set of functional dependencies F for a relation, we typically

first identify the dependencies that are determined from the semantics of the

attributes of the relation. Then we apply Armstrong’s axioms (Rules 1 to 3) to infer

additional functional dependencies that are also true for that relation. A systematic

way to determine these additional functional dependencies is to first determine

each set of attributes A that appears on the left-hand side of some functional

dependencies and then to determine the set of all attributes that are dependent on

A. Thus, for each set of attributes A, we can determine the set A+ of attributes that

are functionally determined by A based on (A+ is called the closure of A under F).

15.1.2 Minimal Sets of Functional Dependencies

In this section we introduce what is referred to as equivalence of sets of functional

dependencies. A set of functional dependencies Y is covered by a set of functional

dependencies X, if every functional dependency in Y is also in X+; that is,

every de pendency in Y can be inferred from X. A set of functional dependencies X

is minimal if it satisfies the following conditions:

Every dependency in X has a single attribute on its right-hand side.

We cannot replace any dependency A ® in X with dependency C ® , where C

is a proper subset of A, and still have a set of dependencies that is equivalent to X.

We cannot remove any dependency from X and still have a set of dependencies

that is equivalent to X.

A minimal set of dependencies should be in a standard form with no redundancies.

A minimal cover of a set of functional dependencies X is a minimal set of dependencies

X that is equivalent to X. Unfortunately, there can be several minimal covers

for a set of functional dependencies. We demonstrate the identification of the

minimal cover for the StaffBranch relation in the following example.

EXAMPLE 15.1 Identifying the minimal set of functional dependencies of the Staff-

Branch relation

We apply the three conditions described previously on the set of functional dependencies

for the StaffBranch relation listed in Example 14.5 to produce the following functional

dependencies:

staffNo ® sName

staffNo ® position

staffNo ® salary

staffNo ® branchNo

branchNo ® bAddress

bAddress ® branchNo

branchNo, position ® salary

lOMoARcPSD|5735817

15.2 Boyce–Codd Normal Form (BCNF) | 485

These functional dependencies satisfy the three conditions for producing a minimal

set of functional dependencies for the StaffBranch relation. Condition 1 ensures that

every dependency is in a standard form with a single attribute on the right-hand side.

Conditions 2 and 3 ensure that there are no redundancies in the dependencies, either

by having redundant attributes on the left-hand side of a dependency (Condition 2) or

by having a dependency that can be inferred from the remaining functional dependencies

in X (Condition 3).

In the following section we return to consider normalization. We begin by discussing

BCNF, a stronger normal form than 3NF.

15.2 Boyce–Codd Normal Form (BCNF)

In the previous chapter we demonstrated how 2NF and 3NF disallow partial and

transitive dependencies on the primary key of a relation, respectively. Relations that

have these types of dependencies may suffer from the update anomalies discussed

in Section 14.3. However, the definitions of 2NF and 3NF discussed in Sections

14.7 and 14.8, respectively, do not consider whether such dependencies remain on

other candidate keys of a relation, if any exist. In Section 14.9 we presented general

definitions for 2NF and 3NF that disallow partial and transitive dependencies on

any candidate key of a relation, respectively. Application of the general definitions

of 2NF and 3NF may identify additional redundancy caused by dependencies that

violate one or more candidate keys. However, despite these additional constraints,

dependencies can still exist that will cause redundancy to be present in 3NF relations.

This weakness in 3NF resulted in the presentation of a stronger normal form

called Boyce–Codd Normal Form (BCNF: Codd, 1974).

15.2.1 Definition of BCNF

BCNF is based on functional dependencies that take into account all candidate keys

in a relation; however, BCNF also has additional constraints compared with the

general definition of 3NF given in Section 14.9.

A relation is in BCNF if and only if every determinant is

a candidate key.

Boyce–Codd Normal

Form (BCNF)

To test whether a relation is in BCNF, we identify all the determinants and make

sure that they are candidate keys. Recall that a determinant is an attribute, or a

group of attributes, on which some other attribute is fully functionally dependent.

The difference between 3NF and BCNF is that for a functional dependency

A ® , 3NF allows this dependency in a relation if is a primary-key attribute and

A is not a candidate key, whereas BCNF insists that for this dependency to remain

in a relation, A must be a candidate key. Therefore, BCNF is a stronger form of

3NF, such that every relation in BCNF is also in 3NF. However, a relation in 3NF

is not necessarily in BCNF.

Before considering the next example, we re-examine the Client, Rental,

PropertyForRent, and Owner relations shown in Figure 14.17. The Client, PropertyForRent,

and Owner

**Preview**

**NOTE: Please check the details before purchasing the document.**