Bài giảng Cơ sở dữ liệu - Chương 8: Phụ thuộc hàm và các dạng chuẩn - Lưu Huỳnh Châu Pha

CD→E, CD→EI } 
BCD→E là phụ thuộc hàm đầy đủ không? 
51 
Một số khái niệm (tt) 
PTH thừa 
Phụ thuộc hàm hiển nhiên: B phụ thuộc hàm hiển nhiên trên A nếu B ⊇ A. 
Xét X → Y là thừa nếu 
F ≡ F – {X→Y} 
Ví dụ: A → A, AB → B, ABC → BC là các PTH hiển nhiên 
52 
Phủ tối thiểu 
Cho F là tập các PTH định nghĩa trên R 
Mà VP chỉ chứa 1 thuộc tính 
PTH G gọi là PTT 
Nếu G là một phủ 
G chỉ chứa những PTH đầy đủ 
G không chứa những PTH thừa 
Ký hiệu: G=PTT(F) 
53 
Ví dụ 
R(A, B, C, D) 
F = { A→B, B→A, B→C, A→C, C→A } 
PTT(F) ? 
Mọi VP đều có 1 thuộc tính 
Các PTH đều đầy đủ 
Có thể bỏ phụ thuộc hàm thừa nào? 
54 
Ví dụ (tt) 
Xét A→B 
A + F – {A→B} = AC 
A→B không là phụ thuộc hàm thừa 
Xét B→A 
B + F-{B→A} = BCA 
B→A là phụ hàm thừa 
không chứa VP 
có chứa VP 
55 
Ví dụ (tt) 
Nếu bỏ đi B→A và A→C thì 
F’ = { A→B, B→C, C→A } 
F’ ≡ F nên F’=PTT(F) 
Chỉ cần xét F được suy dẫn từ F’ 
Nếu bỏ đi B→C 
F” = { A→B, B→A, A→C, C→A} 
F” ≡ F nên F”=PTT(F) 
F’ ≡ F” 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
56 
Thuật toán tìm tập pth nhỏ nhất G dựa trên F 
G ← F 
Replace each FD X → { A 1 , A 2 , ......., A n } in G by n FDs X → A 1 , X → A 2 ,  , X → A n . 
For each FD X → A in G 
	 for each attribute B that is an element of X 
	 If ( ( G – { X → A }) ∪ {( X – { B }) → A } ) is eq nt to G, 
	 then replace X → A with ( X – { B }) → A in G. 
For each remaining FD X → A in G 
	 If ( G – { X → A }) is equivalent to G, 
	 then remove X → A from G. 
57 
Ví dụ 
R(A, B, C) 
F = { AB→C, A→B, B→C } 
PTT(F) ? 
Mọi VP đều có 1 thuộc tính 
Có AB→C không là PTH đầy đủ 
Thay thế bằng các PTH đầy đủ 
Có thể bỏ phụ thuộc hàm thừa nào? 
58 
Ví dụ (tt) 
F = { A→C, A→B, B→C } 
Có thể bỏ phụ thuộc hàm thừa nào? 
59 
Các khái niệm khóa 
Khóa 
Là một tập các thuộc tính dùng để xác định tính duy nhất của mỗi bộ trong quan hệ 
→ Các bộ trong quan hệ khác nhau từng đôi một 
Gồm 
Siêu khóa 
Khóa 
Khóa chính 
60 
Siêu khóa 
Xét quan hệ R 
Gọi SK là một tập con khác rỗng các thuộc tính của R 
SK là siêu khóa khi và chỉ khi 
Mọi lược đồ quan hệ có tối thiểu 1 siêu khóa 
⇒ 
∀ 
r, 
∀ 
t1, t2 
∈ 
r, t1 
t2 
≠ 
≠ 
t1[SK] 
t2[SK] 
Hai bộ bất kỳ có các giá trị khác nhau tại tập thuộc tính siêu khóa 
61 
Khóa 
Xét quan hệ R 
Gọi K là một tập con khác rỗng các thuộc tính của R 
K là khóa nếu thỏa đồng thời 2 điều kiện: 
- K là một SK 
Một lược đồ quan hệ có thể có nhiều khóa 
Khóa được chọn để cài đặt gọi là khóa chính 
không phải là siêu khóa của R 
- ∀ 
≠ 
K 
, K’ 
K’ 
⊂ 
K 
, K’ 
Khóa là siêu khóa bé nhất 
62 
Ví dụ 
A 
B 
C 
R 
x 
1 
10 
D 
a 
x 
2 
20 
a 
1 
1 
1 
40 
40 
50 
b 
c 
d 
y 
y 
z 
Tập hợp các thuộc tính 
ABCD 
ABC, ABD, ACD, BCD 
AB, AC, AD, BC, BD, CD 
A, B, C, D 
Siêu khóa 
ABCD, ABD, ACD, BCD, BD, CD 
Khóa 
BD, CD 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
63 
PTH và Khóa 
Phụ thuộc hàm cho phép ta diễn tả các RBTV không thể diễn tả bằng siêu khóa. 
Vd., lược đồ Muon(tenkh, magdmuon, tencn, sotien) 
Ta muốn có tập các pth sau: 
	 magdmuon → sotien	magdmuon → tencn 
	nhưng không muốn có pth (vì một giao dịch mượn có thể của nhiều khách hàng): 
	 magdmuon → tenkh 
