Bài 12. Phủ Của Tập Phụ Thuộc Hàm

BÀI 12: PHỦ CỦA TẬP PHỤ THUỘC HÀM
12.1: Định nghĩa tương đương
Định lý: Cho F là tập các phụ thuộc hàm trên U và f là một phụ thuộc hàm trên U, khi đó 2 việc sau tương đương
(1)F├f
(2)F╞f
Tức là, phụ thuộc hàm f được suy dẫn từ F theo quan hệ khi và chỉ khi nó được suy dẫn từ F theo hệ tiên đề Amstrong.
1









12.2: Các tập phụ thuộc hàm tương đương
Cho F và G là hai tập phụ thuộc hàm trên tập thuộc tính U, ta nói rằng tập phụ thuộc hàm F tương đương với tập phụ thuộc hàm G nếu và chỉ nếu F+ =G+. Nếu F+ =G+ thì ta nói F là phủ của G và ngược lại G là phủ của F.

*Thuật toán xác định F và G có tương đương hay không?

Bước 1: Với mỗi phụ thuộc hàm X→Y của F ta xác định xem X→Y có được suy dẫn từ G không?
Bước 2: Với mỗi phụ thuộc hàm X→ Y của G ta xác định xem X→Y có được suy dẫn từ F không?
Nếu cả hai bước trên đều đúng thì F≡G.










2
Ví dụ: Cho lược đồ quan hệ có:
F={A→BC, A→D, CD→E}
G={A→BCE, A→ABD, CD→E}
a) F có tương đương với G không?
b) F có tương đương với G’={A→BCDE} không?
a) Ta có AG+ = ABCDE
=> Trong G+có A→BC và A→D => F G+=> F+  G+(1)
AF+= ABCDE => trong F+có A→ BCE và A→ABD
=>F+G => F+ G+(2)
Từ (1)và (2)=>F+ = G+ =>F+ ≡ G+
b) Do (CD)+ =CD=> G không chứa phụ thuộc hàm CD→E
=> F không tương đương với G+




3
12.3: Phụ thuộc hàm không dư thừa

12.3.1: Phụ thuộc hàm dư thừa
Cho F là tập các phụ thuộc hàm trêu U, f là một phụ thuộc hàm của F tức là f  F, f được gọi là dư thừa trong F nếu như (F-f)+ = F+.
Hay có thể nói tương đương f được gọi là dư thừa trong F nếu nó suy dẫn được từ tập F sau khi đã bỏ đi phụ thuộc hàm f.
4
* Thuật toán xác định f= X→Y có phải là thành viên của F hay không?
Bước 1: Tạm xóa f khỏi F, gọi G là tập thu được G=F-f, nếu G  thì chuyển qua bước 2, còn không thì kết thúc thuật toán và kết luận f là không dư thừa trong F.
Bước 2: Giả sử f = X→Y nếu G├f tứcY XG+ thì f là dư thừa trong F còn ngược lại f là không dư thừa(là thành viên).
Hay
Bước 1: Tính
Bước 2: So sánh X+ với Y nếuX+  Y ta khẳng định X→Y là thành viên của F.
5
Ví dụ: Cho F={AB→C, C→D, AB→D}
Cho biết AB→D có dư thừa trong F hay không?
Bước 1: G = F-{f} = {AB→C,C→D}
Bước 2: (AB)G+= AB  C = ABC  D = ABCD  D
G├ f
f không là thành viên của F hay f dư thừa trong F.
6
12.3.2: Phủ không dư
Cho F và G là 2 tập phụ thuộc hàm trên U, F được gọi là phủ không dư của G khi và chỉ khi
+ F+ = G+ (F là phủ của G)
+f F thì (F-f)+  F (tức mọi phụ thuộc hàm trong F đều không dư thừa)

Định lý: Mọi tập phụ thuộc hàm đều tồn tại phủ không dư.
7
12.4: Phủ thu gọn
12.4.1: Phụ thuộc hàm có vế trái dư thừa
F là tập các phụ thuộc hàm trên lược đồ quan hệ Q, Z là tập thuộc tính, Z→Y F. Nói rằng phụ thuộc hàm Z→Y có vế trái dư thừa ( phụ thuộc không đầy đủ ) nếu có một A  Z sao cho:
F=F-{Z→Y} {(Z-A)→Y}
Ngược lại Z→Y là mọt phụ thuộc hàm có vế trái không dư thừa hay Y phụ thuộc hàm đầy đủ vào Z hay phụ thuộc hàm đầy đủ.

