CS340 · Chapter 9 · Annotated SlidesFunctional Dependencies and Normalization
Original
Overview

Functional Dependencies and Normalization

Informal design guidelines (clear semantics, no anomalies, few NULLs, no spurious tuples), functional dependencies, keys and prime attributes, 1NF, 2NF, 3NF and BCNF with their general definitions, lossless decomposition, inference rules and attribute closure, and a full worked example.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 94 slides
  1. 1 Functional Dependencies and Normalization
  2. 2 Slide 2
  3. 3 LEARNING GOALS
  4. 4 CHAPTER OUTLINE
  5. 5 INTRODUCTION
  6. 6 INTRODUCTION
  7. 7 INTRODUCTION
  8. 8 INFORMAL DESIGN GUIDELINES FOR RELATIONAL DATABASES
  9. 9 GUIDELINE FOR REDUNDANT INFORMATION IN TUPLES AND UPDATE ANOMALIES
  10. 10 A SIMPLIFIED COMPANY RELATIONAL DATABASE SCHEMA
  11. 11 A SIMPLIFIED COMPANY RELATIONAL DATABASE INSTANCE
  12. 12 REDUNDANT INFORMATION IN TUPLES AND UPDATE ANOMALIES
  13. 13 EXAMPLE: TWO RELATION SCHEMAS SUFFERING FROM UPDATE ANOMALIES
  14. 14 SAMPLE STATES FOR EMP_DEP T AND
  15. 15 EXAMPLE OF AN UPDATE ANOMALY
  16. 16 EXAMPLE OF AN INSERT ANOMALY
  17. 17 EXAMPLE OF A DELETE ANOMALY
  18. 18 GUIDELINE FOR REDUNDANT INFORMATION IN TUPLES AND UPDATE ANOMALIES
  19. 19 1.3 NULL VALUES IN TUPLES
  20. 20 1.3 NULL VALUES IN TUPLES
  21. 21 1.4 GENERATION OF SPURIOUS TUPLES AVOID AT ANY COST
  22. 22 JOINS?
  23. 23 SUMMARY OF INFORMAL DESIGN GUIDELINES
  24. 24 FUNCTIONAL DEPENDENCIES
  25. 25 FUNCTIONAL DEPENDENCIES
  26. 26 DEFINING FUNCTIONAL DEPENDENCIES
  27. 27 FUNCTIONAL DEPENDENCIES
  28. 28 EXAMPLES OF FD CONSTRAINTS
  29. 29 EXAMPLE BEFORE FORMAL DEFINITIONS
  30. 30 QUICK EXAMPLE
  31. 31 DEFINING FUNCTIONAL DEPENDENCIES
  32. 32 DEFINING FUNCTIONAL DEPENDENCIES
  33. 33 DEFINING FUNCTIONAL DEPENDENCIES
  34. 34 SOME FD PROPERTIES
  35. 35 DEFINING FDS FROM INSTANCES
  36. 36 ACTIVITY: RULING OUT FDS
  37. 37 ACTIVITY 2: WHAT FDS MAY EXIST?
  38. 38 CX
  39. 39 NORMAL FORMS BASED ON PRIMARY KEYS
  40. 40 3.1 NORMALIZATION OF RELATIONS
  41. 41 3.2 PRACTICAL USE OF NORMAL FORMS
  42. 42 3.3DEFINITIONS OF KEYS AND ATTRIBUTES PARTICIPATING IN KEYS (1)
  43. 43 Slide 43
  44. 44 DEFINITIONS OF KEYS AND ATTRIBUTES PARTICIPATING IN KEYS (2)
  45. 45 TYPES OF FUNCTIONAL DEPENDENCIES
  46. 46 TYPES OF FUNCTIONAL DEPENDENCIES
  47. 47 3.4 FIRST NORMAL FORM
  48. 48 EXAMPLE: NORMALIZATIO N INTO 1NF a
  49. 49 Slide 49
  50. 50 NORMALIZATION INTO 1NF
  51. 51 EXAMPLE: NORMALIZING NESTED RELATIONS INTO 1NF
  52. 52 NORMALIZATION INTO 1NF
  53. 53 3.5 SECOND NORMAL FORM (1)
  54. 54 SECOND NORMAL FORM (2)
  55. 55 EXAMPLE: NORMALIZING INTO 2NF
  56. 56 3.6 THIRD NORMAL FORM (1)
  57. 57 THIRD NORMAL FORM (2)
  58. 58 EXAMPLE: NORMALIZING INTO 3NF
  59. 59 NORMAL FORMS DEFINED INFORMALLY
  60. 60 4 GENERAL NORMAL FORM DEFINITIONS (FOR MULTIPLE KEYS) (1)
  61. 61 RELATIOAN SCHEMA LOTS
  62. 62 GENERAL DEFINITIONS OF SECOND AND THIRD NORMAL FORMS
  63. 63 4.1 GENERAL DEFINITION OF 2NF (FOR MULTIPLE CANDIDATE KEYS)
  64. 64 NORMALIZATION INTO 2NF
  65. 65 4.2 GENERAL DEFINITION OF THIRD NORMAL FORM
  66. 66 4.3 INTERPRETING THE GENERAL DEFINITION OF THIRD NORMAL FORM
  67. 67 4.3 INTERPRETING THE GENERAL DEFINITION OF THIRD NORMAL FORM (2)
  68. 68 NORMALIZATIO N INTO 3NF
  69. 69 BOYCE-CODD NORMAL FORM (BCNF)
  70. 70 5. BCNF (BOYCE-CODD NORMAL FORM)
  71. 71 BOYCE-CODD NORMAL FORM (BCNF)
  72. 72 EXAMPLE: BOYCE-CODD NORMAL FORM
  73. 73 BOYCE-CODD NORMAL FORM (BCNF)
  74. 74 BOYCE-CODD NORMAL FORM (BCNF)
  75. 75 EXAMPLE: A RELATION TEACH THAT IS IN 3NF BUT NOT IN BCNF
  76. 76 ACHIEVING THE BCNF BY DECOMPOSITION (1)
  77. 77 ACHIEVING THE BCNF BY DECOMPOSITION (1)
  78. 78 NON-ADDITIVE JOIN TEST
  79. 79 GENERAL METHOD FOR BCNF DECOMPOSITION
  80. 80 BCNF OF TEACH RELATION
  81. 81 DETERMINING FD S CLOSURE
  82. 82 FUNCTIONAL DEPENDENCY INFERENCE RULES
  83. 83 PROOFS
  84. 84 CLOSURE OF ATTRIBUTES
  85. 85 CLOSURE ALGORITHM
  86. 86 FINDING THE KEY
  87. 87
  88. 88
  89. 89 A FULL EXAMPLE
  90. 90 A FULL EXAMPLE (2)
  91. 91 A FULL EXAMPLE (3)
  92. 92 A FULL EXAMPLE (4): KEYS
  93. 93 A FULL EXAMPLE (5): 1NF AND 2NF
  94. 94 A FULL EXAMPLE (5): 3NF AND BCNF
