Teorey J., Lightstone S., Nadeau T. Database Modeling and Design: Logical Design

Подождите немного. Документ загружается.

the composite key is the weakest form of data dependency.

If, however, tables A and B represent the supertype and

subtype cases, respectively, of entities defined by the gen-

eralization abstraction, and A subsumes B because B has

no additional specific attributes, the designer must collect

and analyze additional information to decide whether or

not to eliminate B.

A table can also be subsumed by the construction of a

join of two other tables (a “join” table). When this occurs,

the elimination of a subsumed table may result in the loss

of retrieval efficiency, although storage and update costs

will tend to be decreased. This trade-off must be further

analyzed during physical design with regard to processing

requirements to determine whether elimination of the sub-

sumed table is reasonable.

To continue our example company personnel and proj-

ect database, we want to obtain the primary FDs by apply-

ing the rules in Table 6.2 to

each relationship in the

diagram in Figure 4.3 (see Chapter 4). The results are

shown in Table 6.3.

Next we want to determine the secondary FDs. Let us

assume

that the dependencies in Table

6.4 ar

derived

from

the

equir

ements specification and intuition.

Table 6.2 Primary FDs Derivable from ER

Constructs

Degree Connectivity Primary FD

Binary or one-to-one 2 ways: key(one side) -> key(one side)

Binary Recursive one-to-many key(many side) -> key(one side)

many-to-many none (composite key from both sides)

Ternary one-to-one-to-one 3 ways: key(one), key(one) -> key(one)

one-to-one-to-many 2 ways: key(one), key(many) -> key(one)

one-to-many-to-many 1 way: key(many), key(many) -> key(one)

many-to-many-to-many none (composite key from all three sides)

Generalization none none (secondary FD only)

Chapter 6 NORMALIZATION 121

Normalization of the candidate tables is accomplished

next. In Table 6.5 we bring together the primary and

sec-

ondary FDs that apply to each candidate table. We note

that for each table except employee, all attributes are func-

tionally dependent on the primary key (denoted by the left

Table 6.3 Primary FDs Derived from the

ER diagram in Figure 4.3

dept_no -> div_no in Department from relationship “contains”

emp_id -> dept_no in Employee from relationship “has ”

div_no -> emp_id in Division from relationship “is-headed-by”

dept_no -> emp_id from binary relationship “is-managed-by”

emp_id -> desktop_no from binary relationship “is-allocated”

desktop_no -> emp_id from binary relationship “is-allocated”

emp_id -> workstation_no from binary relationship “has-allocated”

workstation_no -> emp_id from binary relationship "has-allocated"

emp_id -> spouse_id from binary recursive relationship “is-married-to”

spouse_id -> emp_id from binary recursive relationship “is-married-to”

emp_id, loc_name -> project_name from ternary relationship “assigned-to”

Table 6.4 Secondary FDs Derived from the

Requirements Specification

FD Entity

div_no -> div_name, div_addr Division

dept_no -> dept_name, dept_addr, mgr_id Department

emp_id -> emp_name, em p_addr, office_no, phone_no Employee

skill_type -> skill_descrip Skill

project_name -> start_date, end_date, head_id Project

loc_name -> loc_county, loc_state, zip Location

mgr_id -> mgr_start_date, beeper_phone_no Manager

assoc_name -> assoc_addr, phone_no, start_date Prof-assoc

desktop_no -> computer_type, serial_no Desktop

workstation_no -> computer_type, serial_no Workstation

122 Chapter 6 NORMALIZATION

side of the FDs), and are thus BCNF. In the case of the

employee table we note that spouse_id determines emp_id

and emp_id is the primary key; thus, spouse_id can be

shown to be a superkey (see Superkey Rule 2 in the “Deter-

mining the Minimum Set of 3NF Tables” section). There-

fore, employee is found to be BCNF.

In general, we observe that candidate tables, like the

ones shown in Table 6.5,

are fairly good indicators of the

final schema and normally r

equire very little refinement

to get to 3NF or BCNF. This observation is important—

good initial conceptual design usually results in tables

Table 6.5 Candidate Tables (and FDs) from ER

Diagram Transformation