64 
Đồ thị phụ thuộc hàm 
Đồ thị phụ thuộc hàm là một đồ thị vô hướng, với : 
Một tập nút tượng trưng cho tập PTH, ký hiệu O với tên PTH bên cạnh. 
Một tập nút tượng trưng cho các thuộc tính, ký hiệu ● với tên thuộc tính bên cạnh. 
Một tập cung có hướng nối một nút PTH(thuộc tính) đến một nút thuộc tính (PTH). 
Một cung xuất phát từ nút thuộc tính A đến một nút PTH f, cùng với một cung từ nút PTH f đến nút thuộc tính B, biểu diễn cho PTH A→B 
Khi F có nhiều PTT, đồ thị của F có chứa chu trình. 
65 
Ví dụ 
Cho F = {f 1 :A→BC; f 2 : B →A; f 3 : AD →E; f 4 :BD →E } 
Đồ thị của F: 
A 
C 
E 
B 
D 
f 1 
f 2 
f 3 
f 4 
66 
Ứng dụng phụ thuộc hàm vào khóa 
Thuật toán xác định khóa của quan hệ: 
Xây dựng các tổ hợp có thể có từ Q + 
Tìm tập S chứa tất cả các tổ hợp K ⊆ Q + thỏa điều kiện (i), mỗi tổ hợp K như vậy là một siêu khóa của Q. 
∀K∈ S 
	Nếu ∃K’ | K’ ⊂ K thì loại K ra khỏi S 
Thực tế, kết hợp bước 2 và bước 3: bắt đầu xét từ những tổ hợp có ít phần tử nhất, nếu tìm được một tổ hợp K i thỏa điều kiện (i) thì loại bỏ ngay các tổ hợp có chứa K i. 
Vấn đề: Số tổ hợp có thể có từ Q + sẽ rất lớn nếu Q + lớn → Cần giới hạn số tổ hợp cần khảo sát 
67 
Ứng dụng phụ thuộc hàm vào khóa 
Giới hạn số lượng tổ hợp: 
Thuộc tính nguồn: 
A là một thuộc tính nguồn nếu ¬∃f: X→Y ∈ F |A∈Y 
Trên đồ thị PTH, thuộc tính nguồn không có cung vào 
Nhận xét: mọi thuộc tính nguồn phải xuất hiện trong mọi khóa của Q 
Thuộc tính đích: 
B là một thuộc tính đích nếu ¬∃f: X→Y ∈ F | B∈X 
Trên đồ thị PTH, thuộc tính đích chỉ có cung vào, không có cung ra. 
Nhận xét: thuộc tính đích không xuất hiện trong bất kỳ khóa nào của Q 
68 
Ví dụ 
Cho Q(ABCDEG) với 
	F = {f 1 : AD→B; f 2 :EG →A; f 3 : BC →G} 
	Xác định các khóa của Q? 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
69 
Dạng chuẩn 
Mục đích: làm cho sự trùng lắp dữ liệu ít nhất 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
70 
Dạng chuẩn 1(First Normal Form – 1NF) 
Một lược đồ R đạt chuẩn 1NF nếu như miền giá trị của các thuộc tính trên R là nguyên tố(atomic) 
Non-atomic 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
71 
UNF to 1NF 
Điền vào các chỗ trống bằng dữ liệu trùng lắp → dẫn đến nhiều dữ liệu bị trùng lắp trên quan hệ. 
Thay thế các giá trị không nguyên tố bằng cách xác định tập thuộc tính làm khóa chính và sau đó tách thành một quan hệ mới → tạo ra hai hay nhiều quan hệ mới, và sẽ làm giảm bớt sự trùng lắp thông tin. 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
72 
UNF to 1NF (method 1) 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
73 
UNF to 1NF (method 2) 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
74 
Dạng chuẩn 2 (2NF) 
Một lược đồ đạt dạng chuẩn 2 nếu như lược đồ đó đã đạt dạng chuẩn một và các thuộc tính không khóa phụ thuộc đầy đủ vào thuộc tính khóa 
1NF 
propertyNo → pAdress 
PK = {clientNo, propertyNo) 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
75 
1NF to 2NF 
Xác định khóa chính trên quan hệ bị 1NF 
PropertyRentalOwner: clientNo , propertyNo 
Xác định các pth chỉ liên quan đến khóa chính 
	clientNo, propertyNo → pAddress, rentStart, rentFinish, rent, ownerNo, oName 
	propertyNo → pAddress, rent, ownerNo, oName 
