Normal

10.3 Normal Forms Based on Primary Keys 10.3.1 10.3.2 10.3.3 10.3.4 10.3.5 10.3.6

Normalization of Relations Practical Use of Normal Forms Definitions of Keys and Attributes Participating in Keys First Normal Form Second Normal Form Third Normal Form p 312 Chapter 10-1

10.3.1 Normalization of Relations  Normalization: The process of decomposing unsatisfactory "bad" relations by breaking up their attributes into smaller relations  The normal form of a relation refers to the highest normal form condition that a relation meets and indicates the degree to which it has been normalized.

Chapter 10-2

10.3.2 Practical Use of Normal Forms  Normalization is carried out in practice so that the resulting designs are of high quality and meet the desirable properties  Normalization in industry pays particular attention to normalization up to 3NF, BCNF, or 4NF.  We will pay particular attention up to 3NF.

Chapter 10-3

10.3.2 Practical Use of Normal Forms  The database designers need not normalize to the highest possible normal form.  Denormalization: the process of storing the join of higher normal form relations as a base relation—which is in a lower normal form.

Chapter 10-4

An Unnormalized Relation An unnormalized table contains one or more repeating groups.

Is the following table unnormalized? Why or why not? RENTAL transId

date

customerId

rentalItems

Chapter 10-5

10.3.2 First Normal Form (1NF) Disallows composite attributes, multi-valued attributes, and nested relations; i.e., disallows attributes whose values for an individual tuple are non-atomic. Considered to be part of the definition of relation. Chapter 10-6

Figure 10.8 Normalization into 1NF

Chapter 10-7

Problem

Why remove the redundancy in the DNUMBER attribute? How can we remove the redundancy?

Chapter 10-8

Figure 10.8 Normalization into 1NF Place DLOCATION in a separate relation along with the primary key of DEPARTMENT.

p 137 Chapter 10-9

Video Rental Example Unnormalized RENTAL table RENTAL transId, date, customerId, name, address, city, state, zip, videoId, copy#, title, rentAmount, videoId, copy#, title, rentAmount, videoId, copy#, title, rentAmount A customer can rent up to 3 videos on a single transaction. Business Rule: A customer can not rent more than one copy of a given movie in a single transaction. This is an unnormalized relation since there is a repeating group, i.e., videoId, copy#, title, rentAmount. To put it into 1NF, remove the repeating group to its own table. Chapter 10-10

Video Rental Example 1NF RENTAL table RENTAL transId, date, cusId, name, address, city, state, zip RENTAL_ITEM transId, videoId, copy#, title, rentAmount

COPY videoId, #copies

transId date cusId name addr city state zip 101 10/15/04 17 Adams 123 Main Smallville AZ 82345 transId videoId 101 15 101 12

copy# title 1 Matrix 5 Hopscotch

rent 1.50 1.00 Chapter 10-11

Exercise Give an example of a relation that is not in 1NF using the book publishing attributes such as isbn, author, title, publisher, date.

Put your table in 1NF.

Chapter 10-12

Notes

Chapter 10-13

10.3.3 Second Normal Form (2NF) Uses the concepts of primary key and functional dependency Before moving on to 2NF, what problems do you foresee with the 1NF RENTAL_ITEM table? RENTAL_ITEM transId videoId 101 15 101 12

copy# title 1 Matrix 5 Hopscotch

rent 1.50 1.00 Chapter 10-14

Problems with 1NF Consider: RENTAL_ITEM transId videoId 101 15 101 12

copy# title 1 Matrix 5 Hopscotch

rent 1.50 1.00

Every time someone rents video 1, we have to enter the title. The problem is that title depends only on only part of the key (videoId). The movie title does not change with every transaction. Chapter 10-15

Keys and Attributes Participating in Keys (1/2) A superkey of a relation schema R = {A1, A2, ...., An} is a set of attributes S subset-of R with the property that no two tuples t1 and t2 in any legal relation state r of R will have t1[S] = t2[S] A key K is a superkey with the additional property that removal of any attribute from K will cause K not to be a superkey any more. Chapter 10-16