Chú ý: Phụ thuộc hàm có vế trái chứa một thuộc tính là phụ thuộc hàm đầy đủ.
8
* Thuật toán loại khỏi F các phụ thuộc hàm có 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 Z→Y của F (với các phụ thuộc hàm có vế trái có từ 2 thuộc tính trở lên).
Bước 2: Với mỗi tập con thật sự của X,
Nếu X+→Y  F+ thì thay X→Y trong F bằng X+→Y thực hiện lại bước 2.
9
12.4.2: Tập phụ thuộc hàm có vế phải một thuộc tính

Mỗi tập phụ thuộc hàm F đều tương đương với một tập phụ thuộc hàm G mà vế phải của các phụ thuộc hàm trong G chỉ gồm một thuộc tính.
Ví dụ:
F={A→BC, B→C, AB→D}
ta suy ra
F={A→B, A→C, B→C, AB→D} = G
10
12.4.3: Tập phụ thuộc hàm không dư thừa(phủ không dư)
Nói rằng F là tập phụ thuộc hàm không dư thừa nếu không tồn tại F’  F sao cho F’ ≡ F. Ngược lại, F là tập phụ thuộc hàm dư thừa.

Ví dụ:
Cho F={A → BC, B → D, AB → D}
thì F dư thừa vì F’-F = {A → BC, B → D}
11
* Thuật toán loại khỏi F 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 của F.
Bước 2: Nếu X → Y là thành viên của 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 tiếp theo của F.
12
12.4.4: Tập phụ thuộc hàm tối thiểu
F được gọi là một phụ thuộc hàm tối thiểu (phủ tối thiểu) nếu F thỏa mãn đồng thời ba điều kiên sau:
1. F là tập phụ thuộc hàm có vế trái không dư thừa.
2. F là tập phụ thuộc hàm có vế phải một thuộc tính.
3. F là tập phụ thuộc hàm không dư thừa.
Trong đó, điều kiện 1 và 2 có thể thay đổi vị trí cho nhau
13
*Thuật toán tìm phủ tối thiểu của một tập phụ thuộc hàm
Bước 1: Loại bỏ khỏi F các phụ thuộc hàm có vế trái dư thừa.
Bước 2: Tách các phụ thuộc hàm có vế phải trên một thuộc tính thành các phụ thuộc hàm có vế phải một thuộc tính.
Bước 3: Loại bỏ khỏi F các phụ thuộc hàm dư thừa.
14
Ví dụ: Cho lược đồ quan hệ Q(A, B, C, D) và tập phụ thuộc hàm F như sau F={AB →CD, B →C, C→ D}
Hãy tính phủ tối thiểu của F?
Bước 1: AB →CD là phụ thuộc hàm có vế trái dư thừa?
B →CD  F+?
Trả lời: B+ = BCD => B →CD  F+
Vậy AB →CD là phụ thuộc hàm có vế trái dư thừa A
Kết quả của bước 1 là:
F={B →CD, B →C, C→ D}
Bước 2: Kết quả của bước 2 là:
F={B →D, B →C, C→ D} = F1tt
15
Bước 3: Trong F1tt , B→C là phụ thuộc hàm dư thừa?
B→C  G+ ? với G= F1tt -{B→C} = {B→D, C→D}
BG+= BD => B→C  G+ => trong F1tt ,B→C không dư thừa.
Trong F1tt , B→D là phụ thuộc hàm dư thừa?
B→D G+ ?với G =F1tt -{B→D} = {B→C, C→D}
BG+= BCD => B→D  G+ => trong F1tt ,B→D dư thừa.