Slide 1 / 94

Functional Dependencies and Normalization

Slide 1: Functional Dependencies and Normalization
Slide 2 / 94

Slide 2

Slide 2: Slide 2

Notes

  1. 1NF: atomic values. 2NF: no PARTIAL dependency on the key. 3NF: no TRANSITIVE dependency. BCNF: every determinant is a superkey.

Slide 3 / 94

LEARNING GOALS

Slide 3: LEARNING GOALS
Slide 4 / 94

CHAPTER OUTLINE

Slide 4: CHAPTER OUTLINE
Slide 5 / 94

INTRODUCTION

Slide 5: INTRODUCTION
Slide 6 / 94

INTRODUCTION

Slide 6: INTRODUCTION
Slide 7 / 94

INTRODUCTION

Slide 7: INTRODUCTION
Slide 8 / 94

INFORMAL DESIGN GUIDELINES FOR RELATIONAL DATABASES

Slide 8: INFORMAL DESIGN GUIDELINES FOR RELATIONAL DATABASES
Slide 9 / 94

GUIDELINE FOR REDUNDANT INFORMATION IN TUPLES AND UPDATE ANOMALIES

Slide 9: GUIDELINE FOR REDUNDANT INFORMATION IN TUPLES AND UPDATE ANOMALIES
Slide 10 / 94