You're telling me about superkeys? SUPERKEYS?! Ralph, there's nothing new here. It just means that no two rows can be the same for the set of superkey attributes. Call me back when you have something new.

Chapter 10-17

SuperKey A superkey of a relation schema R = {A1, A2, ...., An} is a set of attributes S subset-of R with the property that no two tuples t1 and t2 in any legal relation state r of R will have t1[S] = t2[S] Identify some of the superkeys in the following table: RENTAL_ITEM transId videoId 101 15 101 12

copy# title 1 Matrix 5 Hopscotch

rent 1.50 1.00 Chapter 10-18

Keys and Attributes Participating in Keys (2/2) If a relation schema has more than one key, each is called a candidate key. One of the candidate keys is arbitrarily designated to be the primary key, and the others are called secondary keys. A Prime attribute must be a member of some candidate key A Nonprime attribute is not a prime attribute— that is, it is not a member of any candidate key. Chapter 10-19

Key Given the following table, identify the following: Candidate key Primary key Secondary key Prime attributes Non-prime attributes RENTAL_ITEM transId videoId 101 15 101 12

copy# title 1 Matrix 5 Hopscotch

rent 1.50 1.00 Chapter 10-20

Functional Dependency  Functional dependency denoted A -> B ("A functionally determines B") between two sets of attributes A and B means that the values of the A component uniquely determine the values of the B component.

Chapter 10-21

Functional Dependency  Functional dependency denoted A -> B ("A functionally determines B") between two sets of attributes A and B means that the values of the A component uniquely determine the values of the B component. ...each unique value of the A component determines a unique value of the B component.

Chapter 10-22

Functional Dependency

Functional dependency  Describes a relationship between attributes in a relation.  For example, if A and B are attributes of relation R, B is functionally dependent on A, denoted A -> B, if each value of A is associated with exactly one value of B.

Chapter 10-23

Functional Dependency For example, if A and B are attributes of relation R, "A functionally determines B", or "B is functionally dependent on A", denoted A -> B, if each value of A is associated with exactly one value of B. RENTAL_ITEM transId videoId copy# 101 151 1 101 127 5

title Matrix Hopscotch

rent 1.50 1.00

Identify a functional dependency in RENTAL_ITEM Chapter 10-24

Functional Dependency RENTAL_ITEM transId videoId 101 151 101 127

copy# title 1 Matrix 5 Hopscotch

rent 1.50 1.00

Title ("B") is functionally dependent on videoId ("A"). For each videoId=151 there is only one title value ("Matrix"). If you know the videoId, you always know the title. We find only one title=Matrix whenever videoId=151 videoId functionally determines title. videoId

1

1

title Chapter 10-25

Functional Dependency RENTAL_ITEM transId videoId 101 151 101 127 102 163

copy# 1 5 1

title Matrix Hopscotch Matrix

rent 1.50 1.00 1.50

Title is functionally dependent on videoId. For each videoId=151 there is only one title value ("Matrix"). If you know the videoId, you always know the title. We find only one title=Matrix whenever videoId=151 We find only one title=Matrix whenever videoId=163 videoId functionally determines title. videoId

n

1

title Chapter 10-26

Not Functionally Dependent RENTAL_ITEM transId videoId 101 151 101 151 102 163

copy# 1 5 1

title Matrix Hopscotch Matrix

rent 1.50 1.00 1.50

Here, title ("B") is NOT functionally dependent on videoId ("A"). For each videoId=151 there is more than one title value. We find more than one title whenever videoId=151 videoId does not functionally determine title. videoId

n

n

title Chapter 10-27

Functional Dependency RENTAL_ITEM transId videoId 101 151 101 151 102 163

copy# 1 5 1

title Matrix Hopscotch Matrix

rent 1.50 1.00 1.50

videoId ("A") does not functionally determine title ("B"). videoId does not functionally determine rent. videoId does not functionally determine copy#. n

1 videoId n

n

title Chapter 10-28

Functional Dependency (FD) The Rental_ITEM table is in 1NF, but not in 2NF RENTAL_ITEM is FD on transId videoId