division div_no -> div_name, div_addr

div_no -> emp_id

department dept_no -> dept_name, dept_addr, mgr_id

dept_no -> div_no

dept_no -> emp_id

employee emp_id - > emp_name, emp_addr, office_no, phone_no

emp_id - > dept_no

emp_id - > spouse_id

spouse_id -> em p_id

manager mgr_id -> mgr_start_date, beeper_phone_no

secretary none

engineer emp_id - > desktop_no

technician none

skill skill_type -> skill_descrip

project project_name -> start_date, end_date, head_id

location loc_name -> loc_county, loc_state, zip

prof_assoc assoc_name -> assoc_addr, phone_no, start_date

desktop desktop_no -> computer_type, serial_no

desktop_no -> emp_id

workstation workstation_no -> computer_type, serial_no

workstation_no -> emp_id

assigned_to emp_id, loc_name -> project_name

skill_used none

belongs_to none

Chapter 6 NORMALIZATION 123

that are already normalized or are very close to being

normalized, and thus the normalization process is usually

a simple task.

Determining the Minimum

Set of 3NF Tables

A minimum set of 3NF tables can be obtained from

a given set of FDs by using the well-known synthesis

algorithm developed by Bernstein (1976). This process is

particularly useful when you are confronted with a list of

hundreds or thousands of FDs that describe the semantics

of a database. In practice, the ER modeling process automat-

ically decomposes this problem into smaller subproblems:

The attributes and FDs of interest are restricted to those

attributes within an entity (and its equivalent table) and

any foreign keys that might be imposed upon that table.

Thus, the database designer will rarely have to deal with

more than 10 or 20 attributes at a time, and in fact, most

entities are initially defined in 3NF already. For those tables

that are not yet in 3NF, only minor adjustments will be

needed in most cases.

In the following, we briefly describe the synthesis algo-

rithm for those situations where the ER model is not useful

for the decomposition. In order to apply the algorithm, we

make use of the well-known Armstrong axioms, which

define the basic relationships among FDs.

Inference Rules (Armstrong Axioms)

Reflexivity If Y is a subset of the attributes of X, then X ->

Y (i.e., if X is ABCD and Y is ABC, then X -> Y;

trivially, X -> X).

Augmentation If X -> Y and Z is a subset of table R (i.e., Z

is any attribute in R), then XZ -> YZ.

Transitivity If X -> Y and Y -> Z, then X -> Z.

Pseudotransitivity If X -> Y and YW -> Z, then XW -> Z.

(Transitivity is a special case of

pseudotransitivity when W ¼ null.)

Union If X -> Y and X -> Z, then X -> YZ (or

equivalently X -> Y,Z).

Decomposition If X -> YZ, then X -> Y and X -> Z.

124 Chapter 6 NORMALIZATION

These axioms can be used to derive two practical rules

of thumb for deriving superkeys of tables where at least

one superkey is already known.

Superkey Rule 1 Any FD involving all attributes of a table

defines a superkey as the left side of the FD.

Given: Any FD containing all attributes in the table R(W,

X,Y,Z), i.e. XY -> WZ.

Proof:

1. XY

-> WZ as given.

2. XY - > XY b

y applying the reflexivity axiom.

3. XY - > XYWZ by applying the union axiom.

4. XY uniquely determines every attribute in table R,as

shown in 3.

5. XY uniquely defines table R, by the definition of a table

as having no duplicate rows.

6. XY is therefore a superkey, by definition.

Superkey Rule 2 Any attribute that functionally determines

a superkey of a table is also a superkey for that table.

Given: Attribute A is a superkey for table R(A,B,C,D,E),

and E -> A.

Proof:

1. Attribute A uniquely defines each row in table R, by the

definition of

a superkey.

2. A-> ABCDE by applying the definition of a superkey

and a relational table.

3. E-> A as given.

4. E-> ABCDE by applying the transitivity axiom.

5. E is a superkey for table R, by definition.

Before we can describe the synthesis algorithm, we

must define some important concepts. Let H be a set of

FDs that represents at least part of the known semantics

of a database. The closure of H, specified by H

, is the

set of all FDs derivable from H using the Armstrong axioms

