Bài giảng Cơ sở dữ liệu và quản trị cơ sở dữ liệu - Chương 5: Lý thuyết về phụ thuộc hàm - Nguyễn Vương Thịnh

TR ƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM 
KHOA CÔNG NGHỆ THÔNG TIN 
BÀI G I ẢNG HỌC PHẦN  CƠ SỞ DỮ LIỆU VÀ QUẢN TRỊ CƠ SỞ DỮ LIỆU 
Giảng viên : ThS. Nguyễn V ươ ng Thịnh 
Bộ môn : Hệ thống thông tin 
Hải Phòng, 2016 
Chương 5 
LÝ THUYẾT VỀ PHỤ THUỘC HÀM 
2 
Thông tin về giảng viên 
Họ và tên 
Nguyễn Vương Thịnh 
Đơn vị công tác 
Bộ môn Hệ thống thông tin – Khoa Công nghệ thông tin 
Học vị 
Thạc sỹ 
Chuyên ngành 
Hệ thống thông tin 
Cơ sở đào tạo 
Trường Đại học Công nghệ - Đại học Quốc Gia Hà Nội 
Năm tốt nghiệp 
2012 
Điện thoại 
0983283791 
Email 
thinhnv@vimaru.edu.vn 
Website 
3 
Thông tin về học phần 
Tên học phần 
Cơ sở dữ liệu và quản trị cơ sở dữ liệu 
Tên tiếng Anh 
Data base and Database Management 
Mã học phần 
17425 
Số tín chỉ 
04 tín chỉ (LT: 45 tiết, TH: 30 tiết) 
Bộ môn phụ trách 
Hệ thống thông tin 
PHƯƠNG PHÁP HỌC TẬP, NGHIÊN CỨU 
Nghe giảng, t hảo luận, trao đổi với giảng viên trên lớp. 
Tự n ghiên cứu tài liệu và làm bài tập ở nhà. 
PHƯƠNG PHÁP ĐÁNH GIÁ 
SV phải t ham dự ít nhất 75% thời gian . 
Có 02 bài kiểm tra viết giữa học phần (X 2 = (L 1 + L 2 )/2), 01 bài kiểm tra thực hành (X 3 ). Điểm quá trình X = (X 2 + X 3 )/2. 
Thi kết thúc học phần bằng hình thức trắc nghiệm khách quan trên máy tính (Z = 0.5X + 0.5Y). 
4 
Tài liệu tham khảo 
Elmasri, Navathe, Somayajulu, Gupta, Fundamentals of Database Systems (the 4 th Edition) , Pearson Education Inc, 2004. 
Nguyễn Tuệ, Giáo trình Nhập môn Hệ Cơ sở dữ liệu , Nhà xuất bản Giáo dục Việt Nam, 2007. 
Nguyễn Kim Anh, Nguyên lý của các hệ Cơ sở dữ liệu , Nhà xuất bản Đại học Quốc g ia Hà Nội, 2004. 
5 
Tài liệu tham khảo 
LÝ THUYẾT VỀ PHỤ THUỘC HÀM 
5 .1. PHỤ THUỘC HÀM VÀ HỆ TIÊN ĐỀ ARMSTRONG 
5.2. BAO ĐÓNG CỦA TẬP PHỤ THUỘC HÀM 
5.3. BAO ĐÓNG CỦA TẬP THUỘC TÍNH 
5.4. PHỦ TỐI THIỂU CỦA TẬP PHỤ THUỘC HÀM 
5.6. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ 
6 
7 
Giáo sư William Ward Armstrong 
Đại học Montreal, Canada 
8 
5 .1. PHỤ THUỘC HÀM VÀ HỆ TIÊN ĐỀ ARMSTRONG 
5.1.1. ĐỊNH NGHĨA PHỤ THUỘC HÀM 
Ví dụ: Xét quan hệ trên lược đồ quan hệ Đặt Hàng 
Mã KH 
Tên KH 
Số CMND 
Điện Thoại 
Mã MH 
Tên MH 
Đơn vị tính 
Đơn Giá 
Số Lượng 
Ngày Đặt 
KH01 
An 
031275568 
0988812322 
MH01 
USB 32G 
Chiếc 
25$ 
30 
11/6 
KH02 
Bình 
031254678 
0912345678 
MH02 
Ốp lưng 
Chiếc 
10$ 
100 
20/7 
KH01 
An 
031275568 
0988812322 
MH02 
Ốp lưng 
Chiếc 
20$ 
50 
28/7 
KH03 
Cường 
031255566 
0987654323 
MH01 
USB 32G 
Chiếc 
25$ 
25 
29/7 
KH02 
Bình 
031254678 
0912345678 
MH03 
Thẻ 16G 
Chiếc 
15$ 
20 
01/8 
KH03 
Cường 
031255566 
0987654323 
MH03 
Thẻ 16G 
Chiếc 
15$ 
55 
09/10 
Mã KH quyết định Tên KH, Số CMND, Điện Thoại 
Ký hiệu: Mã KH → Tên KH, Số CMND, Điện Thoại 
Số CMND quyết định Mã KH, Tên KH, Điện Thoại 
Ký hiệu: Số CMND → Mã KH, Tên KH, Điện Thoại 
Mã MH quyết định Tên MH, Đơn V ị T ính, Đơn Giá 
Ký hiệu: Mã MH → Tên MH, Đơn Vị Tính, Đơn Giá 
Mã KH, Mã MH quyết định Số Lượng, Ngày Đặt 
Ký hiệu: Mã KH, Mã MH → Số Lượng, Ngày Đặt 
Phụ thuộc hàm 
9 
Cho lược đồ quan hệ R( Ω ) và các tập thuộc tính X, Y  Ω . 
Ta nói X quyết định Y hay Y phụ thuộc hàm vào X (ký hiệu: X→Y) khi và chỉ khi với mọi quan hệ r trên R( Ω ) và với 02 bộ t 1 , t 2 bất kỳ thuộc r ta luôn có: Nếu t 1 [X] = t 2 [X] thì t 1 [Y] = t 2 [Y] 
Lưu ý : 
+ Phụ thuộc hàm X →  đúng với mọi quan hệ r 
+ Phụ thuộc hàm  → Y đúng với quan hệ r có cùng giá trị trên Y 
A 
B 
C 
a 2 
b 2 
c 2 
a 1 
b 1 
c 1 
a 2 
b 2 
c 2 
a 1 
b 1 
c 1 
a 2 
b 2 
c 2 
a 1 
b 1 
c 1 
X 
Y 
Viết X → Y có nghĩa là: 
Cứ mang giá trị giống nhau trên X thì phải mang giá trị giống nhau trên Y 
10 
5.1.2. HỆ TIÊN ĐỀ ARMSTRONG 
Cho lược đồ quan hệ R( Ω ) và các tập thuộc tính X, Y, Z, W  Ω 
5.1.2.1. LUẬT PHẢN XẠ: Nếu Y  X thì X → Y 
5.1.2.2. LUẬT TĂNG TRƯỞNG: Nếu X → Y thì XZ → YZ 
5.1.2.3. LUẬT BẮC CẦU: Nếu X → Y và Y → Z thì X → Z 
5.1.2.4. LUẬT KẾT HỢP: Nếu X → Y và X → Z thì X → YZ 
5.1.2.5. LUẬT PHÂN RÃ: Nếu X → YZ thì X → Y và X → Z 
5.1.2.6. LUẬT GIẢ BẮC CẦU: Nếu X → Y và YW → Z thì XW → Z 
Được công bố bởi William Ward Armstrong vào năm 1974 
11 
5.2. BAO ĐÓNG CỦA TẬP PHỤ THUỘC HÀM 
5.2.1. BAO ĐÓNG LOGIC CỦA TẬP PHỤ THUỘC HÀM 
5.2.1.1. Phụ thuộc hàm được suy dẫn logic từ tập phụ thuộc hàm F 
Phụ thuộc hàm X → Y được gọi là suy dẫn logic từ tập phụ thuộc hàm F nếu như mọi quan hệ r thỏa mãn tất cả các phụ thuộc hàm trong tập phụ thuộc hàm F thì cũng thỏa mãn phụ thuộc hàm X → Y. 
Ký hiệu: 
5.2.1.2. Bao đóng logic của tập phụ thuộc hàm F 
Tập tất cả các phụ thuộc hàm có thể suy dẫn logic từ tập phụ thuộc hàm F được gọi là bao đóng logic của F. Ký hiệu là F * . 
12 
5.2.2. BAO ĐÓNG CỦA TẬP PHỤ THUỘC HÀM 
5.2.2.1. Phụ thuộc hàm suy dẫn được từ tập phụ thuộc hàm F nhờ hệ tiên đề Armstrong 
Phụ thuộc hàm X → Y được gọi là suy dẫn được từ tập phụ thuộc hàm F nhờ hệ tiên đề Amrstrong nếu như ta có thể suy dẫn ra phụ thuộc hàm này từ các phụ thuộc hàm trong F bằng cách áp dụng liên tiếp các luật của hệ tiên đề Armstrong. 
Ký hiệu: 
5.2.2.2. Bao đóng của tập phụ thuộc hàm F 
Tập tất cả các phụ thuộc hàm có thể suy dẫn ra từ tập phụ thuộc hàm F nhờ áp dụng các luật cùa hệ tiên đề Armstrong được gọi là bao đóng (closure) của F. Ký hiệu là F + . 
13 
5.2.2.3. Tính chất của bao đóng của tập phụ thuộc hàm 
A. Tính phản xạ: F  F + 
B. Tính đơn điệu: Nếu F  G thì F +  G + 
C. Tính bao phủ: Nếu F  G + thì F +  G + 
D . Tính lũy đẳng: (F + ) + = F + 
14 
5.2.3. HỆ TIÊN ĐỀ ARMSTRONG LÀ ĐÚNG VÀ ĐẦY ĐỦ 
A. Hệ tiên đề Armstrong là đúng : 
Từ tập phụ thuộc hàm F ban đầu, h ệ tiên đề Armstrong chỉ có thể sinh ra các phụ thuộc hàm nằm trong F * 
B. Hệ tiên đề Armstrong là đầy đủ : 
Từ tập phụ thuộc hàm F ban đầu, h ệ tiên đề Armstrong có thể sinh ra được tất cả các phụ thuộc hàm của F * 
Vậy nên: 
Kể từ giờ trở đi ta không phân biệt F * hay F + nữa mà chỉ dùng một khái niệm bao đóng F + 
15 
5.3. BAO ĐÓNG CỦA TẬP THUỘC TÍNH 
5.3.1. KHÁI NIỆM 
Bao đóng của tập thuộc tính X đối với tập phụ thuộc hàm F ký hiệu là X + được định ngĩa như sau: với . 
5.3.2. THUẬT TOÁN TÌM BAO ĐÓNG CỦA TẬP THUỘC TÍNH 
Xác định liên tiếp các tập thuộc tính X 0 , X 1 , X 2 ,... 
Bước 1 : X 0 = X 
Bước 2 : Lần lượt xét các phụ thuộc hàm trong F. Nếu có phụ thuộc hàm Y → Z nào đó có Y  X i thì X i+1 = X i  Z. Sau đó loại phụ thuộc hàm Y → Z ra khỏi tập phụ hàm F. 
Bước 3 : Nếu tại bước 2 không tìm được thêm X i+1 thì X i là bao đóng của X. Ngược lại, tiếp tục lặp lại bước 2 . 
16 
Ví dụ : Cho lược đồ quan hệ R(A,B,C,D,E,G,H) và tập phụ thuộc hàm : 
F = {B → A, DA → CE, D → H, GH → C, AC → D} 
Tìm bao đóng của X = AC . 
Giải : 
Bước 1: X o = AC 
Bước 2: Duyệt các phụ thuộc hàm trong F: 
- Có AC → D nên X 1 = X o  {D} = ACD và loại AC → D khỏi F 
Lặp lại bước 2: Duyệt các phụ thuộc hàm còn lại trong F: 
- Có DA → CE nên X 2 = X 1  {CE} = ACDE và loại DA → CE ra khỏi F 
- Có D → H nên X 3 = X 2  {H} = ACDEH và loại D → H ra khỏi F. 
Lặp lại bước 2: Từ các phụ thuộc hàm còn lại F = {B → A, GH → C} không thể sinh thêm X 4 từ X 3 
Bước 3: Thuật toán kết thúc. Bao đóng là X + = X 3 = ACDEH. 
17 
5.3.3. TÍNH CHẤT CỦA BAO ĐÓNG CỦA TẬP THUỘC TÍNH 
A. Tính phản xạ: X  X + 
B. Tính đơn điệu: Nếu X  Y thì X +  Y + 
C. Tính lũy đẳng: (X + ) + = X + 
D. Các tính chất khác: 
X + Y +  (XY) + 
(X + Y) + = (XY + ) + = (X + Y + ) + 
X → Y Y +  X + 
X → X + và X + → X 
X + = Y + X → Y và Y → X 
18 
5.3.4. ĐỊNH LÝ BÀI TOÁN THÀNH VIÊN 
Chứng minh định lý 
Chứng minh 
Với mọi thuộc tính A i ∈ Y: Vì Y ⊆ X + nên A i ∈ X + . Theo định nghĩa bao đóng tập thuộc tính nếu A i ∈ X + thì X → A i ∈ F + . Áp dụng luật hợp thì hay 
Chứng minh 
Xét Áp dụng luật phân rã thì với mọi thuộc tính A i ∈ Y ta luôn có X → A i ∈ F + . Theo định nghĩa bao đóng tập thuộc tính nếu X → A i ∈ F + thì A i ∈ X + . Mà m ọi phần tử A i ∈ Y đều thuộc X + nên Y ⊆ X + 
19 
Ví dụ 5.1 : Cho lược đồ quan hệ R(A,B,C,D,E,G,H) và tập phụ thuộc hàm: F = {B → A, DA → CE, D → H, GH → C, AC → D} 
Chứng minh rằng p hụ thuộc hàm AC → EH có thể suy diễn ra từ các phụ hàm trong F. 
Giải 
Cách 1 : Chỉ ra một cách suy diễn có thể: 
 (Luật bắc cầu) 
 (Luật tăng trưởng 2 vế - thêm A) 
 (Luật bắc cầu và luật phân rã) 
 (Luật hợp) (đpcm) 