copy#

title

rent

is FD on is FD on 101 101 102

151 127 163

1 5 1

Matrix Hopscotch Matrix

1.50 1.00 1.50 Chapter 10-29

Second Normal Form (2NF) A relation schema R is in second normal form (2NF) if every non-prime attribute A in R is fully functionally dependent on the primary key.  From 1NF to 2NF: Split the table. Pull out the columns that depend on part of the key. Chapter 10-30

2NF VIDEO

RENTAL_ITEM is FD on transId videoId 101 101 102

151 127 163

copy# 1 5 1

is FD on is FD on videoId title 151 127 163

rent

Matrix 1.50 Hopscotch 1.00 Matrix 1.50

RENTAL_ITEM and VIDEO are now in 2NF. Chapter 10-31

Second Normal Form Definitions: Full functional dependency - a FD Y -> Z where removal of any attribute from Y means the FD does not hold any more Examples: {SSN, PNUMBER} -> HOURS is a full FD since neither SSN -> HOURS nor PNUMBER -> HOURS hold {SSN, PNUMBER} -> ENAME is not a full FD (it is called a partial dependency ) since SSN -> ENAME also holds Chapter 10-32

Figure 10.10 Normalizing into 2NF and 3NF

Chapter 10-33

Fig10.10 Normalizing into 2NF and 3NF

Chapter 10-34

Figure 10.11 Normalization into 2NF and 3NF

Chapter 10-35

Fig 10.11 Normalization into 2NF and 3NF

Chapter 10-36

Functional Dependencies

RENTAL transId, date, cusId, name, 101 10/15/04 17 102 10/15/04 18

address,

city,

state,

zip

Adams 123 Main Smallville AZ 82345 Jones 33 Sneath Teapot AZ 82348

Identify the functional dependencies in the RENTAL table Chapter 10-37

Functional Dependencies RENTAL FD on transId transId, date, cusId, name, address, city, state, zip

FD on cusId What we have here is a "transitive functional dependency". Chapter 10-38

Notes

Chapter 10-39

10.3.4 Third Normal Form (3NF) Definition: Transitive functional dependency - a FD X -> Z that can be derived from two FDs X -> Y and Y -> Z Examples:

- SSN -> DMGRSSN is a transitive FD since SSN -> DNUMBER and DNUMBER -> DMGRSSN hold - SSN -> ENAME is non-transitive since there is no set of attributes X where SSN -> X and X -> ENAME Chapter 10-40

