DBMS 8 1
DBMS 8 1
DBMS 8 1
OF DATABASE
SYSTEMS
LESSON 8: Functional Dependencies and Normalization
for Relational Databases
Nguyễn Thị Hậu
University of Engineering and Technology,
Vietnam National University in Hanoi (UET-VNU)
nguyenhau@vnu.edu.vn
Chapter Outline
1. Informal Design Guidelines for Relational Databases
2. Functional Dependencies (FDs)
3. Normal Forms Based on Primary Keys
4. General Normal Form Definitions (For Multiple Keys)
5. BCNF (Boyce-Codd Normal Form)
Chapter 10-7
Redundant Information in Tuples and Update Anomalies
Dư thừa
Figure Two relation schemas suffering from update anomalies
• X -> Y holds if whenever two tuples have the same value for X, they must have
the same value for Y
• For any two tuples t1 and t2 in any relation instance r(R): If t1[X]=t2[X], then
t1[Y]=t2[Y]
• X -> Y in R specifies a constraint on all relation instances r(R)
• Written as X -> Y; can be displayed graphically on a relation schema as in Figures.
( denoted by the arrow: ).
• FDs are derived from the real-world constraints on the attributes
• Given a set of FDs F, we can infer additional FDs that hold whenever
the FDs in F hold
Armstrong's inference rules:
IR1. (Reflexive) If Y subset-of X, then X -> Y
IR2. (Augmentation) If X -> Y, then XZ -> YZ
(Notation: XZ stands for X U Z)
IR3. (Transitive) If X -> Y and Y -> Z, then X -> Z
• IR1, IR2, IR3 form a sound and complete set of inference rules
• The last three inference rules, as well as any other inference rules,
can be deduced from IR1, IR2, and IR3 (completeness property)
• Closure of a set F of FDs is the set F+ of all FDs that can be inferred
from F
F+ = F { f / F |= f}
• F = {X Y , Y Z }
F+ = {X Y , Y Z , X Z , X YZ}
A+ = {A, D,E }
F |= AB E ?
AB+ = {A, B, C, D, E }
B+ = {B} F |= DC ?
D+ = {D, E} F |= AD CDE ?
AD+ = {A, D, E} F |=AB CDE
Example
Cho F ={ A B, C DE, AC F}
Xác định các bao đóng sau:
A+ = {A, B }
F |= A E ?
C+ = {C, D, E }
AC+ = {A, B, C, D, E, F} F |= ACBDF ?
Nhập môn Cơ sở Dữ liệu
- Initializing: X+ ={AB}
- With (a): X+ ={ABC}
- With (b): X+ ={ABCD}
- With (c): X+ ={ABCDE}
- With (d): X+ ={ABCDE}
Example of computing the closure of a set
Ex. 3: F ={ AG I, BE I,E G, AB E, GI H}
Proving that F |= AB GH using closure computing method
AB E
AB GH
2.3 Equivalence of Sets of FDs
Cần chứng minh các phụ thuộc hàm của E suy dẫn được từ F và ngược lại
{A C} |= {A AC}
|= {A D}
{AC D} |= {A CD}
kết hợp với {A C}
Vậy F |= {A CD}
{E AD} |= {E A}
|= {E AH} Vậy F |= {E AH}
{E H}
Tức là F phủ E
F = {A C, AC D, EAD, E H }
E = { A CD, E AH }
Kiểm tra xem E tương đương F ?
Cách 1: Dùng các quy tắc suy diễn
F = {A C, AC D, EAD, E H }
E = { A CD, E AH }
Kiểm tra xem E tương đương F ?
{E}+E = {ACDEH}
vậy F phủ E
vậy E phủ F