A SIMPLIFIED COMPANY RELATIONAL DATABASE SCHEMA

Slide 10: A SIMPLIFIED COMPANY RELATIONAL DATABASE SCHEMA
Slide 11 / 94

A SIMPLIFIED COMPANY RELATIONAL DATABASE INSTANCE

Slide 11: A SIMPLIFIED COMPANY RELATIONAL DATABASE INSTANCE
Slide 12 / 94

REDUNDANT INFORMATION IN TUPLES AND UPDATE ANOMALIES

Slide 12: REDUNDANT INFORMATION IN TUPLES AND UPDATE ANOMALIES
Slide 13 / 94

EXAMPLE: TWO RELATION SCHEMAS SUFFERING FROM UPDATE ANOMALIES

Slide 13: EXAMPLE: TWO RELATION SCHEMAS SUFFERING FROM UPDATE ANOMALIES
Slide 14 / 94

SAMPLE STATES FOR EMP_DEP T AND

Slide 14: SAMPLE STATES FOR EMP_DEP T AND
Slide 15 / 94

EXAMPLE OF AN UPDATE ANOMALY

Slide 15: EXAMPLE OF AN UPDATE ANOMALY

Notes

  1. Update anomaly: changing one fact means changing many rows.

Slide 16 / 94

EXAMPLE OF AN INSERT ANOMALY

Slide 16: EXAMPLE OF AN INSERT ANOMALY

Notes

  1. Insert anomaly: can’t add a fact without unrelated data (a new project with no employees).

Exam angle

PredictionQ1

You can’t record a new department until it has an employee. This is a(n):

Slide 17 / 94

EXAMPLE OF A DELETE ANOMALY

Slide 17: EXAMPLE OF A DELETE ANOMALY

Notes

  1. Delete anomaly: deleting one fact loses another (last employee of a department deletes the department).

Slide 18 / 94

GUIDELINE FOR REDUNDANT INFORMATION IN TUPLES AND UPDATE ANOMALIES

Slide 18: GUIDELINE FOR REDUNDANT INFORMATION IN TUPLES AND UPDATE ANOMALIES
Slide 19 / 94

1.3 NULL VALUES IN TUPLES

Slide 19: 1.3 NULL VALUES IN TUPLES
Slide 20 / 94

1.3 NULL VALUES IN TUPLES

Slide 20: 1.3 NULL VALUES IN TUPLES
Slide 21 / 94

1.4 GENERATION OF SPURIOUS TUPLES AVOID AT ANY COST

Slide 21: 1.4 GENERATION OF SPURIOUS TUPLES AVOID AT ANY COST

Notes

  1. Spurious tuples: wrong rows produced by joining a bad decomposition; join on PK–FK pairs to avoid them.

Slide 22 / 94

JOINS?

Slide 22: JOINS?
Slide 23 / 94

SUMMARY OF INFORMAL DESIGN GUIDELINES

Slide 23: SUMMARY OF INFORMAL DESIGN GUIDELINES
Slide 24 / 94

FUNCTIONAL DEPENDENCIES

Slide 24: FUNCTIONAL DEPENDENCIES

Exam angle

PredictionQ1

Ssn → Ename means:

Slide 25 / 94

FUNCTIONAL DEPENDENCIES

Slide 25: FUNCTIONAL DEPENDENCIES
Slide 26 / 94

DEFINING FUNCTIONAL DEPENDENCIES

Slide 26: DEFINING FUNCTIONAL DEPENDENCIES
Slide 27 / 94

FUNCTIONAL DEPENDENCIES

Slide 27: FUNCTIONAL DEPENDENCIES
Slide 28 / 94