Third Normal Form (2/2) A relation schema R is in third normal form (3NF) if it is in 2NF and no non-prime attribute A in R is transitively dependent on the primary key R can be decomposed into 3NF relations via the process of 3NF normalization NOTE: In X -> Y and Y -> Z, with X as the primary key, we consider this a problem only if Y is not a candidate key. When Y is a candidate key, there is no problem with the transitive dependency . E.g., Consider EMP (SSN, Emp#, Salary ). Here, SSN -> Emp# -> Salary and Emp# is a candidate key. Chapter 10-41

3NF RENTAL

CUSTOMER

FD on transId transId, date, cusId

cusId, name, address, city, state, zip

FD on cusID

Chapter 10-42

Notes

Chapter 10-43

Notes

Chapter 10-44

10.3.1 Normalization of Relations

 First Normal Form (1NF) is part of relational table definition  2NF, 3NF, BCNF based on keys and functional dependencies (FDs) of a relation schema  4NF based on keys, multi-valued dependencies(MVDs) 5NF based on keys, join dependencies (JDs) (Chapter 11)  Additional properties may be needed to ensure a good relational design (lossless join, dependency preservation; Chapter 11)

Chapter 10-45

10.4 General Normal Form Definitions (For Multiple Keys)

(1)

The above definitions consider the primary key only The following more general definitions take into account relations with multiple candidate keys A relation schema R is in second normal form (2NF) if every non-prime attribute A in R is fully functionally dependent on every key of R

Chapter 10-46

General Normal Form Definitions (2)

Definition: Superkey of relation schema R - a set of attributes S of R that contains a key of R A relation schema R is in third normal form (3NF) if whenever a FD X -> A holds in R, then either: (a) X is a superkey of R, or (b) A is a prime attribute of R NOTE: Boyce-Codd normal form disallows condition (b) above Chapter 10-47

5 BCNF (Boyce-Codd Normal Form)

A relation schema R is in Boyce-Codd Normal Form (BCNF) if whenever an FD X -> A holds in R, then X is a superkey of R  Each normal form is strictly stronger than the previous one – Every 2NF relation is in 1NF – Every 3NF relation is in 2NF – Every BCNF relation is in 3NF

 There exist relations that are in 3NF but not in BCNF  The goal is to have each relation in BCNF (or 3NF) Chapter 10-48

Figure 10.12 Boyce-Codd normal form

Note: The above figure is now called Figure 10.12 in Edition 4 Chapter 10-49

Figure 10.13 a relation TEACH that is in 3NF but not in BCNF

Note: The above figure is now called Figure 10.13 in Edition 4 Chapter 10-50

Achieving the BCNF by Decomposition (1)

 Two FDs exist in the relation TEACH: fd1: { student, course} -> instructor fd2: instructor -> course  {student, course} is a candidate key for this relation and that the dependencies shown follow the pattern in Figure 10.12 (b). So this relation is in 3NF but not in BCNF  A relation NOT in BCNF should be decomposed so as to meet this property, while possibly forgoing the preservation of all functional dependencies in the decomposed relations. (See Algorithm 11.3) Chapter 10-51

Achieving the BCNF by Decomposition (2)





 

Three possible decompositions for relation TEACH  {student, instructor} and {student, course}  {course, instructor } and {course, student}  {instructor, course } and {instructor, student} All three decompositions will lose fd1. We have to settle for sacrificing the functional dependency preservation. But we cannot sacrifice the non-additivity property after decomposition. Out of the above three, only the 3rd decomposition will not generate spurious tuples after join.(and hence has the non-additivity property). A test to determine whether a binary decomposition (decomposition into two relations) is nonadditive (lossless) is discussed in section 11.1.4 under Property LJ1. Verify that the third decomposition above meets the property.

Chapter 10-52

Chapter 10

Functional Dependencies and Normalization for Relational Databases

Figure10.8 Normalization into 1NF. (a) A relation schema that is not in 1NF. (b) Example state of relation DEPARTMENT. (c) 1NF version of same relation with redundancy.

Chapter 10-55

Figure10.9 Normalizing nested relations into 1NF. (a) Schema of the EMP_PROJ relation with a “nested relation” attribute PROJS. (b) Example extension of the EMP_PROJ relation showing nested relations within each tuple. (c) Decomposition of EMP_PROJ into relations EMP_PROJ1 and EMP_PROJ2 by propagating the primary key.

Chapter 10-56

Figure10.10 Normalizing into 2NF and 3NF. (a) Normalizing EMP_PROJ into 2NF relations (b) Normalizing EMP_DEPT into 3NF relations.

Chapter 10-57

Figure 10.11 Normalization into 2NF and 3NF. (a) the LOTS relation with its functional dependencies FD1 though FD4. (b) Decomposing into the 2NF relations LOTS1 and LOTS2. (c) Decomposing LOTS1 into the 3NF relations LOTS1A and LOTS1B. (d) Summary of the progressive normalization of LOTS.

Chapter 10-58

p 137 Chapter 10-59

Out

Chapter 10-60

Figure 10.9 Normalization nested relations into 1NF

p 317 Chapter 10-61

Exercise 10.32 Car_Sale(Car#, Salesman#, Date_sold, com% , Discount_amt) with functional dependencies: Date_sold -> Discount_amt (The date sold uniquely determines the amount of the discount). Salesman# -> com% (The salesman number uniquely determines the amount of the commission) p 330 Chapter 10-62

Second Normal Form (2/2) A relation schema R is in second normal form (2NF) if every non-prime attribute A in R is fully functionally dependent on the primary key R can be decomposed into 2NF relations via the process of 2NF normalization Chapter 10-63

p. 139 Chapter 10-64