Cách 2 : Dùng định lý bài toán thành viên: 
Tính bao đóng vế trái: (AC) + = ACDEH. Vì vế phải EH ⊆ ACDEH nên phụ thuộc hàm AC → EH ∈ F + hay có thể suy diễn ra từ F (đpcm). 
20 
5.3.5. TÌM BAO ĐÓNG CỦA TẬP PHỤ THUỘC HÀM DỰA TRÊN BAO ĐÓNG CỦA TẬP THUỘC TÍNH 
Cho lược đồ quan hệ R( Ω ) và tập phụ thuộc hàm F 
Thuật toán tìm F + 
Bước 1 : Tìm tất cả các tập thuộc tính là tập con thực sự của Ω . 
Bước 2 : Tìm bao đóng của từng tập thuộc tính con của Ω tìm được ở bước 1. 
Bước 3 : Dựa vào các bao đóng của các tập thuộc tính con tìm được ở bước 2 để suy ra các phụ thuộc hàm trong F + . 
21 
X 
X + 
Các tập con của X + không thuộc X 
Các phụ thuộc hàm trong F + 
(không kể các phụ thuộc hàm hiển nhiên) 
A 
A 
B 
B 
C 
BC 
B, BC 
C → B, C → BC 
AB 
ABC 
C, AC, BC, ABC 
AB → C, AB → AC, AB → BC, AB → ABC 
AC 
ABC 
B, AB, BC, ABC 
AC → B, AC → AB, AC → BC, AC → ABC 
BC 
BC 
Ví dụ 5.2 : Cho lược đồ quan hệ R(A, B, C) và tập phụ thuộc hàm: 
F = {AB → C, C → B} 
Hãy tìm bao đóng F + của tập phụ thuộc hàm F. 
Lưu ý : Các phụ thuộc hàm hiển nhiên là phụ thuộc hàm dạng 
X → X hoặc X → Y với Y ⊆ X 
22 
5.4. PHỦ TỐI THIỂU CỦA TẬP PHỤ THUỘC HÀM 
5.4.1. TẬP PHỤ THUỘC HÀM TƯƠNG ĐƯƠNG 
5.4.1.1. Định nghĩa 
Hai tập phụ thuộc hàm F và G được gọi là tương đương với nhau (ký hiệu F ≡ G) nếu như F + = G + 
5.4.1.2. Cách c hứng minh 2 tập phụ thuộc hàm F và G là tương đương 
Bước 1 : Chứng minh mọi phụ thuộc hàm X → Y ∈ F là thành viên của G + hay F  G + và từ tính chất bao phủ suy ra F +  G + (1) 
Bước 2 : Chứng minh mọi phụ thuộc hàm X → Y ∈ G là thành viên của F + hay G  F + và từ tính chất bao phủ suy ra G +  F + (2) 
Từ (1) và (2) suy ra F + = G + hay F ≡ G (đpcm) 
23 
Ví dụ 5.3 : Cho lược đồ quan hệ R(A,B,C,D,E) và 2 tập phụ thuộc hàm: 
F = {A → BC, A → D, CD → E} 
G = {A → BCE, A → ABD, CD → E} 
Hai tập phụ thuộc hàm F và G có tương đương với nhau không? 
Giải : 
+ Chứng minh F  G + : Xét từng phụ thuộc hàm trong F 
A → BC: (A) + G = ABCDE mà BC  ABCDE nên A → BC ∈ G + 
A → D : (A) + G = ABCDE mà D  ABCDE nên A → D ∈ G + 
CD → E: (CD) + G = CDE mà E  CDE nên CD → E ∈ G + 
Vậy F  G + hay theo tính chất bao phủ thì F +  G + (1) 
+ Chứng minh G  F + : Xét từng phụ thuộc hàm trong G 
A → BCE: (A ) + F = ABCDE mà BCE  ABCDE nên A → BCE ∈ F + 
A → ABD: (A ) + F = ABCDE mà ABD  ABCDE nên A → ABD ∈ F + 
CD → E: (CD ) + F = CDE mà E  CDE nên CD → E ∈ F + 
Vậy G  F + hay theo tính chất bao phủ thì G +  F + (2) 
Từ (1) và (2) suy ra F + = G + hay F ≡ G 
24 
5.4.2. TẬP PHỤ THUỘC HÀM CÓ VẾ TRÁI KHÔNG DƯ THỪA 
5.4.2.1. Phụ thuộc hàm có vế trái dư thừa 
Phụ thuộc hàm X → Y trong F được gọi là có vế trái dư thừa (hay phụ thuộc hàm không đầy đủ ) nếu như tồn tại X’ ⊂ X sao cho: 
F ≡ F\{ X → Y} ∪ {X’ → Y} 
Ngược lại, X → Y được gọi là phụ thuộc hàm có vế trái không dư thừa (hay phụ thuộc hàm đầy đủ ). 
Ví dụ: Cho tập phụ thuộc hàm F = {A → BC, B → C, AB → D} 
Phụ thuộc hàm AB → D có vế trái dư thừa (thừa thuộc tính B) vì: 
F\{ AB → D} ∪ { A → D} = { A → BC, B → C, A → D} ≡ F 
(Bản chất là vì A → BC nên A → B và dẫn tới A B → D không cần có thuộc tính B mà chỉ cần A → D là đủ ) 
25 
5.4.2.2. Tìm t ập phụ thuộc hàm có vế trái không dư thừa 
A. Định nghĩa : Tập phụ thuộc hàm F được gọi là tập phụ thuộc hàm có vế trái không dư thừa nếu như trong F không chứa phụ thuộc hàm nào có vế trái dư thừa. 
B. Thuật toán loại khỏi F các thuộc tính vế trái dư thừa 
Bước 1 : Lần lượt thực hiện bước 2 cho các phụ thuộc hàm X → Y trong F 
Bước 2 : Nếu tìm được X’ ⊂ X và X’ ≠ ∅ sao cho X’ → Y ∈ F + thì thay thế ngay phụ thuộc hàm X → Y trong F bằng X ’ → Y và thực hiện lại bước 2 với phụ thuộc hàm X ’ → Y vừa được thay thế. Nếu không, quay lại bước 1 
Ví dụ : Cho tập phụ thuộc hàm F = {A → BC, B → C, AB → D} 
Xét AB → D: Xét A có A + = ABCD nên A → D ∈ F + và ta thay AB → D trong F bằng A → D. Lúc này F = { A → BC, B → C, A → D } và là tập phụ thuộc hàm có vế trái không dư thừa. 
26 
5.4.3. TẬP PHỤ THUỘC HÀM CÓ VẾ PHẢI MỘT THUỘC TÍNH 
Bằng cách áp dụng luật phân rã, mọi tập phụ thuộc hàm F đều có thể đưa về tập phụ thuộc hàm G tương đương với nó mà vế phải mỗi phụ thuộc hàm trong G đều chỉ có 1 thuộc tính. 
Ví dụ 5.4 : 
F = {A → BC, B → DE, DG → AE} 
≡ G = {A → B, A → C, B → D, B → E, DG → A, DG → F} 
27 
5.4.4. TẬP PHỤ THUỘC HÀM KHÔNG DƯ THỪA 
5.4.4.1. Phụ thuộc hàm dư thừa 
Phụ thuộc hàm X → Y trong F được gọi là phụ thuộc hàm dư thừa nếu: F\{X → Y} ≡ F 
5.4.4.2 . Tập phụ thuộc hàm không dư thừa 
Tập phụ thuộc hàm F được gọi là tập phụ thuộc hàm không dư thừa nếu như nó không chứa phụ thuộc hàm dư thừa hay nói cách khác không tồn tại F’ ⊂ F mà F’ ≡ F. 
5.4.4.3. Thuật toán loại bỏ các phụ thuộc hàm dư thừa 
Bước 1: Lần lượt xét các phụ thuộc hàm X → Y ∈ F. 
Bước 2: Nếu X → Y ∈ (F\ {X → Y}) + thì loại X → Y khỏi F. 
Bước 3: Thực hiện bước 2 cho các phụ thuộc hàm khác của F. 
28 
Ví dụ 5.5 : Cho tập phụ thuộc hàm F = {X → YW, XW → Z, Z →Y, XY → Z } 
Hãy loại bỏ các phụ thuộc hàm dư thừa. 
Giải 
+ Xét X → YW: F\{ X → YW} = { XW → Z, Z →Y, XY → Z } 
X + = X ⊉ YW nên X → YW không dư thừa 
+ Xét XW → Z: F\{XW → Z} = { X → YW, Z →Y, XY → Z} 
(XW) + = XYWZ ⊇ Z nên XW → Z là dư thừa và bị loại khỏi F 
Lúc này F = {X → YW, Z →Y, XY → Z } 
+ Xét Z → Y: F\{ Z → Y} = {X → YW, XY → Z } 
(Z) + = Z ⊉ Y nên Z → Y không dư thừa 
+ Xét XY → Z: F\{ XY → Z} = {X → YW, Z → Y} 
(XY) + = XYW ⊉ Z nên XY → Z không dư thừa 
Vậy sau khi loại các phụ thuộc hàm dư thừa thì ta có được tập phụ thuộc hàm không dư thừa F = {X → YW, Z →Y, XY → Z} 
29 
5.4.5. PHỦ TỐI THIỂU 
5.4.5.1. Khái niệm 
Một tập phụ thuộc hàm được gọi là tập phụ thuộc hàm tối thiểu nếu thỏa mãn đồng thời 03 tính chất: 
1. Là tập phụ thuộc hàm có vế trái không dư thừa. 
2. Là tập phụ thuộc hàm có vế phải chỉ gồm 1 thuộc tính. 
3. Là tập phụ thuộc hàm không dư thừa. 
Với mỗi tập phụ thuộc hàm F bất kỳ, luôn tìm được ít nhất 1 tập phụ thuộc hàm tối thiểu tương đương với nó gọi là phủ tối thiểu . 
5.4.5.2 . Thuật toán tìm phủ tối thiểu của tập phụ thuộc hàm F 
Bước 1: Loại khỏi F các thuộc tính vế trái dư thừa. 
Bước 2: Đưa F về dạng có vế phải gồm 1 thuộc tính bằng cách sử dụng luật phân rã. 
Bước 3: Loại bỏ khỏi F các phụ thuộc hàm dư thừa. 
30 
Ví dụ 5.6 : Cho lược đồ quan hệ R(A,B,C,D) và tập phụ thuộc hàm: 
F = { AB → CD , B → C , C → D} Tìm phủ tối thiểu của F. 
Giải 
Bước 1 : Xét AB → CD: (B) + = BCD ⊇ CD nên B → CD ∈ F + 
Tức là có thể thay AB → CD bằng B → CD (A dư thừa) 
F = { B → CD, B → C, C → D } 
Bước 2 : Đưa tập phụ thuộc hàm F về tập phụ thuộc hàm tương đương có vế phải chỉ gồm 1 thuộc tính: 
F = {B → D , B → C, C → D} 
31 
Bước 3 : 
F = {B → D, B → C, C → D} 
+ Xét B → D: G = F\{B → D} = {B → C, C → D} có (B) + G = BCD nên B → D ∈ G + . Vậy B → D là dư thừa và ta loại nó khỏi F. Lúc này: 
F = {B → C, C → D } 
+ Xét B → C: G = F\{ B → C} = { C → D} có ( B) + G = B nên B → D ∉ G + . Vậy B → C không dư thừa. 
+ Xét C → D: G = F\{ C → D} = {B → C} có (C) + G = C nên C → D ∉ G + . Vậy C → D không dư thừa. Vậy phủ tối thiểu cần tìm là: F tt = { B → C, C → D } 
32 
5.5. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ 
5.5.1. ĐỊNH NGHĨA 
Cho lược đồ quan hệ R(Ω) với Ω là tập thuộc tính. Xét một tập thuộc tính K ⊆ Ω. Tập thuộc tính K được gọi là một khóa của lược đồ quan hệ R(Ω) khi và chỉ khi thỏa mãn đồng thời hai điều kiện sau đây: 
K + = Ω (hay K → Ω ∈ F + ). 
∄K o ⊂ K sao cho K o + = Ω (hay K o → Ω ∈ F + ). 
Khóa là tập thuộc tính tối thiểu có bao đóng bằng Ω (không có tập con nào của nó có tính chất như vậy). 
33 
Khóa dự tuyển (candidate key) : Trong một lược đồ quan hệ có thể tồn tại một hay nhiều khóa , ta gọi các khóa này là khóa dự tuyển (candidate key) hoặc đôi khi chỉ gọi tắt là khóa . 
Khóa chính (primary key) : Người ta có thể chọn ra một trong số các khóa dự tuyển để sử dụng. Khi đó, khóa được chọn ra sử dụng sẽ được gọi là khóa chính (primary key). 
Siêu khóa (super key) : Tập thuộc tính S được gọi là siêu khóa (super key) nếu nó chứa khóa hay K ⊆ S. 
Thuộc tính khóa và thuộc tính không khóa : 
Thuộc tính A được gọi là thuộc tính khóa (prime attribute) nếu như A ∈ K với K là một khóa bất kỳ của lược đồ quan hệ. 
Ngược lại, A được gọi là thuộc tính không khóa (nonprime attribute). 
34 
5.5.2. CÁC TÍNH CHẤT CỦA KHÓA 
Tập các phụ thuộc hàm của lược đồ quan hệ R( Ω) là: 
F = { L i → R i | L i , R i ⊆ Ω; i = 1,2,,n } 
Đặt là tập gồm các thuộc tính xuất hiện ở vế trái của các phụ thuộc hàm và là tập gồm các thuộc tính xuất hiện ở vế phải của các phụ thuộc hàm . 
Tính chất 1 : Với mọi khóa K của lược đồ quan hệ ta luôn có: 
Ω\R ⊆ K ⊆ (Ω\R) ∪ (L∩R ) 
L∩R 
Ω\R 
K 
35 
Tính chất 2 : Các khóa của lược đồ quan hệ chỉ khác nhau trên các thuộc tính nằm trong tập L ∩ R 
Tính chất 3 : Nếu L ∩ R = ⍉ thì ta có Ω\R là khóa duy nhất của lược đồ quan hệ. 
Tính chất 4 : Nếu R\L ≠ ⍉ thì tồn tại khoá K sao cho K ≠ Ω là khoá không tầm thường . 
5.5.3. THUẬT TOÁN TÌM MỘT KHÓA CỦA LƯỢC ĐỒ QUAN HỆ 
Ý tưởng : 
Khóa của lược đồ quan hệ bị kẹp giữa hai tập thuộc tính là Ω\R và (Ω\R ) ∪ ( L∩ R) 
C ác khóa chỉ khác nhau trên các thuộc tính nằm trong tập L∩R. 
⇒ Thuật toán tìm khóa: xuất phát từ tập siêu khóa (Ω\R )∪ ( L∩R ), loại bỏ dần các thuộc tính nằm trong tập L∩R cho đến khi thu được tập thuộc tính nhỏ nhất có bao đóng là Ω thì dừng lại. 
36 
Input: 	 	Tập thuộc tính Ω và tập phụ thuộc hàm F. 
Output: 	Một khóa K của lược đồ quan hệ. 
begin 
X:= Ω\R 
If (Ω\R) + ⊂ Ω then 
begin 
X:= X ∪ (L∩R) 
for each A i ∈ L∩R do 
if (X\{A i }) + = Ω then X:= X\{A i }; 
e nd ; 
K:=X; 
end . 
37 
Ví dụ 5.7 : Cho lược đồ quan hệ R(A,B,C,D,E,G) với tập phụ thuộc hàm 
F = { B→C, C→B, A→GD} 
Hãy chỉ ra một khóa của lược đồ quan hệ này. 
Giải 
Ω = ABCDEG, L = ABC, R = BCDG 
Ω\R = AE, L∩R = BC 
Ta thấy (Ω\R) + = (AE) + = AEDG ⊂ Ω nên: 
X = Ω\R ∪ (L∩R) = ABCE 
Xét (X\{B}) + = (ACE) + = ABCEGD = Ω ⟹ X = ACE 
Xét (X\{C}) + = (AE) + = ADEG ≠ Ω ⟹ Không thể loại bỏ C khỏi X. 
Vậy K = X = ACE là một khóa của lược đồ quan hệ. 
38 
Ví dụ 5.8 : Cho lược đồ quan hệ R(A,B,C,D,E,G,H,I) với tập phụ thuộc hàm 
F = { AB→E, AG→I, BE→I, E→G, GI→H} 
Hãy chỉ ra một khóa của lược đồ quan hệ này. 
Giải 
Ω = ABCDEGHI, L = ABEGI, R = EGHI 
Ω\R = ABCD, L∩R = EGI 
Ta thấy (Ω\R) + = (ABCD) + = ABCDEGHI = Ω 
⟹ K = ABCD là khóa duy nhất. 
39 
Bước 1 : Đặt TN = Ω\R và TG = L∩R 
Bước 2 : 
if TG= ⍉ then 
Lược đồ quan hệ chỉ có một khóa K = TN; 
Kết thúc thuật toán; 
e lse 
Qua bước 3; 
Bước 3 : Tìm tất cả các tập con X i của tập TG 
Bước 4 : 
Gọi S là tập các khóa của lược đồ quan hệ; 
Đặt S = ⍉; 
Tìm các siêu khóa S i bằng cách: 
 ∀X i 