or inference rules. For example, we can apply the transitiv-

ity rule to the following FDs in set H:

A-> B, B - > C, A -> C, and C -> D

to derive the FDs A -> DandB-> D . All six FDs constitute the

closure H

.AcoverofH,calledH

,isanysetofFDsfrom

which H

can be derived. P o ssible covers for this example are:

1. A-> B, B -> C, C -> D, A -> C, A -> D, B -> D (trivial

case where H

and H

are equal)

Chapter 6 NORMALIZATION 125

2. A-> B, B -> C, C -> D, A -> C, A -> D

3. A-> B, B -> C, C -> D, A -> C (this is the original set H)

4. A-> B, B -> C, C -> D

A nonredundant cover of H is a cover of H that contains

no proper subset of FDs that is also a cover. In this exam-

ple, cover 4 is nonredundant. The following synthesis

algorithm requires nonredundant covers.

3NF Synthesis Algorithm

Given a set of FDs, H, we determine a minimum set of

tables in 3NF.

H: AB - > CDM-> NP

A-> DEFG D -> M

E-> GL-> D

F-> DJ PQR -> ST

G-> DI PR -> S

D-> KL

From this point the process of arriving at the minimum

set of 3NF tables consists of five steps:

1. Eliminate extraneous attributes in the left sides of the

FDs.

2. Search for a nonredundant cover, G of H.

3. Partition G into groups so that all FDs with the same left

side are in one group.

4. Merge equivalent keys.

5. Define the minimum set of normalized tables.

Now we discuss each step in turn, in terms of the pre-

ceding set of FDs, H.

Step 1: Elimination of Extraneous Attributes

The first task is to get rid of extraneous attributes in the

left sides of the FDs. The following two relationships (rules)

among attributes on the left side of an FD provide the

means to reduce the left side to fewer attributes.

Reduction Rule 1 XY -> ZandX-> Z ¼> Yisextraneouson

the left side (applying the reflexivity and transitivity axioms).

Reduction Rule 2 XY -> Z and X -> Y ¼> Y is extraneous;

therefore, X -> Z (applying the pseudotransitivity axiom).

126 Chapter 6 NORMALIZATION

Applying these reduction rules to the set of FDs in H,

we get:

DM -> NP and D -> M ¼> D-> NP

PQR -> ST and PR -> S ¼> PQR -> T

Step 2: Search for a Nonredundant Cover

We must eliminate any FD derivable from others in H

using the inference rules. The transitive FDs to be

eliminated are:

A-> E and E -> G ¼> eliminate A - > G

A-> F and F -> D ¼> eliminate A -> D

Step 3: Partitioning of the Nonredundant Cover

To partition the nonredundant cover into groups so that

all FDs with the same left side are in one group, we must

separate the nonfully functional dependencies and transi-

tive dependencies into separate tables. At this point we

have a feasible solution for 3NF tables, but it is not neces-

sarily the minimum set.

These nonfully functional dependencies must be put

into separate groups (potential tables):

AB -> C

A-> EF

The groups with the same left side are:

G1: AB -> C

G2: A -> EF

G3: E -> G

G4: G -> DI

G5: F -> DJ

G6: D -> KLMNP

G7: L -> D

G8: PQR -> T

G9: PR -> S

Step 4: Merge of Equivalent Keys (Merge of Tables)

In this step we merge groups with left sides that are

equivalent (e.g., X -> Y and Y -> X imply that X and Y are

equivalent). This step produces a minimum set of tables.

1. Write out the closure of all left side attributes resulting

from Step 3, based on transitivities.

2. Using the closures, find tables that are subsets of other

groups and try to merge them. Use Superkey Rule 1 and

Superkey Rule 2 to establish if the merge will result in

FDs with superkeys on the left side. If not, try using the

axioms to modify the FDs to fit the definition of superkeys.

Chapter 6 NORMALIZATION 127

3. After the subsets are exhausted, look for any overlaps

among tables and apply Superkey Rules 1 and 2 (and

the axioms) again.

In this example, note that G7 (L -> D) has a subset of

the attributes of G6 (D -> KLMNP). Therefore, we merge

