Bài giảng Cơ sở dữ liệu - Chương 7: Phụ thuộc hàm và chuẩn hóa cơ sở dữ liệu

ác thuộc tính của R.
• R có thể có nhiều khóa.
Phụ thuộc hàm
Xác định khóa của lược đồ
ƒ Nhập: tập PTH F xác định trên lược đồ R(U).
ƒ Xuất: khóa K của R.
ƒ Thuật toán 7.3.1
• B1: 
K = U = {A1, …, An};
i = 1;
• B2:
Nếu U ⊆ (K - {Ai})F+ thì K = K - {Ai}.
i = i + 1;
Nếu i > n thì sang B3. Ngược lại, tiếp tục B2.
• B3:
Xuất K.
Ví dụ tìm khóa của lược đồ
ƒ Cho R(U), U = {A, B, C, D, E, F, G}.
• F = {B → A, D → C, D → BE, DF → G}.
ƒ Tìm khóa của R
• B1: 
K = ABCDEFG.
• B2:
- Lặp 1: (BCDEFG)F+ = BCDEFGA ⇒ K = BCDEFG.
- Lặp 2: (CDEFG)F+ = CDEFGBA ⇒ K = CDEFG.
- Lặp 3: (DEFG)F+ = DEFGCBA ⇒ K = DEFG.
- Lặp 4: (EFG)F+ = EFG.
- Lặp 5: (DFG)F+ = DFGCBEA ⇒ K = DFG.
- Lặp 6: (DG)F+ = DGCBEA.
- Lặp 7: (DF)F+ = DFCBEAG ⇒ K = DF.
• B3: 
Khóa là K = DF.
Phụ thuộc hàm
Xác định tất cả khóa của lược đồ
ƒ Nhập: tập PTH F xác định trên lược đồ R(U).
ƒ Xuất: tất cả khóa của R.
ƒ Thuật toán 7.3.2
• B1: 
Xây dựng 2n tập con của U = {A1, …, An};
S = {};
• B2:
Với mỗi tập con X ⊆ U
Nếu U ⊆ XF+ thì S = S ∪ {X}.
• B3:
∀X, Y ∈ S, nếu X ⊂ Y thì S = S - {X}.
• B4:
S là tập các khóa của R.
Ví dụ tìm tất cả khóa của lược đồ
ƒ Cho R(U), U = {A, B, C, D, E, F}.
• F = {AE → C, CF → A, BD → F, AF → E}.
ƒ Tìm tất cả khóa của R
• Tập siêu khóa
S = {ABD, BCD, ABCD, ABDE, BCDE, ABCDE, ABDF, BCDF, ABCDF,
ABDEF, BCDEF, ABCDEF}.
ABD
BCD
ABCD
ABDE
BCDE
ABCDE
ABDF
BCDF
ABCDF
ABDEF
BCDEF
ABCDEF
Phụ thuộc hàm
Chuẩn hóa lược đồ CSDL
ƒ Chuẩn hóa là gì?
ƒ Các dạng chuẩn là gì?
ƒ Các dạng chuẩn
• Dạng 1 (1 Normal Form - 1NF).
• Dạng 2 (2 Normal Form - 2NF).
• Dạng 3 (3 Normal Form - 3NF).
• Dạng Boyce - Codd (Boyce - Codd Normal Form 
- BCNF).
Dạng chuẩn 1 (1)
ƒ Lược đồ quan hệ R được gọi là thuộc dạng chuẩn 1 nếu và
chỉ nếu mọi thuộc tính của R là thuộc tính đơn.
Go Vap9876543214Hanh chinh
Tan Binh,
Thu Duc
3334455555Nghien cuu
CacTrusoTrPhgMaPBTenPB
PHONGBAN
Thu Duc3334455555Nghien cuu
Go Vap9876543214Hanh chinh
Tan Binh3334455555Nghien cuu
TrusoTrPhgMaPBTenPB
PHONGBAN
Không thuộc 
dạng chuẩn 1
Thuộc dạng chuẩn 1
Phụ thuộc hàm
Dạng chuẩn 1 (2)
ƒ Nhận xét
• Mọi lược đồ quan hệ đều thuộc dạng chuẩn 1.
• Dạng chuẩn 1 có thể dẫn đến sự trùng lặp dữ liệu. Do đó
gây ra các dị thường về cập nhật dữ liệu.
Dạng chuẩn 2 theo khóa chính (1)
ƒ Lược đồ quan hệ R được gọi là thuộc dạng chuẩn 2 nếu mọi thuộc tính 
không khóa của R phụ thuộc đầy đủ vào khóa chính của R.
ƒ R(U), K ⊆ U là khóa chính của R
• A ∈ U là thuộc tính không khóa nếu A ∉ K.
• X → Y là PTH đầy đủ nếu ∀A ∈ X thì (X - {A}) → Y không đúng trên R. 
Ngược lại X → Y là PTH bộ phận.
ƒ Ví dụ
FD2
FD1
DiadiemTenDATenNVSoGioMaDAMaNV
FD3
NVIEN_DUAN
Thuộc tính không khóa
PTH đầy đủ
PTH bộ phận
Phụ thuộc hàm
Dạng chuẩn 2 theo khóa chính (2)
FD2
FD1
DiadiemTenDATenNVSoGioMaDAMaNV
FD3
NVIEN_DUAN
FD1
SoGioMaDAMaNV
NV_DA1
FD2
TenNVMaNV
NV_DA2
FD3
DiadiemTenDAMaDA
NV_DA3
3 lược đồ NV_DA1, NV_DA2, NV_DA3 thuộc dạng chuẩn 2
Dạng chuẩn 2 theo khóa chính (3)
ƒ Nhận xét
• Mọi lược đồ quan hệ thuộc dạng chuẩn 2 cũng thuộc 
dạng chuẩn 1.
• Nếu R chỉ có một khóa K và card(K) = 1 thì R thuộc dạng 
chuẩn 2.
• Còn xuất hiện sự trùng lặp dữ liệu. Do đó gây ra các dị 
thường về cập nhật dữ liệu.
FD2
FD1
TenPBMaPB TrPhongDChiNgSinhMaNVTenNV
NHANVIEN_PHONGBAN
Thuộc dạng 
chuẩn 2
Phụ thuộc hàm
Dạng chuẩn 3 theo khóa chính (1)
ƒ Lược đồ quan hệ R được gọi là thuộc dạng chuẩn 3 nếu
• R thuộc dạng chuẩn 2.
• Mọi thuộc tính không khóa của R không phụ thuộc bắt cầu vào khóa chính 
của R.
ƒ Cho R(U)
• X → Y là PTH bắt cầu nếu ∃Z ⊆ U, Z không là khóa và cũng không là tập 
con của khóa của R mà X → Z và Z → Y đúng trên R.
ƒ Ví dụ
FD2
FD3
FD1
TenPBMaPB TrPhongDChiNgSinhMaNVTenNV
NHANVIEN_PHONGBAN
PTH bắt cầu
Dạng chuẩn 3 theo khóa chính (2)
ƒ Nhận xét
• Mọi lược đồ quan hệ thuộc dạng chuẩn 3 cũng thuộc 
dạng chuẩn 2.
• PTH bắt cầu là nguyên nhân dẫn đến trùng lặp dữ liệu.
• Dạng chuẩn 3 là dạng chuẩn tối thiểu trong thiết kế
CSDL.
MaPBDiachiNgSinhMaNVTenNV
NV_PB1
TrPhgTenPBMaPB
NV_PB2
Thuộc dạng 
chuẩn 3
Phụ thuộc hàm
Dạng chuẩn 2 tổng quát
ƒ Lược đồ quan hệ R được gọi là thuộc dạng chuẩn 2 nếu 
mọi thuộc tính không khóa của R phụ thuộc đầy đủ vào các 
khóa của R.
ƒ Cho R(ABCDEF) có 2 khóa là A và BC.
FD3
FD2
FD1
FEDCBA
FD4
R
FD5
Lược đồ R không thuộc dạng chuẩn 2
Dạng chuẩn 3 tổng quát
ƒ Lược đồ quan hệ R được gọi là thuộc dạng chuẩn 3 nếu 
PTH không hiển nhiên X → A đúng trên R thì
• X là siêu khóa của R, hoặc
• A là thuộc tính khóa của R.
ƒ R1(ABCDE) có 2 khóa là A và BC.
ƒ Nhận xét
• Định nghĩa tổng quát cho phép kiểm tra dạng chuẩn 3 mà không cần 
kiểm tra dạng chuẩn 2.
FD2
FD1
EDCBA
FD4
R1
Lược đồ bên 
thuộc dạng 
chuẩn 2,
nhưng không
thuộc dạng
chuẩn 3FD5
Phụ thuộc hàm
Dạng chuẩn Boyce - Codd (1)
ƒ Lược đồ quan hệ R được gọi là thuộc dạng chuẩn BC nếu 
PTH không hiển nhiên X → Y đúng trên R thì X là siêu khóa 
của R.
ƒ R11(ABCD)
FD2
FD5
FD1
DCBA
R11
Lược đồ R11 thuộc dạng chuẩn 3,nhưng không thuộc dạng chuẩn BC
Dạng chuẩn Boyce - Codd (2)
1ba2
2ab3
2bb4
1aa1
DCBA
R11
1b2
2a3
2b4
1a1
DCA
R111
b2
a1
BD
R112
Trùng lặp dữ liệu
Phụ thuộc hàm
Dạng chuẩn Boyce - Codd (3)
ƒ Nhận xét
• Mọi lược đồ quan hệ thuộc dạng chuẩn BC cũng thuộc 
dạng chuẩn 3.
• Dạng chuẩn BC đơn giản và chặt chẽ hơn dạng chuẩn 3.
• Mục tiêu của quá trình chuẩn hóa là đưa các lược đồ
quan hệ về dạng chuẩn 3 hoặc BC.
FD1
DCA
R111
FD5
DB
R112
2 lược đồ trên thuộc dạng chuẩn BC
Thiết kế Top-Down
ƒ Các bước thực hiện
• Thiết kế lược đồ mức khái niệm với mô hình dữ liệu cấp 
cao (EER).
• Chuyển lược đồ khái niệm thành tập hợp các quan hệ.
• Với mỗi quan hệ xác định tập PTH.
• Áp dụng các quy tắc chuẩn hóa để loại bỏ các PTH bộ
phận và bắt cầu trong các quan hệ.
Phụ thuộc hàm
Phân rã lược đồ quan hệ
ƒ Lược đồ quan hệ chung R(A1, …, An)
• Tập hợp tất cả các thuộc tính của các thực thể.
ƒ Xác định tập PTH F trên R.
ƒ Phân rã
• Sử dụng các thuật toán chuẩn hóa để tách R thành tập 
các lược đồ D = {R1, …, Rm}.
ƒ Yêu cầu
• Bảo toàn thuộc tính.
• Các lược đồ Ri phải ở dạng chuẩn 3 hoặc Boyce-Codd.
Phân rã bảo toàn PTH (1)
ƒ Tính chất bảo toàn PTH
• Xét lược đồ R và tập PTH F. Giả sử R được phân rã 
thành D = {R1, …, Rm}.
- Đặt πRi(F) = {X → Y ∈ F+ : X ∪ Y ⊂ Ri}.
- D được gọi là phân rã bảo toàn phụ thuộc hàm đối với F nếu 
(πR1(F) ∪ … ∪ πRm(F))+ = F+.
ƒ Ví dụ
FD2
FD5
FD1
DCBA
R11
FD1
DCA
R111
FD5
DB
R112
Phụ thuộc hàm
Phân rã bảo toàn PTH (2)
2δα3
3γβ2
2βα1
DCBAR11
2δ3
4β4
3γ2
2β1
DCAR111
β3
4
2
D
α
α
BR112
…………
4βα4
2βα1
DCBA Thêm bộ (4, β, 4) vào R111
và (4, α) vào R112
thì trạng thái csdl sẽ không
thỏa PTH FD2
Phân rã bảo toàn PTH (3)
ƒ Định lý 7.1
• Tồn tại một phân rã bảo toàn PTH D = {R1, …, Rm} của 
lược đồ R đối với tập PTH F sao cho các Ri ở dạng 
chuẩn 3.
ƒ Thuật toán 7.4
• Nhập: R(U), U = {A1, …, An} và tập PTH F.
• Xuất: D = {R1, …, Rm}, Ri ở dạng chuẩn 3.
• B1: 
- Tìm phủ tối thiểu G của F.
• B2: 
- Với mỗi X → Aj ∈ G, xây dựng lược đồ Ri(Ui), Ui = X ∪ {Aj}. Khóa 
chính của Ri là X.
Phụ thuộc hàm
Phân rã bảo toàn PTH (4)
• B3:
- Giả sử xong B2 ta có các lược đồ R1, …, Rm. Nếu U1 ∪ … ∪ Um≠ U thì xây dựng thêm lược đồ Rm+1(Um+1), Um+1 = U - (U1 ∪ … ∪
Um). Khóa chính của Rm+1 là Um+1.
• B4:
- Xuất các lược đồ Ri.
Ví dụ phân rã bảo toàn PTH (1)
ƒ Cho
• R(ABCDEFG)
• F = {B → A, D → C, D → EB, DF → G}
ƒ Tách về dạng chuẩn 3, bảo toàn PTH
• B1:
- Phủ tối thiểu G = {B → A, D → C, D → B, D → E, DF → G}.
• B2:
• B3:
- Xuất D = {R1, R2, R3}.
R(ABCDEFG)
R1(BA) R(DC) R3(DFG)R(DB) R(DE)
R2(DBCE)
Phụ thuộc hàm
Ví dụ phân rã bảo toàn PTH (2)
ƒ Cho
• R(ABCDEFGHI)
• F = {B → A, D → C, D → EB, DF → G}
ƒ Tách về dạng chuẩn 3, bảo toàn PTH
• B1:
- Phủ tối thiểu G = {B → A, D → C, D → B, D → E, DF → G}.
• B2:
• B3:
- Vì U1 ∪ U2 ∪ U3 = {ABCDEFG} nên đặt R4(HI).
• B4:
- D = {R1, R2, R3, R4}.
R(ABCDEFG)
R1(BA) R3(DFG)R2(DBCE)
Phân rã không mất thông tin (1)
ƒ Tính chất không mất thông tin
• Xét lược đồ R và tập PTH F. Giả sử R được phân rã thành D = {R1, 
…, Rm}.
- D được gọi là phân rã không mất thông tin đối với F nếu với mọi trạng 
thái r ∈ R thì (πR1(r) * … * πRm(r)) = r.
ƒ Định lý 7.2
• Phân rã D = {R1(U1), R2(U2)} của R(U) không mất thông tin đối với 
tập PTH F nếu và chỉ nếu:
- (U1 ∩ U2) → (U1 – U2) ∈ F+, hoặc
- (U1 ∩ U2) → (U2 – U1) ∈ F+.
ƒ Định lý 7.3
• Nếu phân rã D = {R1, …, Rm} của R không mất thông tin đối với F và
phân rã Di = {Q1, …, Qk} của Ri không mất thông tin đối với πRi(F) thì
D’ = {R1, …, Ri-1, Q1, …, Qk, Ri+1, …, Rm} của R cũng không mất 
thông tin.
Phụ thuộc hàm
Phân rã không mất thông tin (2)
ƒ Thuật toán 7.5
• Nhập: R(U), U = {A1, …, An} và tập PTH F.
• Xuất: D = {R1, …, Rm}, Ri ở dạng chuẩn Boyce-Codd.
• B1:
- D = {R};
• B2:
- Nếu có lược đồ Q(UQ) ∈ D không ở dạng chuẩn BC thì
+ Tìm X → Y ∈ πQ(F) làm Q vi phạm điều kiện BC.
+ D = (D - {Q}) ∪ Q1(UQ1) ∪ Q2(UQ2) với UQ1 = UQ - Y và UQ2 = X ∪ Y.
+ Quay lại B2.
- Ngược lại, chuyển sang B3.
• B3:
- Xuất D.
Ví dụ phân rã không mất thông tin (1)
ƒ Cho:
• R(ABCDEFG)
• F = {B → A, D → C, D → EB, DF → G}
ƒ Tách về dạng chuẩn BC, không mất thông tin.
D → BCE
B → A
R(ABCDEFG)
R1(BA) R2(BCDEFG)
R3(DBCE) R4(DFG)
F, KR = DF
{B → A},
KR1 = B
{D → C, D → EB, DF → G},
KR2 = DF
{D → C, D → EB},
KR3 = D
{DF → G},
KR4 = DF
Phụ thuộc hàm
Ví dụ phân rã không mất thông tin (2)
D → A
D → BCE
R(ABCDEFG)
R1(DBCE) R2(ADEF)
R3(DA) R4(DFG)
F, KR = DF
{D → BCE},
KR1 = D
{D → A, D → E},
KR2 = DF
{D → A},
KR3 = D
{DF → G},
KR4 = DF
Phụ lục về Thuật toán 7.2
ƒ Với X → {A}, X = {B1, …, Bl}. Tại sao A ∈ (X - {Bi})F+ thì Bi
thừa?
• Đặt G = (F - {X → {A}}) ∪ {(X - {Bi}) → {A}}
• F+ ⊂ G+ là hiển nhiên vì X → {A} ∈ G+
- X → (X - {Bi}) và (X - {Bi}) → {A} ⇒ X → {A}.
• Khi nào G+ ⊂ F+?
- (X - {Bi}) → {A} ∈ F+ hay A ∈ (X - {Bi})F+.