if (TN ∪ X i ) + = Ω then 
begin 
S i = TN ∪ X i ; 
S = S ∪ {S i }; 
end ; 
Bước 5 : Tìm khóa bằng cách loại bỏ các siêu khóa không tối thiểu: 
∀S i , S j ∈ S 
if (S i ⊂ S j ) then S = S\{S j }; 
S còn lại chính là tập siêu khóa cần tìm; 
5.5.3. THUẬT TOÁN TÌM TẤT CẢ CÁC KHÓA CỦA LƯỢC ĐỒ QUAN HỆ 
40 
Ví dụ 5.9 : Cho lược đồ quan hệ R(C,S,Z) với tập phụ thuộc hàm: 
F = {CS→Z, Z→C} 
Hãy tìm tất cả các khóa của lược đồ quan hệ này. 
Giải 
TN = Ω\R = S, TG = L∩R = CZ 
Gọi X i là các tập con của tập TG. Ta có bảng sau: 
V ậy ta tìm được tất cả là 2 khóa: SC, SZ. Siêu khóa SCZ bị loại vì nó không phải là siêu khóa tối thiểu. 
X i 
S i = TN ∪ X i 
(TN ∪ X i ) + 
Siêu khóa 
Khóa 
⍉ 
S 
S 
C 
SC 
Ω 
SC 
SC 
Z 
SZ 
Ω 
SZ 
SZ 
CZ 
SCZ 
Ω 
SCZ 
41 
Ví dụ 5.10 : Cho lược đồ quan hệ R(A,B,C,D,E,G) với tập phụ thuộc hàm 
F = {B→C, C→B, A→GD} 
Hãy tìm tất cả các khóa của lược đồ quan hệ này. 
Giải 
Ω = ABCDEG, L = ABC, R = BCDG 
TN = Ω\R = AE, TG = L∩R = BC 
Gọi X i là các tập con của tập TG. Ta có bảng sau: 
Vậy ta tìm được tất cả là 2 khóa: ABE, ACE. Siêu khóa ABCE bị loại vì nó không phải là siêu khóa tối thiểu. 
X i 
S i = TN ∪ X i 
(TN ∪ X i ) + 
Siêu khóa 
Khóa 
⍉ 
AE 
AEDG 
B 
ABE 
Ω 
ABE 
ABE 
C 
ACE 
Ω 
ACE 
ACE 
BC 
ABCE 
Ω 
ABCE 
42 
Ví dụ 5.11 : Cho lược đồ quan hệ R(A,B,C,D) với tập phụ thuộc hàm 
F = {AB→C, B→D, BC→A} 
Hãy tìm tất cả các khóa của lược đồ quan hệ này. 
Giải 
Ω = ABCD 
L = ABC, R = ACD 
TN = Ω\R = B 
TG = L∩R = AC 
Gọi X i là các tập con của tập TG. Ta có bảng sau: 
Vậy ta tìm được tất cả là 2 khóa: AB, BC. Siêu khóa ABC bị loại vì nó không phải là siêu khóa tối thiểu. 
X i 
S i = TN ∪ X i 
(TN ∪ X i ) + 
Siêu khóa 
Khóa 
⍉ 
B 
BD 
A 
AB 
Ω 
AB 
AB 
C 
BC 
Ω 
BC 
BC 
AC 
ABC 
Ω 
ABC 
43 
Ví dụ 5.12 : Cho lược đồ quan hệ R(A,B,C,D,E,H) với tập phụ thuộc hàm 
F = {A→E, C→D, E→DH} 
Hãy tìm tất cả các khóa của lược đồ quan hệ này. 
Giải 
Ω = ABCDEH, L = ACE, R = DEH 
TN = Ω\R = ABC, TG = L∩R = E 
Gọi X i là các tập con của tập TG. Ta có bảng sau: 
Vậy ta tìm được tất cả là 1 khóa: ABC. Siêu khóa ABCE bị loại vì nó không phải là siêu khóa tối thiểu. 
X i 
S i = TN ∪ X i 
(TN ∪ X i ) + 
Siêu khóa 
Khóa 
⍉ 
ABC 
Ω 
ABC 
ABC 
E 
ABCE 
Ω 
ABCE 
44 
Ví dụ 5.13 : Cho lược đồ quan hệ R(A,B,C,D,E,I) với tập phụ thuộc hàm 
F = {ACD→EBI, CE→AD} 
Hãy tìm tất cả các khóa của lược đồ quan hệ này. 
Giải 
Ω = ABCDEI, L = ACDE, R = ABDEI 
TN = Ω\R = C, TG = L∩R = ADE 
Gọi X i là các tập con của tập TG. Ta có bảng sau: 
Vậy ta tìm được tất cả là 2 khóa: CE, ACD. Các siêu khóa ACE, CDE, ACDE bị loại vì nó không phải là siêu khóa tối thiểu (có chứa siêu khóa CE). 
X i 
S i = TN ∪ X i 
(TN ∪ X i ) + 
Siêu khóa 
Khóa 
⍉ 
C 
C 
A 
AC 
AC 
D 
CD 
AD 
E 
CE 
Ω 
CE 
CE 
AD 
ACD 
Ω 
ACD 
ACD 
AE 
ACE 
Ω 
ACE 
DE 
CDE 
Ω 
CDE 
ADE 
ACDE 
Ω 
ACDE 
Q & A 
45