Nếu có tồn tại pth riêng phần trên khóa chính thì xóa chúng bằng cách thay thế bằng quan hệ mới 
X ó a (pAddress, rent, ownerNo, oName) từ PropertyRentalOwner bằng c á ch thay ch ú ng th à nh quan hệ mới PreoprtyOwner . 
PropertyRentalOwner được đổi tên th à nh Rental . 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
76 
1NF to 2NF(tt) 
1NF 
2NF 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
77 
Dạng chuẩn 3(3NF) 
Một lược đồ R ở dạng chuẩn 3 khi nó đạt dạng chuẩn 2 và tất cả các thuộc tính không khóa không phụ thuộc bắt cầu vào khóa 
Ví dụ: 
1. propertyNo → pAddress, rent, ownerNo, oName 
⇒ propertyNo → ownerNo 
2. ownerNo → oName 
Bắc cầu: propertyNo → oName 
Vì thế, PropertyOwner không đạt 3NF 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
78 
2NF to 3NF 
Xác định thuộc tính khóa trong quan hệ đạt dạng chuẩn 2 
	PropertyOwner: propertyNo 
Xác định phụ thuộc hàm trong quan hệ 
	propertyNo → pAddress, rent, ownerNo, oName 
	ownerNo → oName 
Nếu pth bắt cầu tồn tại trên khóa chính thì xóa bỏ chúng bằng cách thay thế chúng bằng một quan hệ mới. 
X ó a oName từ PropertyOwner bằng c á ch thay thế quan hệ Owner . 
PropertyOwner được thay đổi th à nh PropertyForRent . 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
79 
2NF to 3NF 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
80 
BCNF(Boyce – Codd NF) 
Một lược đồ chỉ đạt dạng chuẩn BCNF nếu khi mỗi xác định đều là siêu khóa. 
Mọi quan hệ đạng chuẩn BCNF đều đạt dạng chuẩn 3, nhưng ngược lại thì chưa chắc. 
Example: 
Client , PropertyForRent & Owner đạt chuẩn BCNF vì mỗi xác định có thể đều là khóa. 
Rental cũng đạt chuẩn BCNF vì mỗi xác định (vd. clientNo , propertyNo hoặc clientNo , rentStart hoặc propertyNo , rentStart ) đều cũng là khóa 
3NF to BCNF 
Xác định phụ thuộc hàm A → B của Q, trong đó A#B và A không là siêu khóa 
Phân rã quan hệ gốc Q thành hai quan hệ Q1={A,B}, Q2 ={tập các thuộc tính còn lại của Q} 
Lặp lại qui trình trên cho Q2 đến khi không thể tiếp tục. 
Quan hệ Q1 và các Qi phân rã được từ Q2 là quan hệ cuối cùng đạt chuẩn BCNF 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
81 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
82 
3NF to BCNF 
3NF 
Primary key 
Primary key 
Ví dụ 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
83 
 Xét quan hệ Hướngdẫn 
Các qui tắc đặt trên quan hệ là: 
Mỗi sinh viên có thể theo một số chủ đề 
Mỗi chủ đề có thể có một số hướng dẫn viên 
Một hướng dẫn viên chỉ tư vấn cho một chủ đề 
Mỗi sinh viên cụ thể theo một chủ đề có một hướng dẫn viên cụ thể 
Một hướng dẫn viên có thể tư vấn một số sinh viên 
Mã sinh viên 
Chủ đề 
Hướng dẫn viên 
97001 
Mạng truyền thông 
Mr.Minh 
97001 
Hệ thống TT 
Mr.Hà 
97003 
Cơ sở dữ liệu 
Mr.Hiếu 
97004 
Mạng truyền thông 
Mr.Nam 
97005 
Mạng truyền thông 
Mr.Minh 
Ví dụ: 
Yêu cầu 
Xác định các phụ thuộc hàm liên quan? 
Xác định dạng chuẩn của Hướngdẫn? 
Chuẩn hóa thành dạng chuẩn cao nhất 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
84 
Ví dụ 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
85 
Cho quan hệ 
Các phụ thuộc hàm 
Sohd → makh,tenkh,dckh,ngayhd,mahg,tenhg,mota_hg,dvt 
Makh → tenkh, dckh 
Mahg → tenhg,mota_hg,dvt 
Sohd,mahg → soluong_hg 
HÓA ĐƠN 
Sohd,makh,tenkh,dckh,ngayhd,mahg,tenhg,mota_hg,dvt,soluong_hg 
Ví dụ 
Yêu cầu 
Xác định khóa? 
Chuẩn hóa lược đồ trên sao cho đạt chuẩn cao nhất? 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
86 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 
87