Kết quả của bước 3 cho phủ tối thiểu:
F={B→C, C→D} = Ftt
16
BÀI 14:KHÓA CỦA LƯỢC ĐỒ QUAN HỆ
14.1: Khóa và siêu khóa
Đn1: Cho lược đồ quan hệ α=(U,F), KU nếu K+=U, thì ta nói K là một siêu khóa.
Chú ý: Điều kiện K+=U có thể thay bằng K →U hoặc K→ UK.
Đn2: Cho lược đồ quan hệ α=(U,F), tập KU được gọi là khóa của lược đồ α nếu như nó thỏa mãn:
K là một siêu khóa.
 K1 K thì K1 không là siêu khóa tức K1+ ≠U.
17
Chú ý: Định nghĩa 2 tương đương với định nghĩa :

Cho lược đồ quan hệ α=(U,F), tập KU được gọi là khóa của lược đồ α nếu như nó thỏa mãn:
a) K→ UF+
b)K1K thì K1 → UF+
Hai điều kiện trên còn tương đương với:
a) K+=U.
b)AK thì (K-{A})+U.
Hoặc nó tương đương với
a)K→U.
b)AK thì (K-{A})+→U.




18
*Tính chất của khóa và siêu khóa
Hợp của 2 siêu khóa là một siêu khóa.
Giao của 2 siêu khóa chưa chắc là một siêu khóa.
Hai khóa bất kỳ không giao nhau.
Hợp của 2 khóa là 1 khóa khi và chỉ khi lược đồ có duy nhất 1 khóa.
Một lược đồ có thể có nhiều khóa.
Bản thân U là một siêu khóa.
Với mọt quan hệ R trên U, thì R luôn có ít nhất một khóa.
19
* Tìm một siêu khóa của lược đồ
Cho lược đồ quan hệ α=(U,F), hãy tìm một siêu khóa K của lược đồ
Ta có thể tìm siêu khóa K của lược đồ theo các bước sau:
Đặt L= Li |Li →Ri  F
Đặt R= Ri |Li →Ri  F
Đặt K = UR  L thì K là một siêu khóa.
*Nhận xét: Khi đã có một siêu khóa nếu ta bỏ đi một số thuộc tính ta sẽ thu được một khóa.
20
14.2: Họ Sperner và khóa
Nếu gọi Kα là tập tất cả các khóa của lược đồ α=(U,F), như vậy mỗi phần tử của Kα là một tập thuộc tính và các tập hợp đó là không bao nhau.
Định nghĩa: Họ Sperner trên U là họ M ={X|X  U} sao cho hai phần tử của M là không bao nhau.
Nhận xét: Tập hợp Kα tất cả các khóa của lược đồ là 1 họ Sperner trên U.
21
14.3: Một số vấn đề về khóa
14.3.1: Kiểm tra một tập cho trước có phải là khóa hay không?
Cho K  U hỏi rằng K có phải là khóa hay không?
Cách làm: Tính
+)Nếu U thì K không là khóa của lược đồ.
+)Nếu K+=U chứng tỏ K là một siêu khóa
Để kiểm tra K có phải là khóa không ta lấy mọi tập con thực sự của K, nếu tất cả các tập con thực sự của K đều không là siêu khóa thì chứng tỏ K là khóa, nếu tồn tại một tập con thực sự của K là siêu khóa thì K không phải là khóa .
22
14.3.2: Tìm một khóa của lược đồ quan hệ
Cho lược đồ α=(U,F), hãy tìm một khóa K
Tư tưởng chung:
B1) Trước hết chọn một siêu khóa K.
B2) Từ siêu khóa đó kiểm tra xem nó có phải là khóa không.
B3) Nếu K là khóa thì dừng thuật toán, ngược lại chuyển bước tiếp theo.
B4) Nếu K chưa phải là khóa thì có K1 là tập con thực sự của K và lớn nhất của K và K1 là siêu khóa, thay K bằng K1 và quay trở lại bước 2.
23
14.3.3: Giao của tất cả các khóa
Ký hiệu Iα là tập mà mỗi phần tử của nó tham gia vào tất cả các khóa của lược đồ hay Iα là giao của tất cả các khóa của lược đồ.
Ký hiệu Nα là tập mà mỗi phần tử của nó không tham gia vào bất cứ một khóa nào của lược đồ.
Ký hiệu Sα ={U (Ri -Li )|  Li →RiF}
Ta sẽ chứng minh được Iα = Sα
24
Định nghĩa: Cho lược đồ quan hệ α=(U,F), thuộc tính A trong U được gọi là thuộc tính tiền định nếu như A có mặt ở vế phải của một phụ thuộc hàm bất kỳ thì A cũng phải xuất hiện ở vế trái của phụ thuộc hàm đó hoặc thuộc tính A không xuất hiện ở bất cứ phụ thuộc hàm nào.