EXAMPLES OF FD CONSTRAINTS

Slide 28: EXAMPLES OF FD CONSTRAINTS
Slide 29 / 94

EXAMPLE BEFORE FORMAL DEFINITIONS

Slide 29: EXAMPLE BEFORE FORMAL DEFINITIONS
Slide 30 / 94

QUICK EXAMPLE

Slide 30: QUICK EXAMPLE
Slide 31 / 94

DEFINING FUNCTIONAL DEPENDENCIES

Slide 31: DEFINING FUNCTIONAL DEPENDENCIES
Slide 32 / 94

DEFINING FUNCTIONAL DEPENDENCIES

Slide 32: DEFINING FUNCTIONAL DEPENDENCIES
Slide 33 / 94

DEFINING FUNCTIONAL DEPENDENCIES

Slide 33: DEFINING FUNCTIONAL DEPENDENCIES
Slide 34 / 94

SOME FD PROPERTIES

Slide 34: SOME FD PROPERTIES
Slide 35 / 94

DEFINING FDS FROM INSTANCES

Slide 35: DEFINING FDS FROM INSTANCES

Notes

  1. An instance can DISPROVE an FD (two rows agree on X but differ on Y) but can never prove one holds.

Exam angle

PredictionQ1

A sample table can prove that an FD holds for all possible data.

Slide 36 / 94

ACTIVITY: RULING OUT FDS

Slide 36: ACTIVITY: RULING OUT FDS
Slide 37 / 94

ACTIVITY 2: WHAT FDS MAY EXIST?

Slide 37: ACTIVITY 2: WHAT FDS MAY EXIST?
Slide 38 / 94

CX

Slide 38: CX
Slide 39 / 94

NORMAL FORMS BASED ON PRIMARY KEYS

Slide 39: NORMAL FORMS BASED ON PRIMARY KEYS
Slide 40 / 94

3.1 NORMALIZATION OF RELATIONS

Slide 40: 3.1 NORMALIZATION OF RELATIONS
Slide 41 / 94

3.2 PRACTICAL USE OF NORMAL FORMS

Slide 41: 3.2 PRACTICAL USE OF NORMAL FORMS
Slide 42 / 94

3.3DEFINITIONS OF KEYS AND ATTRIBUTES PARTICIPATING IN KEYS (1)

Slide 42: 3.3DEFINITIONS OF KEYS AND ATTRIBUTES PARTICIPATING IN KEYS (1)

Notes

  1. Prime attribute: member of some candidate key. Nonprime: not in any candidate key.

Slide 43 / 94

Slide 43

Slide 43: Slide 43
Slide 44 / 94

DEFINITIONS OF KEYS AND ATTRIBUTES PARTICIPATING IN KEYS (2)

Slide 44: DEFINITIONS OF KEYS AND ATTRIBUTES PARTICIPATING IN KEYS (2)
Slide 45 / 94

TYPES OF FUNCTIONAL DEPENDENCIES

Slide 45: TYPES OF FUNCTIONAL DEPENDENCIES
Slide 46 / 94

TYPES OF FUNCTIONAL DEPENDENCIES

Slide 46: TYPES OF FUNCTIONAL DEPENDENCIES
Slide 47 / 94

3.4 FIRST NORMAL FORM

Slide 47: 3.4 FIRST NORMAL FORM

Notes

  1. 1NF: every attribute is atomic (no multivalued or composite values, no nested relations).

Exam angle

Slide 48 / 94

EXAMPLE: NORMALIZATIO N INTO 1NF a

Slide 48: EXAMPLE: NORMALIZATIO N INTO 1NF a
Slide 49 / 94

Slide 49

Slide 49: Slide 49
Slide 50 / 94

NORMALIZATION INTO 1NF

Slide 50: NORMALIZATION INTO 1NF
Slide 51 / 94

EXAMPLE: NORMALIZING NESTED RELATIONS INTO 1NF

Slide 51: EXAMPLE: NORMALIZING NESTED RELATIONS INTO 1NF
Slide 52 / 94

