Chương 4: LÝ THUYẾT THIẾT KẾ CƠ SỞ DỮ LIỆU QH
I. PHỤ THUỘC HÀM
– Định nghĩa phụ thuộc hàm
– Hệ tiên đề Armstrong
– Bao đóng của tập PTH
– Bao đóng của tập thuộc tính
– Siêu khóa và khóa
– Phủ tối thiểu
II. PHÉP TÁCH LƯỢC ĐỒ QUAN HỆ
– Định nghĩa phép tách
– Phép tách không mất mát thông tin
III. CHUẨN HÓA LƯỢC ĐỒ QUAN HỆ
– Khái niệm chuẩn hóa
– Các dạng chuẩn (1NF, 2NF, 3NF)
– Phép tách lược đồ thành các lược đồ 3NFI. PHỤ THUỘC HÀM
1.1. Đặt vấn đề
z MASV→HOTEN, MAKHOA, TENKHOA
z MAMON→TENMON, SOTC
z MAKHOA→TENKHOA
z MASV, MAMON→ DIEMI. PHỤ THUỘC HÀM
1.2. Định nghĩa PTH
Cho quan hệ r(U) với U = {A1, A2,
. . . , An} và các tập thuộc tính X, Y ⊆ U.
Phụ thuộc hàm là một phát biểu dạng X→Y (đọc là X xác định Y hay Y phụ
thuộc hàm vào X), nếu với mọi t1, t2 ∈r mà t1[X]= t2[X] thì t1[Y]= t2[Y]. Khi đóta
nói quan hệ r thoả phụ thuộc hàm X → Y.
1.3. Hệ tiên đề Armstrong
Cho lược đồ quan hệ R(U) với U={A1, . . . , An}.  X, Y, Z ⊆ U. Khi đóta có
các tiên đề sau:
z Tính phản xạ: Nếu Y ⊆ X  thì X → Y;
z Tính tăng trưởng: Nếu X → Y  thì XZ → YZ;
z Tính bắc cầu: Nếu X → Y và Y → Z thì X → Z.I. PHỤ THUỘC HÀM
Các luật được suy ra từ hệ tiên đề Armstrong
z Luật hợp: X → Y và X → Z thì X → YZ;
z Luật tựa bắc cầu: Nếu X → Y và WY → Z thì XW → Z;
z Luật tách: Nếu X → Y  và Z⊆Y  thì X → Z.
1.4. Bao đóng của tập phụ thuộc hàm
Gọi F là tập tất cả các phụ thuộc hàm của lược đồ R(U). X, Y ⊆ U. X→Y
là phụ thuộc hàm.  Ta nói rằng phụ thuộc hàm X → Y được suy dẫn logic từ F
nếu mỗi quan hệ r trên R(U) thoả các phụ thuộc hàm của F thì cũng thoả X→Y.
Tập F+={Tập tất cả các phụ thuộc hàm được suy dẫn logic từ F}
Ö Được gọi là bao đóng của tập phụ thuộc hàm  F.I. PHỤ THUỘC HÀM
Ví dụ 1:
F={A→BC, C→D}
A→D có phải là một suy dẫn logic từ F?
Chứng minh
A→A=> A→ABC       =>  A→ABCD  =>A→D 
A→BC                     C→DI. PHỤ THUỘC HÀM
Ví dụ 2:
Cho lược đồ quan hệ R, quan hệ r xác định trên R và tập phụ thuộc hàm
F = {AB → C, B → D, CD → E, CE → GH, G → A}
Chứng minh rằng nếu quan hệ r trên lược đồ R thoả F thì r cũng thoả
AB→E, AB→G.I. PHỤ THUỘC HÀM
1.5. Bao đóng của tập thuộc tính
Cho tập thuộc tính U, X ⊂ U và tập phụ thuộc hàm F. Bao đóng của X đối
với tập phụ thuộc hàm F  là tập
X+={A∈U| (X→A) ∈F+}
Thu Thuậ ật to t toá án t n tì ìm bao đ m bao đó óng t ng tậ ập thu p thuộ ộc t c tí ính: nh:
Vào: Lược đồ quan hệ R(U), tập PTH F, tập thuộc tính X ⊂ U
Ra: X+ ={A∈U | X →A ∈F+}
Cách tính:
– Đặt X(0)
= X
– X(i)
=    X (i-1)
∪ A  nếu tồn tại (Y→Z) ∈ F+ mà A ∈ Z và Y ⊆ X (i-1)
X (i-1)
nếu ngược lại
Bổ đề: X → Y ⇔ Y ⊆ X+I. PHỤ THUỘC HÀM
Ví dụ:
Cho lược đồ quan hệ R, quan hệ r xác định trên R và tập phụ thuộc hàm
F = {AB → C, B → D, CD → E, CE → GH, G → A}
Tính AB+
?
GiảiI. PHỤ THUỘC HÀM
1.6. Định nghĩa siêu khoá, khoá
Cho lược đồ quan hệ R(U). F là tập phụ thuộc hàm của R.
z K được gọi là siêu khoá của lược đồ R nếu K → U
z K được gọi là khoá của lược đồ R nếu:
– K → U
– Với ∀ K' ⊂ K thì K' → UI. PHỤ THUỘC HÀM
Thu Thuậ ật to t toá án t n tì ìm kho m khoá á: :
Vào: Lược đồ quan hệ R(U), U={A1, A2, ... , An } và tập phụ thuộc hàm F.
Ra : K là một khoá của R.
Cách tính:
– Bước 0: Đặt K
(0)
= U
– Bước i:  K
(i)
=   K
(i-1)
\{Ai
}  nếu K
(i-1)
\{Ai
}→ U
K
(i-1)
nếu ngược lạiI. PHỤ THUỘC HÀM
1.7. Phủ tối thiểu
1.7.1. Tập phụ thuộc hàm tương đương
Cho hai tập phụ thuộc hàm F và G. Ta nói F và G tương đương.
Ký hiệu F∼ G,  nếu F+ = G+. Khi đó ta còn gọi là G ph phủ ủ F (và F ph phủ ủ G).
C Cá ách ki ch kiể ểm tra F tương đương v m tra F tương đương vớ ới G i G
– Lấy mỗi phụ thuộc hàm (X→Y) ∈ F và kiểm tra (X→Y) ∈ G+.
– Lấy mỗi phụ thuộc hàm (X→Y) ∈ G và kiểm tra (X→Y) ∈ F+. I. PHỤ THUỘC HÀM
Ví dụ:
Cho tập phụ thuộc hàm
F={A → BCDE, C →D, EG → H, AE → H}
và G={A → B, A → C, A → E, C →D, EG → H, A → H}
Chứng minh rằng F~G ?I. PHỤ THUỘC HÀM
1.7.2. Tập phụ thuộc hàm tối thiểu
Tập phụ thuộc hàm F được gọi là tối thiểu nếu:
i) Vế phải của mỗi phụ thuộc hàm thuộc F chỉ có một thuộc tính.
(Tính không dư thừa phải).
Ví dụ:
Cho F={A → BCDE, C →D, EG → H, AE → H}
Ta có
F1={A → B, A → C, A → D, A → E, C →D, EG → H, AE → H}I. PHỤ THUỘC HÀM
1.7.2. Tập phụ thuộc hàm tối thiểu
ii) Không tồn tại  phụ thuộc hàm  (X→A ) ∈ F mà F+ = (F \ {X →A})+ .   
(Tính không dư thừa phụ thuộc hàm).
Ví dụ:
F1={A → B, A → C, A → D, A → E, C →D, EG → H, AE → H}
Ta có
F2={A → B, A → C, A → E, C →D, EG → H, AE → H}I. PHỤ THUỘC HÀM
1.7.2. Tập phụ thuộc hàm tối thiểu
iii) Không tồn tại phụ thuộc hàm (X→A ) ∈F mà
F+
= (F \ {X →A} ∪ {Z → A})+ với Z⊂ X
(Tính không dư thừa trái)
Ví dụ:
F2={A → B, A → C, A → E, C →D, EG → H, AE → H}
Ta có
F3={A → B, A → C, A → D, A → E, C →D, EG → H, A → H}I. PHỤ THUỘC HÀM
1.7.3. Phủ tối thiểu
Cho tập phụ thuộc hàm F. Tập phụ thuộc hàm F’ là phủ tối thiểu
của F nếu:
– F’ là tập phụ thuộc hàm tối thiểu
– F’ ~ F.I. PHỤ THUỘC HÀM
Thu Thuậ ật to t toá án t n tì ìm ph m phủ ủ t tố ối thi i thiể ểu c u củ ủa t a tậ ập ph p phụ ụ thu thuộ ộc h c hà àm: m:
Vào:  Lược đồ quan hệ R(U), tập phụ thuộc hàm F = {Li
→ Ri
, i=1,..., m}
Ra: Tập phụ thuộc hàm F' là phủ tối thiểu của F
Cách thực hiện:
i) Xác định tập phụ thuộc hàm F1 ∼ F với F1  không dư thừa phải
bằng cách tách  các phụ thuộc hàm dạng  Li → A1 ... Ak thành các
phụ thuộc hàm Li
→ A1, ..., Li
→ Ak.
Ví dụ:
Cho F={A → BCDE, C →D, EG → H, AE → H}
Ta có
F1={A → B, A → C, A → D, A → E, C →D, EG → H, AE → H}
( Thay PTH A → BCDE bằng các PTH A → B, A → C, A → D, A → E)I. PHỤ THUỘC HÀM
Thu Thuậ ật to t toá án t n tì ìm ph m phủ ủ t tố ối thi i thiể ểu c u củ ủa t a tậ ập ph p phụ ụ thu thuộ ộc h c hà àm: m:
ii) Xác định tập phụ thuộc hàm F2 ∼ F1  không dư thừa phụ thuộc hàm
theo thuật toán sau:
+ Bước 0: Đặt F(0)
= F1
+ Bước i : Tính F(i)
=  F(i-1)
\{Li
→ Ri
} nếu F(i-1)
\{Li
→ Ri
} ∼ F(i-1)
F(i-1)
nếu ngược lại
Ví dụ:
F1={A → B, A → C, A → D, A → E, C →D, EG → H, AE → H}
Ta có
F2={A → B, A → C, A → E, C →D, EG → H, AE → H}I. PHỤ THUỘC HÀM
Thu Thuậ ật to t toá án t n tì ìm ph m phủ ủ t tố ối thi i thiể ểu c u củ ủa t a tậ ập ph p phụ ụ thu thuộ ộc h c hà àm: m:
iii) Xác định tập phụ thuộc hàm F3∼F2 không dư thừa trái bằng thuật toán
sau:
+ Bước 0: Đặt F(0)
=F2
+ Bước i : Tính F(i)
=    F(i-1)
\{Li
→Ri
}∪{Zi
→Ri
} nếu tồn tại Zi
⊂ Li
mà F(i-1)
\{Li
→ Ri
}∪ {Zi
→ Ri
} ∼ F(i-1)
F(i-1)
nếu ngược lại
Ví dụ:
F2={A → B, A → C, A → E, C →D, EG → H, AE → H}
Ta có
F3={A → B, A → C, A → E, C →D, EG → H, A → H}II. PHÉP TÁCH CÁC LƯỢC ĐỒ QUAN HỆ
2.1 Khái niệm phép tách lược đồ quan hệ
Cho lược đồ quan hệ R(U).
Tập các lược đồ ρ={R1(U1), R2(U2), ...,Rm(Um)} được gọi là phép tách
của R nếu U1
∪ U2
∪ ... ∪ Um=U.
Nếu ρ là phép tách của R, ta ký hiệu:
ρ (R1, R2, ..., Rm )
hay  ρ=(R1, R2, ..., Rm).II. PHÉP TÁCH CÁC LƯỢC ĐỒ QUAN HỆ
2.2. Phép tách không mất mát thông tin
Cho lược đồ quan hệ R và tập phụ thuộc hàm F. Phép tách  lược
đồ R thành tập các lược đồ R1, . . . , Rm được gọi là không mất mát
thông tin đối với F nếu với mỗi quan hệ r trên R thoả F thì
ΠU1(r)* ΠU2(r) * . . . * ΠUm(r) =rIII. CHUẨN HOÁ LƯỢC ĐỒ QUAN HỆ
3.1. Các khái niệm
– Chuẩn hoá lược đồ quan hệ là quá trình biến đổi các lược đồ quan
hệ thành các dạng thích hợp để tránh các dị thường về dữ liệu.
– Lược đồ được chuẩn hoá là lược đồ trong đómiền trị của mỗi
thuộc tính chỉ chứa các giá trị nguyên tố (không phân nhỏ được
nữa), do đómỗi giá trị trong các quan hệ cũng là các giá trị
nguyên tố.
– Lược đồ có chứa các miền trị không nguyên tố được gọi là lược đồ
không chuẩn hoá.III. CHUẨN HOÁ LƯỢC ĐỒ QUAN HỆ
3.2. Một số định nghĩa
Định nghĩa 1:
 Cho lược đồ quan hệ R trên tập thuộc tính U = { A1, A2,... , An}. Thuộc