Định lý 1: Cho lược đồ quan hệ α=(U,F),
gọi N={ (Ri -Li )| Li  Iα} khi đó N  Nα (hay N là tập chứa một số các phần tử không khóa của lược đồ ).


25
Định lý 2: Với Y Nα và X  Iα thì Y (XY)+ X  Nα 1
Hệ quả : Từ định lý 2 ta thấy nếu N={ (Ri -Li )| Li Iα } thì N’=(N Iα)+Iα  Nα

Định lý 3: Cho lược đồ quan hệ α=(U,F), gọi N”=RL|(R=Ri ,,L= Li )|  Li →RiF} (N” là tập tất cả các thuộc tính chỉ xuất hiện ở vế phải mà không xuất hiện ở vế trái của các tập phụ thuộc hàm) thì N”  Nα.
26
14.3.4: Thuật toán tìm giao của tất cả các khóa

Giao của tất cả các khóa được tìm theo công thức:
Iα ={U (Ri - Li)}
27
14.3.5: Thuật toán kiểm tra 1 lược đồ đã cho có một hay nhiều khóa?
Bước 1: Tìm giao của tất cả các khóa của lược đồ Iα .
Bước 2: Nếu (Iα)+= U thì lược đồ đã cho có duy nhất một khóa.
Bước 3: Nếu (Iα)+U thì lược đồ có nhiều khóa.
28
14.3.6: Thuật toán tìm tất cả các khóa của lược đồ quan hệ
*Thuật toán 1:
Bước 1: Xác định tất cả các tập con khác rỗng của Q+. Kết quả tìm được giả sử là các tập thuộc tính X1, X2, …, X2n -1.
Bước 2: Tìm bao đóng của các X1.
Bước 3: Siêu khóa là các X1 có bao đóng đúng bằng Q+. Giả sử ta đã có các siêu khóa là S = {S1, S2,…,Sm}.
Bước 4: Xây dựng tập chứa tất cả các khóa của Q từ tập S bằng cách xét mọi Si, Sj con của S(i ≠j), nếu Si  Sjthì ta loại Sj (i,j=1,..,n) kết quả còn lại của S chính là tập tất cả các khóa cần tìm.
29
*Thuật toán 2:
B1) Xác định Iα .
B2) Nếu (Iα)+ =U thì kết luận lược đồ có 1 khóa duy nhất là Iα và kết thúc thuâth toán, ngược lại thì chuyển sang bước tiếp theo.
B3) Xác định N={ (Ri -Li )| Li Iα }
+) Đặt N’ = (IαN)+ Iα (N’Nα )
+) Đặt B =UN’Iα .
B4) Nếu |B|=2 (tập B chỉ gồm có 2 thuộc tính ), giả sử B=B1B2 khi đó lược đồ chỉ có 2 khóa là B1 và B2, kết thúc thuật toán. Ngược lại nếu |B| > 2 thì chuyển sang bước tiếp theo.
B5) Tìm tất cả các tập con khác rỗng của B, ký hiệu các tập con đó là{B1, B2, …, Bn}. Tính ( Bi Iα)+ (i=1…n), nếu ( Bi Iα)+ =U thì đặt Mi = Bi Iα
30
*Thuật toán 2:
B6) Khi đó M={ M1, M2, …, Mh} là họ tất cả các siêu khóa của lược đồ α.
B7) Loại bỏ các siêu khóa không tối thiểu ra khỏi M, tức là nếu  Mi  Mj(*) (i≠j,i,j= ) thì loại Mj ra khỏi M. Tập M thu được sau khi loại bỏ tất cả các phần tử thỏa mãn biểu thức (*) chính là họ tất cả các khóa của lược đồ α.


31