NORMALIZATION INTO 1NF

Slide 52: NORMALIZATION INTO 1NF
Slide 53 / 94

3.5 SECOND NORMAL FORM (1)

Slide 53: 3.5 SECOND NORMAL FORM (1)

Notes

  1. 2NF: 1NF + every nonprime attribute is FULLY dependent on the primary key (no partial dependency on part of a composite key).

  2. Trap A relation with a single-attribute primary key is automatically in 2NF.

Exam angle

PredictionQ1

2NF removes:

Slide 54 / 94

SECOND NORMAL FORM (2)

Slide 54: SECOND NORMAL FORM (2)
Slide 55 / 94

EXAMPLE: NORMALIZING INTO 2NF

Slide 55: EXAMPLE: NORMALIZING INTO 2NF
Slide 56 / 94

3.6 THIRD NORMAL FORM (1)

Slide 56: 3.6 THIRD NORMAL FORM (1)

Notes

  1. 3NF: 2NF + no nonprime attribute transitively dependent on the key (key → X → Y with X not a key).

Exam angle

Past exam · Midterm exam

Related question: Q17: normalize LIBRARY to 3NF

PredictionQ1

EMP_DEPT(Ssn, Ename, Dnumber, Dname) with Ssn → Ename, Dnumber and Dnumber → Dname. Normalize to 3NF.

Compare with the model answer

Dname depends transitively on Ssn through Dnumber. Split into EMP(Ssn, Ename, Dnumber) with Dnumber as an FK, and DEPT(Dnumber, Dname).

Slide 57 / 94

THIRD NORMAL FORM (2)

Slide 57: THIRD NORMAL FORM (2)
Slide 58 / 94

EXAMPLE: NORMALIZING INTO 3NF

Slide 58: EXAMPLE: NORMALIZING INTO 3NF
Slide 59 / 94

NORMAL FORMS DEFINED INFORMALLY

Slide 59: NORMAL FORMS DEFINED INFORMALLY
Slide 60 / 94

4 GENERAL NORMAL FORM DEFINITIONS (FOR MULTIPLE KEYS) (1)

Slide 60: 4 GENERAL NORMAL FORM DEFINITIONS (FOR MULTIPLE KEYS) (1)
Slide 61 / 94

RELATIOAN SCHEMA LOTS

Slide 61: RELATIOAN SCHEMA LOTS
Slide 62 / 94

GENERAL DEFINITIONS OF SECOND AND THIRD NORMAL FORMS

Slide 62: GENERAL DEFINITIONS OF SECOND AND THIRD NORMAL FORMS
Slide 63 / 94

4.1 GENERAL DEFINITION OF 2NF (FOR MULTIPLE CANDIDATE KEYS)

Slide 63: 4.1 GENERAL DEFINITION OF 2NF (FOR MULTIPLE CANDIDATE KEYS)
Slide 64 / 94

NORMALIZATION INTO 2NF

Slide 64: NORMALIZATION INTO 2NF
Slide 65 / 94

4.2 GENERAL DEFINITION OF THIRD NORMAL FORM

Slide 65: 4.2 GENERAL DEFINITION OF THIRD NORMAL FORM
Slide 66 / 94

4.3 INTERPRETING THE GENERAL DEFINITION OF THIRD NORMAL FORM

Slide 66: 4.3 INTERPRETING THE GENERAL DEFINITION OF THIRD NORMAL FORM
Slide 67 / 94

4.3 INTERPRETING THE GENERAL DEFINITION OF THIRD NORMAL FORM (2)

Slide 67: 4.3 INTERPRETING THE GENERAL DEFINITION OF THIRD NORMAL FORM (2)
Slide 68 / 94

NORMALIZATIO N INTO 3NF

Slide 68: NORMALIZATIO N INTO 3NF
Slide 69 / 94

BOYCE-CODD NORMAL FORM (BCNF)

Slide 69: BOYCE-CODD NORMAL FORM (BCNF)