to a single table, R6, with FDs D -> KLMNP, L -> D,

because it satisfies 3NF: D is a superkey by Superkey Rule

1 and L is a superkey by Superkey Rule 2.

Step 5: Definition of the Minimum Set of Normalized Tables

The minimum set of normalized tables has now been

determined. We define these tables below in terms of the

table name, the attributes in the table, the FDs in the table,

and the candidate keys for that table:

R1: ABC (AB -> C with key AB)

R2: AEF (A -> EF with key A)

R3:EG(E-> G with key E)

R4: DGI (G -> DI with key G)

R5: DFJ (F -> DJ with key F)

R6: DKLMNP (D -> KLMNP, L -> D, with keys D, L)

R7: PQRT (PQR -> T with key PQR)

R8: PRS (PR -> S with key PR)

Note that this result is not only 3NF, but also BCNF,

which is very frequently the case. This fact suggests a prac-

tical algorithm for a (near) minimum set of BCNF tables:

Use Bernstein’s algorithm to attain a minimum set of 3NF

tables, then inspect each table for further decomposition

(or partial replication, as shown in the “Boyce-Codd Nor-

mal Form” section above) to BCNF.

Summary

In this chapter we defined the constraints imposed on

tables, most commonly the functional dependencies, or FDs.

Based on these constraints, practical normal forms for data-

basetablesaredefined:1NF,2NF,3NF,andBCNF.Allare

based on the types of FDs present. In this chapter, a practical

algorithm for finding the minimum set of 3NF tables is given.

The following statements summarize the functional

equivalence between the ER model and normalized tables:

1. Within an entity. The level of normalization is totally

dependent on the interrelationships among the key

128 Chapter 6 NORMALIZATION

and nonkey attributes. It could be any form from

unnormalized to BCNF.

2. Binary (or binary recursive) one-to-one or one-to-many

relationship. Within the “child” entity, the foreign key

(a replication of the primary key of the “parent”) is func-

tionally dependent on the child’s primary key. This is at

least BCNF, assuming that the entity by itself, without

the foreign key, is already BCNF.

3. Binary (or binary recursive) many-to-many relationship.

The intersection table has a composite key and possibly

some nonkey attributes functionally dependent on it.

This is BCNF.

4. Ternary relationship:

a. one-to-one-to-one ¼> three overlapping composite

keys, BCNF

b. one-to-one-to-many ¼> two overlapping composite

keys, BCNF

c. one-to-many-to-many ¼> one composite key, BCNF

d. many-to-many-to-many ¼ > one composite key with

three attributes, BCNF

In summary, we observed that a good, methodical con-

ceptual design procedure often results in database tables

that are either normalized (BCNF) already, or can be nor-

malized with very minor changes.

Tips and Insights for Database

Professionals

Tip 1. Analyze the potential for performance benefits

first before normalizing; you want to see if perfor-

mance gains can be had.

a. Potential to reduce storage space by reducing redun-

dancy (potential, but not guaranteed).

b. Potential to reduce update time (as a result of

reducing redundancy).

c. Potential to reduce query time (as a result of

smaller tables).

Tip 2. Boyce-Codd normal form (BCNF), a variant of

third normal form (3NF), is the most practical goal

for tables in relational databases. It is easy to con-

ceptualize (has the simplest definition) and eliminates

Chapter 6 NORMALIZATION 129

almost all delete anomalies, and thus preserves data

integrity to a high degree. Most entities in ER models

translate directly to BCNF tables. Those entities that

don’t can usually be split into BCNF tables by simple

decomposition applying the BCNF definition.

Tip 3. Consider denormalization if performance is

compromised too much by normalization. Sometimes

you can trade off the increase in update cost due to

redundancy versus lower query cost due to redundancy,

and still maintain data integrity.

Literature Summary

Good summaries of normal forms can be found in Date

(2003), Kent (1983), Dutka and Hanson (1989), and Smith

(1985). Algorithms for normal form decomposition and

synthesis techniques are given in Bernstein (1976), Fagin

(1977), and Maier (1983). The earliest work done in normal

forms was by Codd (1970, 1974) and by Armstrong (1974).

130 Chapter 6 NORMALIZATION