tính A∈U được gọi là thuộc tính khoá nếu A là thành phần của một
khoá nào đócủa R. Ngược lại A được gọi là thuộc tính không khoá.
Ký hiệu Fn là tập thuộc tính không khóa.
Ví dụ:  Cho lược đồ quan hệ R(U) với U={ A, B, C, D, E}
F={AB →CE,  B → D, BC →A}.
Các khóa của R là K1=AB, K2= BC
 ) A, B, C là thuộc tính khoá
Fn={D, E}.III. CHUẨN HOÁ LƯỢC ĐỒ QUAN HỆ
3.2. Một số định nghĩa
Định nghĩa 2:
Cho lược đồ quan hệ R(U).  X ⊆U, A ∈U ; A được gọi là phụ thuộc
hàm đầy đủ vào X nếu A  phụ thuộc hàm  vào X (nghĩa là X→A) nhưng
A không phụ thuộc hàm vào bất kỳ tập con thực sự nào của X (nghĩa
là với ∀X'⊂ X  thì X'→A).
Ví dụ:  Cho lược đồ quan hệ R(U) với U={ A, B, C, D, E}
F={AB →CE,  B → D, BC →A}.
) Thuộc tính E là phụ thuộc hàm đầy đủ vào AB
Thuộc tính D là không phụ thuộc hàm đầy đủ vào AB (hay D phụ
thuộc hàm bộ phận vào AB)III. CHUẨN HOÁ LƯỢC ĐỒ QUAN HỆ
3.2. Một số định nghĩa
Định nghĩa 3:
Cho lược đồ quan hệ R(U).  X ⊆ U, A ∈U. A được gọi là phụ thuộc
bắc cầu vào X nếu tồn tại Y ⊂ U sao cho X →Y, Y → A nhưng Y → X
với A ∉XY.
Ví dụ:  Cho lược đồ quan hệ R(U) với U={ A, B, C, D, E}
F={A →BCE,  B → DC}.
) Thuộc tính D,C là phụ thuộc hàm bắc cầu vào AIII. CHUẨN HOÁ LƯỢC ĐỒ QUAN HỆ
3.3. Các dạng chuẩn (Normal Forms)
z Dạng chuẩn 1 ( 1NF)
z Dạng chuẩn 2 ( 2NF)
z Dạng chuẩn 3 ( 3NF) III. CHUẨN HOÁ LƯỢC ĐỒ QUAN HỆ
z Dạng chuẩn 1 ( 1NF)
Lược đồ quan hệ R được gọi là ở dạng chuẩn 1 (1NF) nếu toàn bộ các miền trị
có mặt trong R đều chỉ chứa các giá trị nguyên tố.
Ví dụ:
Không ở
dạng 1NF
Ở dạng
1NF
Dư thừa
dữ liệuIII. CHUẨN HOÁ LƯỢC ĐỒ QUAN HỆ
z Dạng chuẩn 2 (2NF)
Lược đồ quan hệ R được gọi là ở dạng chuẩn 2 (2NF) nếu:
– R ở dạng chuẩn 1
– Mọi thuộc tính không khoá của R đều phụ thuộc hàm đầy đủ vào khoá.
Ví dụ:
Cho lược đồ quan hệ R(U) với:
U=ABCDEGH, F={A → BC, D→EG, AD→H}
R(U) có ở dạng chuẩn 2 không?III. CHUẨN HOÁ LƯỢC ĐỒ QUAN HỆ
z Dạng chuẩn 3 (3NF)
Lược đồ quan hệ R được gọi là ở dạng chuẩn 3 (3NF) nếu:
– R ở dạng chuẩn 2
– Mọi thuộc tính không khoá của R đều không phụ thuộc bắc cầu vào khoá
của R.
Ví dụ:
Cho lược đồ quan hệ R(U) với:
U=ABCDEG, F={A → BCD, D→EG}
R(U) có ở dạng chuẩn 3 không?III. CHUẨN HOÁ LƯỢC ĐỒ QUAN HỆ
3.4. Phép tách một lược đồ quan hệ thành các lược đồ 3NF không
mất mát thông tin
z Vào: Lược đồ quan hệ R(U). Tập phụ thuộc hàm F.
z Ra: ρ ={R1(U1), ...,Rm(Um) | Ri
(Ui
), i=1, ..., m là 3NF}
với phép tách không mất mát thông
z Phương pháp:
– Bước 1: Tìm phủ tối thiểu F' của F
(Loại sự dư thừa trong tập phụ thuộc hàm)
– Bước 2: (Tách thành các lược đồ 3NF)
1. Đặt U0= X với  X là tập các thuộc tính không xuất hiện trong bất kỳ một phụ
thuộc hàm nào (cả vế trái lẫn vế phải) của F‘. Nếu U0 ≠∅ thì lấy R0(U0).
2. Xác định Ri (i>0): Mỗi nhóm PTH có cùng vế trái dạng: 
Li
→Ai1, ..., Li
→Aik thì xác định Ri
(Li
Ai1 . . . Aik)
Ta có ρ (Ri
(Ui
), R0(U0)) là phép tách thành 3NFIII. CHUẨN HOÁ LƯỢC ĐỒ QUAN HỆ
3.4. Phép tách một lược đồ quan hệ thành các lược đồ 3NF không
mất mát thông tin
– Bước 3: (Chuyển thành phép tách không mất mát thông tin)
1. Tìm một khoá K của R(U)
2. Kiểm tra K
i. Nếu tồn tại Ui
mà K ⊆ Ui
thì ρ(Ri
(Ui
), R0(U0)) là phép tách thành 3NF
không mất mát thông tin của R(U)
ii. Nếu không tồn tại Ui  thoả i) nhưng tồn tại Ui
mà K⊆ U0 ∪ Ui
thì ta có:
ρ(Ri
(Ui
), R0(K) với i >0) (thay U0 =K) là phép tách thành 3NF không mất
mát thông tin của R(U)
iii. Nếu  không tồn tại Ui
thoả ii) thì ρ(Ri
(Ui
), R0(U0), R(K)) là phép tách
thành 3NF không mất mát thông tin của R(U).