Notes

  1. BCNF: for every nontrivial FD X → A, X is a superkey. Stricter than 3NF.

  2. Tip 1NF: atomic values. 2NF: no PARTIAL dependency on the key. 3NF: no TRANSITIVE dependency. BCNF: every determinant is a superkey.

Exam angle

PredictionQ1

A relation is in BCNF if for every nontrivial FD X → A:

Slide 70 / 94

5. BCNF (BOYCE-CODD NORMAL FORM)

Slide 70: 5. BCNF (BOYCE-CODD NORMAL FORM)
Slide 71 / 94

BOYCE-CODD NORMAL FORM (BCNF)

Slide 71: BOYCE-CODD NORMAL FORM (BCNF)
Slide 72 / 94

EXAMPLE: BOYCE-CODD NORMAL FORM

Slide 72: EXAMPLE: BOYCE-CODD NORMAL FORM
Slide 73 / 94

BOYCE-CODD NORMAL FORM (BCNF)

Slide 73: BOYCE-CODD NORMAL FORM (BCNF)
Slide 74 / 94

BOYCE-CODD NORMAL FORM (BCNF)

Slide 74: BOYCE-CODD NORMAL FORM (BCNF)
Slide 75 / 94

EXAMPLE: A RELATION TEACH THAT IS IN 3NF BUT NOT IN BCNF

Slide 75: EXAMPLE: A RELATION TEACH THAT IS IN 3NF BUT NOT IN BCNF
Slide 76 / 94

ACHIEVING THE BCNF BY DECOMPOSITION (1)

Slide 76: ACHIEVING THE BCNF BY DECOMPOSITION (1)
Slide 77 / 94

ACHIEVING THE BCNF BY DECOMPOSITION (1)

Slide 77: ACHIEVING THE BCNF BY DECOMPOSITION (1)
Slide 78 / 94

NON-ADDITIVE JOIN TEST

Slide 78: NON-ADDITIVE JOIN TEST
Slide 79 / 94

GENERAL METHOD FOR BCNF DECOMPOSITION

Slide 79: GENERAL METHOD FOR BCNF DECOMPOSITION
Slide 80 / 94

BCNF OF TEACH RELATION

Slide 80: BCNF OF TEACH RELATION
Slide 81 / 94

DETERMINING FD S CLOSURE

Slide 81: DETERMINING FD S CLOSURE
Slide 82 / 94

FUNCTIONAL DEPENDENCY INFERENCE RULES

Slide 82: FUNCTIONAL DEPENDENCY INFERENCE RULES
Slide 83 / 94

PROOFS

Slide 83: PROOFS
Slide 84 / 94

CLOSURE OF ATTRIBUTES

Slide 84: CLOSURE OF ATTRIBUTES

Exam angle

PredictionQ1

R(A, B, C, D) with A → B, B → C, C → D. A candidate key is:

Slide 85 / 94

CLOSURE ALGORITHM

Slide 85: CLOSURE ALGORITHM
Slide 86 / 94

FINDING THE KEY

Slide 86: FINDING THE KEY

Notes

  1. Find a key: start with attributes on no right-hand side (they must be in every key), compute the closure, add attributes until it covers R.

Slide 87 / 94

Slide 87: 
Slide 88 / 94

Slide 88: 
Slide 89 / 94

A FULL EXAMPLE

Slide 89: A FULL EXAMPLE
Slide 90 / 94

A FULL EXAMPLE (2)

Slide 90: A FULL EXAMPLE (2)
Slide 91 / 94

A FULL EXAMPLE (3)

Slide 91: A FULL EXAMPLE (3)
Slide 92 / 94

A FULL EXAMPLE (4): KEYS

Slide 92: A FULL EXAMPLE (4): KEYS
Slide 93 / 94

A FULL EXAMPLE (5): 1NF AND 2NF

Slide 93: A FULL EXAMPLE (5): 1NF AND 2NF
Slide 94 / 94

A FULL EXAMPLE (5): 3NF AND BCNF

Slide 94: A FULL EXAMPLE (5): 3NF AND BCNF